PRG29003: Introdução a Pilhas
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()) {
int x = numeros.top();
numeros.pop();
cout << "Topo da pilha: " << x << " e o desempilhou ..." << endl;
}
}
Atividades
Objetivo: escrever um programa que localize um arquivo dentro de uma árvore de diretórios.
A busca deve iniciar em algum subdiretório a ser informado, e ela termina ao encontrar o arquivo (ou se não encontrá-lo !). Ao localizar o arquivo procurado, deve ser informado o caminho seguido até encontrá-lo. O diretório inicial e o nome do arquivo devem ser fornecidos, respectivamente, no primeiro e segundo argumentos de linha de comando.
Para se familiarizar com pilhas, resolva estes problemas. Observe que eles estão disponibilizados no GitHub (ver instruções de acesso):