A Estrutura de Dados

Universidade Veiga de Almeida

Estrutura de Dados – Parte III

Prof. Eliane Xavier Cavalcanti

V - Pilha (Stack)

É uma lista linear, em que todas as inserções e remoções de elementos só podem ser feitas numa extremidade chamada Topo.

As pilhas também são chamadas de estruturas LIFO (Last In First Out), ou seja, o último elemento inserido é o primeiro a ser removido.

[pic 1]

5.1- Implementação (Estática)

A maneira mais simples de se representar uma pilha é através de um vetor de m elementos.

Digamos que este vetor chama-se P e seus elementos tem índices 0, 1, 2, ..., m-1.

O número máximo de elemento da pilha será m, o elemento do fundo será P[0], o elemento seguinte P[1] e assim por diante. Devido a este fato, esta representação é chamada seqüencial.

Associada a pilha tem-se uma variável chamada Topo, de tal forma que o elemento no topo da

pilha será P[Topo].

Pode-se convencionar que Topo = -1 indica uma pilha vazia.

Operações associadas com uma pilha:

• Inicializar uma pilha P vazia

• Inserir na pilha P

• Excluir da Pilha P

• Verificar se a pilha P está vazia

Exemplo de uso de Pilhas

• processamento das chamadas de sub-rotinas e seus retornos

• simulação de sistemas

• sequencias bem-formadas

• Análise de expressões Pós fixas (Calculadores HP)

Algoritmos para Pilha utilizando vetores

Convenções:

Topo = -1 indica pilha vazia

Topo = TAM_VET - 1 indica pilha cheia

Inicialização

Topo = -1

INSERÇÃO

Se Topo = TAM_VET -1 então

“PILHA CHEIA - INSERÇÃO IMPOSSÍVEL”

senão

Topo = Topo + 1

P[Topo] = Elemento

Fimse

REMOÇÂO

Se Topo = -1 então

“PILHA VAZIA - REMOÇÃO IMPOSSÍVEL”

senão

Elemento = P[Topo]

Topo = Topo -1

Fimse

Exemplo 1 – Implementação de pilhas com vetores em linguagem C - pilha de floats

#include

#define TAM_VET 10

#define VERD 1

#define FALSO 0

#define ERRO -1

void Inic_Pilha (int &Topo) {

Topo = -1;

}

int Pilha_Vazia(int Topo) {

if (Topo == -1)  return(VERD);

return(FALSO);

}

int Pilha_Cheia(int Topo) {

if (Topo == TAM_VET-1) return(VERD);

return(FALSO);

}

int Empilha(float P[], int &Topo, float x) {

if (Topo == TAM_VET-1) {

            printf ( "Erro - Ins. Pilha cheia");

return(ERRO);

}

else {

Topo++;

P[Topo] = x;