Pilha c

Estrutura de Dados
PILHAS

Ciência
Computação
Aula 2
Prof. Botas

Prof. Luis C. Botas www.lcbotas.com.br 1

PILHAS: Fundamentos - Operações
• Definição:
 É um tipo de lista linear, onde todas as operações (inserção/remoção) são realizadas numa mesma extremidade (topo)
 Devido a forma de acesso, os elementos são sempre removidos em ordem inversa a que foram inseridos, daí a expressão LIFO (Last-In / First-Out)

Operações Comuns:
 Push (empurrar): insere um novo elemento no topo da pilha
 Pop (saltar): remove um elemento do topo da pilha
Exemplo:

b a a

a

Push(P,a)

Push(P,b)

Pop(P)

Prof. Botas

Pop(P)

2

PILHAS: Fundamentos - Operações
Considerações:
• Init: inicializar a pilha no estado vazia
• Empty (vazio): verificar se a pilha esta vazia. Uma operação POP não se aplica a uma pilha sem elementos para desempilhar (UnderFlow)
Em geral, uma pilha tem o espaço como seu fator limitante (não cresce indeterminadamente)
 Full (cheio):verificar se a pilha esta cheia. Em caso positivo a operação PUSH não será executada (Overflow)
 StackTop: determinar ou apontar o item superior da pilha sem removê-lo.
 Atenção! – FULL não é o inverso de EMPTY
Exemplos simples de uso de pilha:
 Conversão de decimal em binário
 Agrupamento de expressões com “(“, “*“ e “{“ (Pg.94)
Implementação:
 Uma pilha é um conjunto ordenado de itens, portanto o modo mais simples de implementar é utilizando VETOR (desde que declarado suficientemente grande) Prof. Botas

3

PILHAS: Implementação
Como construir uma pilha:
 Estrutura de 2 objetos: um Vetor para armazenar os elementos da pilha, e uma variável (inteira) para indicar a posição do topo da pilha.
#define vetorpilha 100 struct pilha { int topo; int elementos[vetorpilha];
} s; /* s  stack (pilha) */
Considerando que uma pilha vazia não possui elementos, então ela pode ser referenciada como topo equivalendo a -1 (já que o vetor representativo da
pilha