Estruturas de Dados Intermediário/Pilhas

Pilha ou stack é um tipo especial de lista linear em que todas as operações de inserção e remoção são realizadas pela mesma extremidade chamada topo.

Uma representação simplificada de uma Pilha

Os elementos são removidos na ordem inversa daquela em que foram inseridos de modo que o último elemento que entra é sempre o primeiro que sai, por isto este tipo de estrutura é chamada LIFO (Last In - First Out).

O exemplo mais prático que costuma utilizar-se para entender o processo de pilha é como uma pilha de livros ou pilha de pratos, no qual ao se colocar diversos elementos uns sobre os outros, se quisermos pegar o livro mais abaixo deveremos tirar todos os livros que estiverem sobre ele."

Operações sobre pilhas

Uma pilha geralmente suporta três operações básicas:

• TOP: acessa-se o elemento posicionado no topo da pilha;
• PUSH: insere um novo elemento no topo da lista;
• POP: remove o elemento do topo da lista.

Se tivermos uma pilha p e um elemento x qualquer, a operação PUSH (p,x) acrescenta o elemento x no topo da pilha e aumenta-lhe o tamanho. Já a operação POP(P) remove o elemento que está no topo da pilha fazendo com que esta diminua. Já a operação TOP não altera o tamanho da estrutura , pois simplesmente visita o topo da pilha retornado uma cópia do elemento que encontra-se no seu topo.

Visualização do comportamento de uma pilha

Na tabela abaixo é descrito o comportamento de uma pilha. A primeira coluna descreve qual operação é efetuada sobre uma pilha que inicia vazia, a segunda coluna descreve os elementos da pilha e como estão organizados (estando o "topo" à direita), visualização descreve o elemento visitado quando utilizado o TOP e a quarta coluna mostra a quantidade de elementos na pilha.

Operação	Pilha	Visualização	Tamanho da Pilha
PUSH (P,1)	1		1
PUSH (P,2)	1,2		2
TOP	1,2	2	2
PUSH (P,3)	1,2,3		3
POP (P)	1,2		2
POP (P)	1		1
POP (P)			0

Operações auxiliares

Ao implementar uma pilha dentro do computador a quantidade de memória alocada funciona como um dos fatores limitantes da pilha. Assim são necessárias mais três operações para manipular corretamente a estrutura.

• INIT: inicia a pilha como "Vazia"
• IS_EMPTY: verifica se a pilha está "Vazia"
• IS_FULL: verifica se a pilha está "cheia"

Toda vez que criamos uma estrutura de pilha, esta deve ser inicializada para garantir que não haja nenhuma "sujeira" no local onde esteja montada. Para verificar se uma pilha P está vazia, devemos usar uma função Is_Empty(P) que retorna verdadeiro se uma pilha estiver vazia. A função Is_Full (P) é utilizada para verificar se a pilha está cheia, retornando verdadeiro caso não haja espaço para armazenar mais elementos.

Is_Full não é o contrário de Is_Empty. Quando Is_Empty retorna falso, não siginifica no entanto que ela esteja cheia. Do mesmo modo se uma função Is_Full retorna falso não significa que a pilha esteja vazia.

Pseudo-código de uma pilha

    record Nodo {
    data  //informação a ser armazenada no nodo
    próximo // referência ao próximo nodo; null para o último nodo
 }

    record Stack {
     Node stackPointer   // ponteiro para o nodo do topo; valor null para uma pilha vazia
 }

  function push(Stack stack, Element element) { // insere elemento em uma pilha
     new(newNode)            // Aloca memória para manter novo node
     newNode.data   := element
     newNode.next   := stack.stackPointer
     stack.stackPointer := newNode
 }

 function pop(Stack stack) { // retira o elemento do topo e retorna o nodo do topo agora
     node := stack.stackPointer
     stack.stackPointer := node.next
     element := node.data      
     return element
 }

 function top(Stack stack) { // retorna o nodo no topo
     return stack.stackPointer.data
 }

 function length(Stack stack) { // retorna a quantidade de nodos na pilha
     length := 0
     node := stack.stackPointer
     while node not null {
         length := length + 1
         node := node.next
     }
     return length
 }

Aplicações de Pilhas

Pilhas são utilizados em diversas aplicações em Ciências da Computação. Um dos mais salientes casos é a análise de expressões e sintaxe. Calculadores que utilizam a Notação Polonesa Reversa utilizam pilha para expressar seus valores, podendo ser representadas de forma prefixa, posfixa ou infixa. Conversões de uma forma de expressão para outras também necessitam de pilhas. Muitos compiladores utilizam pilhas para análise sintática de expressões, blocos de programas e afins.

Exemplo de uso de pilha em Notação Polonesa Reversa

Por exemplo: ((1 + 2) * 4) + 3 em notação pós-fixa

1 2 + 4 * 3 +

Utilizando uma pilha consideramos:

• empilhar quando encontrar um operando;
• sacar dois operandos e achar o valor quando encontrar uma operação.
• empilhar o resultado.

Entrada	Operação	Pilha
1	push operando	1
2	push operando	1, 2
+	adicionar	3
4	Push operando	3, 4
*	multiplicar	12
3	push operando	12, 3
+	adicionar	15

O resultado final 15 estará no topo da pilha no fim do cálculo.

Aula-Auxílio

• Notação Polonesa

Bibliografia

• Stack program in c++
• Stack Machines - the new wave
• Bounding stack depth
• Libsafe - Protecting Critical Elements of Stacks
• Stack Size Analysis for Interrupt-driven Programs (322 KB)
• Stack Implementation ( Graphical & Text Mode) C Language implementation of Stack
• Pointers to stack visualizations