Pilha e fila

FEUP/LEEC Algoritmos e Estruturas de Dados 2001/2002

Pilhas e Filas

João Canas Ferreira http://www.fe.up.pt/~jcf

FEUP/LEEC,AED,2001/2002, v0.1

Pilhas e Filas

#1

Conteúdo
1. Pilhas (a) Implementação baseada em listas (b) Implementação baseada em vectores 2. Filas (a) Implementação baseada em listas (b) Implementação baseada em vectores 3. Aplicações de pilhas (a) Cálculo de expressões RPN (b) Conversão de expressões infixas para RPN 4. Aplicação de filas (a) Percurso mais curto num labirinto

FEUP/LEEC,AED,2001/2002, v0.1

Pilhas e Filas

#2

1

Pilhas

Pilha Estrutura de dados em que a inserção e a remoção de elementos de uma sequência se faz pela mesma extremidade, geralmente designada por topo da pilha. Uma pilha pode ser considerada como uma restrição de lista. Visto que se trata de uma estrutura de dados mais simples que a lista, é possível obter implementações mais eficazes. O conceito de iterador não se aplica a esta estrutura de dados. LIFO = Last-in First-out

FEUP/LEEC,AED,2001/2002, v0.1

Pilhas e Filas

#3

Operações com pilhas
1 2 3 4 5 5 1 2 3 4 5 3 2 1 1 2 1 4 3 2 1 4 3 2 1

5

4

3

2

2

5 4 3 2 1 4 3 2 1 3 2 1 2 1 1 5 4 3 2 1

FEUP/LEEC,AED,2001/2002, v0.1

Pilhas e Filas

#4

2

Pilha – Implementação baseada em listas template class LStack { public: LStack(); LStack(const LStack &stk); ~LStack(); bool isEmpty() const; bool isFull() const; const T & top() const; void makeEmpty(); void pop(); void push(const T &x); T topAndPop(); const LStack & operator=(const LStack &stk); ///... Pilhas e Filas #5

FEUP/LEEC,AED,2001/2002, v0.1

Classe LStack – Secção privada template class LStack { // ... private: class ListNode // classe privada { public: T element; ListNode *next; ListNode(const T & elem, ListNode *n = 0) : element(elem), next(n) { }; }; ListNode *topOfStack; };

FEUP/LEEC,AED,2001/2002, v0.1

Pilhas e Filas

#6

3

push() e top()

template void LStack::push(const