|
A pilha foi inicialmente proposta em 1955, e patenteada em 1957, pelo alemão [[Friedrich Ludwig Bauer]].<ref name="patent">{{cite paper|publisher=Deutsches Patentamt|url=http://v3.espacenet.com/origdoc?DB=EPODOC&IDX=DE1094019&F=0&QPN=DE1094019 |title=Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens.|date=30. März 1957<!-- Bekanntmachung der Anmeldung und Ausgabe der Auslegeschrift: 1. Dezember 1960. Dr. Friedrich Ludwig Bauer und Dr. Klaus Samelson, München, sind als Erfinder genannt worden. Erteilt 12. August 1971, DE-PS 1094019.-->|accessdate=2010-10-01|language=german|authors=Dr. Friedrich Ludwig Bauer and Dr. Klaus Samelson|address=Germany, Munich}}</ref> O mesmo conceito foi desenvolvido, por volta da mesma época, pelo australiano [[Charles Leonard Hamblin]].
== Aspectos{{Ver Importantestambém}} ==
Uma pilha é uma [[estrutura de dados]] que permite inclusão e remoção de elementos seguindo a regra de que, caso haja remoção, o elemento a ser removido é sempre o que está na estrutura há menos tempo. Essa regra é conceitualmente conhecida como [[LIFO]], Last-In-First-Out, ou seja, o primeiro elemento que entrar será o último elemento a sair.
Pilhas podem ser utilizadas no âmbito de Software e no âmbito de Hardware.
No âmbito de Software, uma pilha pode ser implementada de diversas maneiras em um programa, sendo que as formas de implementação mais comuns são através de [[vetores]] e [[listas encadeadas]]. As pilhas são facilmente implementadas utilizando vetores e listas encadeadas e por isso são as formas de implementação mais comuns.
No âmbito de Hardware, um uso comum de pilhas são ao nível de arquitetura como um meio de alocação e acesso a memória.
== Operações básicas (Operações essenciais) ==
Uma pilha é estrutura de dados restrita, devido ao fato de apenas permitir um pequeno número de operações sobre ela. Basicamente apenas duas operações: Empilhar (Push) e Desempilhar (Pop). Como a pilha segue a lógica do Last-In-First-Out ([[LIFO]] - Primeiro a entrar é último a sair) essas duas operações (Push e Pop) são executadas somente sobre o elemento ao topo da pilha.
*'''Empilhar (Push)'''
A operação de empilhar insere um elemento no topo da pilha. Também é utilizada para inicializar a pilha (caso seja feito sobre uma pilha vazia). É necessário verificar se a pilha está cheia antes de permitir essa operação a fim de impedir uma possível transborda.
*'''Desempilhar (Pop)'''
A operação de desempilhar remove um elemento do topo da pilha e retorna o valor do elemento removido para fins de leitura. É necessário verificar se a pilha está vazia antes de permitir essa operação a fim de impedir qualquer erro que possa ser gerado por tentar ler e remover elementos inexistentes.
== Operações não-essenciais ==
Além das operações básicas, também podem ser implementadas operações extras que incrementem a funcionalidade de uma pilha e/ou permita maior flexibilidade ao lidar com ela.
*'''Ler Topo'''
A operação de ler o topo faz a leitura do elemento ao topo sem remove-lo da pilha, essa operação é considerada não essencial pois pode ser reproduzida através das operações básicas Pop e Push com dados iguais (primeiro execute o pop e com seu retorno execute um push).
*'''Verificar se está vazia'''
Operação que tem por objetivo identificar se não há nenhum elemento na pilha, caracterizando que ela está vazia.
*'''Verificar se está cheia'''
Operação que tem por objetivo identificar se a pilha possui o máximo de elementos que ela poderia possuir, caracterizando que ela está cheia.
*'''Inicializar'''
Operação que inicializa uma pilha e a coloca em estado de "pronta". Durante a inicialização é possível definir um tamanho máximo para a pilha.
== Aplicações ==
Pilhas possuem inúmeras aplicações, elas estão por toda a parte, basicamente qualquer operação que siga a lógica do Last-In-First-Out ([[LIFO]] - Primeiro a entrar é o último a sair) pode ser considerado um uso de pilha. Um pequeno exemplo de nosso cotidiano é na cozinha ao lavar pratos: Ensaboamos os pratos e os empilhamos para posteriormente enxagua-los, e assim, sempre enxaguaremos por último o primeiro prato que foi ensaboado e sempre enxaguaremos primeiro o último prato ensaboado.
Voltando ao mundo da [[computação]], seguem abaixo exemplos de aplicações:
'''Verificação de sintaxe: parênteses e colchetes.'''<ref name="verificacao_sintaxe_parenteses_colchetes">{{cite paper|publisher=USP.br|url=http://www.ime.usp.br/~pf/algoritmos/aulas/pilha.html|title=Estrutura de dados: Pilha.|accessdate=2013-11-16}}</ref>
Suponha que queremos decidir se uma dada sequência de parênteses e colchetes está bem-formada (ou seja, parênteses e colchetes são fechados na ordem inversa àquela em que forma abertos). Por exemplo, a primeira das sequências abaixo está bem-formada enquanto a segunda não está.
* (()[()])
* ([)]
Nesse caso utiliza-se pilhas para, ao ler uma determinada cadeia de caracteres, empilhar os parênteses e colchetes esquerdos (aberturas) e, quando encontrar um parêntese ou colchete direito (fechamento), comparar se há correspondência com o esquerdo no topo da pilha. Se corresponder o elemento é removido do topo da pilha, se não corresponder o programa retorna o erro.
'''Histórico de navegação na internet'''
Um histórico de navegação pode ser entendido como um sistema de retrocesso ([[backtracking]]) onde a etapas de determinada ação são registradas sequencialmente, supondo que a ação em questão possua etapas que retornem em erro (um caminho errado em um labirinto, por exemplo) é possível voltar à etapa anterior e tentar uma nova opção.
Os históricos de navegação empilham as páginas acessadas pelo usuário, dessa forma quando ele solicita retorno irá retornar à última página que entrou na pilha, ou seja, a última página visitada.
Sistemas modernos de histórico de navegação também implementam o retorno às páginas que o usuário estava antes de solicitar o retorno, essa operação é comumente chamada de avançar e é facilmente implementada ao gerar uma segunda pilha que armazena a página que o usuário está visualizando no momento da solicitação do retorno.
A imagem abaixo demonstra o histórico de navegação:
[[File:Historico-navegacao.png|Histórico de Navegação]]
== Referências ==
{{reflist}}
== {{Ver também}} ==
== {{Ligações externas}} ==
| 