PRG29003: Introdução a Pilhas: mudanças entre as edições
Ir para navegação
Ir para pesquisar
Sem resumo de edição |
|||
| Linha 24: | Linha 24: | ||
Na [https://pt.wikipedia.org/wiki/Standard_Template_Library biblioteca STL] existe a estrutura de dados [http://www.cplusplus.com/reference/stack/stack/ stack], que implementa uma pilha. Suas operações elementares são estas: | |||
* [http://www.cplusplus.com/reference/stack/stack/push/ push]: empilha um dado | |||
* [http://www.cplusplus.com/reference/stack/stack/pop pop]: desempilha um dado | |||
* [http://www.cplusplus.com/reference/stack/stack/back back]: acessa o dado que está no topo da pilha | |||
* [http://www.cplusplus.com/reference/stack/stack/empty empty]: retorna ''true'' se pilha estiver vazia | |||
* [http://www.cplusplus.com/reference/stack/stack/size size]: retorna a quantidade de dados armazenados na pilha | |||
| Linha 66: | Linha 37: | ||
#include <iostream> | #include <iostream> | ||
#include <string> | #include <string> | ||
#include < | #include <stack> | ||
using namespace std; | using namespace std; | ||
int main() { | int main() { | ||
// uma pilha | // uma pilha para armazenar inteiros | ||
stack<int> numeros; | |||
numeros.push(6); | numeros.push(6); | ||
| Linha 83: | Linha 53: | ||
while (not numeros.vazia()) { | while (not numeros.vazia()) { | ||
cout << "Topo da pilha: " << numeros. | cout << "Topo da pilha: " << numeros.back() << " e o desempilhou ..." << endl; | ||
} | } | ||
| Linha 92: | Linha 61: | ||
== Atividades == | == Atividades == | ||
* [[Introdução_C%2B%2B]] | * [[Introdução_C%2B%2B]] | ||
Edição das 17h48min de 26 de fevereiro de 2020
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
- back: 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.comprimento() << endl;
while (not numeros.vazia()) {
cout << "Topo da pilha: " << numeros.back() << " e o desempilhou ..." << endl;
}
}
1 Atividades
Resolva esses problemas: