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

A declaração da Pilha na biblioteca Prglib é esta:

template <typename T> class pilha {
 public:
  // construtor: deve-se informar a capacidade da pilha
  pilha(unsigned int umaCapacidade);
 
  // construtor de cópia: cria uma pilha que é cópia de outra
  pilha(const pilha<T>& outra);
 
  // destrutor da pilha
  ~pilha();
 
  // operador de atribuição: torna esta pilha uma cópia de outra pilha
  pilha<T> & operator=(const pilha<T> & outra);
 
  // operações da pilha
 
  virtual void push(const T & dado); // empilha um dado
 
  T pop(); // desempilha um dado
 
  virtual const T& top() const; // retorna o dado do topo da pilha, sem retirá-lo
 
  bool vazia() const;
  bool cheia() const;
  unsigned int comprimento() const;
  void esvazia();
  unsigned int capacidade() const;
  
 private:
  unsigned int N;
};

Arquivo libs/pilha.h

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

#include <iostream>
#include <string>
#include <prglib.h>

using namespace std;
using namespace prglib;

int main() {
  // uma pilha com capacidade de armazenar 20 inteiros
  pilha<int> numeros(20);

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

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

  while (not numeros.vazia()) {
    cout << "Topo da pilha: " << numeros.top() << endl;
    cout << "... desempilhou: " << numeros.pop() << endl;
  }

}

Atividades

• Introdução_C++
• Biblioteca Prglib

Resolva esses problemas:

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