Pilha e fila

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2293 palavras )
  • Download(s) : 0
  • Publicado : 25 de março de 2013
Ler documento completo
Amostra do texto
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 deexpressõ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 delista. 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 11 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(constT &x) { topOfStack = new ListNode(x, topOfStack); } template const T & LStack::top() const { if (isEmpty()) throw Underflow(); return topOfStack->element; }

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

Pilhas e Filas

#7

pop() e topAndPop()
template void LStack::pop() { if (isEmpty()) throw Underflow(); ListNode *oldTop = topOfStack; topOfStack = topOfStack->next; delete oldTop; } template TLStack::topAndPop() { T topItem = top(); pop(); return topItem; }

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

Pilhas e Filas

#8

4

Pilhas–Implementação baseada em vectores

template class VStack { public: explicit VStack(int capacity = 100); bool isEmpty() const; bool isFull() const; const T & top() const; void makeEmpty(); void pop(); void push(const T &x); T topAndPop(); //...FEUP/LEEC,AED,2001/2002, v0.1

Pilhas e Filas

#9

VStack – Secção privada
template class VStack { // ... private: vector theArray; int topOfStack; };

Atenção: Não deixar o vector aumentar de tamanho.
topOfStack =3 VAZIO

topOfStack = -1

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

Pilhas e Filas

# 10

5

Classe VStack – Implementação
template bool VStack::isFull() const { return topOfStack ==theArray.size() - 1; } template void VStack::makeEmpty() { topOfStack = -1; } template void VStack::push(const T &x) { if (isFull()) throw Overflow(); theArray[++topOfStack] = x; }

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

Pilhas e Filas

# 11

Classe VStack – pop() e top()
template const T & VStack::top() const { if (isEmpty()) throw Underflow(); return theArray[topOfStack]; } template voidVStack::pop() { if (isEmpty()) throw Underflow(); topOfStack--; } template T VStack::topAndPop() { if (isEmpty()) throw Underflow(); return theArray[topOfStack--]; } Pilhas e Filas # 12

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

6

Filas

Fila Estrutura de dados em que a inserção e a remoção de elementos de uma sequência se faz por extremidades opostas, geralmente designadas por cabeça e cauda da fila....
tracking img