PRG29003: Introdução a Pilhas

Próxima aula

Pilhas são estruturas de dados lineares, em que os dados são retirados em ordem inversa a que foram inseridos. Esse comportamento é denominado LIFO (Last In First Out - último a entrar, primeiro a sair).

Algumas pilhas da vida real ...

Pilhas apresentam três operações típicas:

* Push: empilha um novo dado (acrescenta-o ao topo da pilha). * Pop: desempilha um dado (retira-o do topo da pilha) *Top: acessa o dado do topo da pilha (sem retirá-lo)

Algumas aplicações de pilhas são:

• Cálculo de expressões em diferentes representações (infix, postfix, prefix)
• Balanceamento de símbolos em expressões, tais como parênteses, chaves e outros.
• Operações como refazer ou desfazer em editores e outros programas
• Avançar e recuar entre páginas visitadas em navegadores web
• Usada em muitos algoritmos, tais como travessias de árvores (usada, por exemplo, em procura de arquivos em diretórios), resolução de labirintos, resolvedor de sudoku, problema do período de preços de ações

Na biblioteca STL existe a estrutura de dados stack, que implementa uma pilha. Suas operações elementares são estas:

• push: empilha um dado
• pop: desempilha um dado
• top: acessa o dado que está no topo da pilha
• empty: retorna true se pilha estiver vazia
• size: retorna a quantidade de dados armazenados na pilha

... e um exemplo de uso é mostrado a seguir:

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main() {
  // uma pilha para armazenar inteiros
  stack<int> numeros;

  numeros.push(6);
  numeros.push(8);
  numeros.push(10);
  numeros.push(12);

  cout << "Pilha de numeros tem comprimento=" << numeros.size() << endl;

  while (! numeros.empty()) {
    cout << "Topo da pilha: " << numeros.top() << " e o desempilhou ..." << endl;
    numero.pop();
  }

}

Atividades

• Introdução_C++

Resolva esses problemas. Observe que eles estão disponibilizados no GitHub (ver instruções de acesso)::

1. Empilhador de caracteres
2. Inversor das linhas de um arquivo
3. Reduzir caminhos de arquivos
4. Criação de uma fila usando pilhas