Pilha

SEM0543 – Organização de Dados em
Computadores
Estruturas de dados

Estudo de caso: pilha ou stack
(LIFO – Last In, First Out)

Pilha baseada em Vetor

Simples modo de implementar um TAD Pilha usando vetor Adicionar elementos da esquerda para a direita
Uma variável mantém o índice para o elemento do topo da pilha …

S
0 1 2

t

3

Pilha baseada em Vetor

OPERAÇÕES
Algorithm tamanho() return t + 1
Algorithm desempilhar() if vazia() then return PilhaVazia else t←t−1 return S[t + 1]
…

S
0 1 2

t
4

Pilha baseada em vetor (cont.)
O vetor armazenando os elementos na pilha pode ficar cheio
Uma operação de empilhar deve retornar PilhaCheia
Essa é uma limitação da implementação de pilha baseada em vetor
(não intrinsica do TAD Pilha)

Algorithm empilhar(o) if t = S.length − 1 then return PilhaCheia else t←t+1
S[t] ← o

…

S
0 1 2

t
5

Implementação Pilha
#include
#define MAX 10
/* Informa sobre a ocorrencia de overflow. */ void overflow() { printf ("Overflow!! Pilha no limite maximo.\n");
}
/* Informa sobre a ocorrencia de underflow. */ void underflow() { printf ("Underflow!! Pilha no limite minimo.\n");
}
/* Inicializa a pilha. */ void inicializaPilha(int *topo, int *pilha) {
*topo = -1;
}
/* "Limpa" o conteudo da pilha. */ void limpaPilha(int *topo, int *pilha) {
*topo = -1;
}
6

Implementação Pilha (cont.)
/* Verifica se a pilha esta' vazia. Devolve 1 se estiver, senao devolve 0. */ int pilhaVazia(int *topo, int *pilha){ if (*topo == -1) return 1; else return 0;
}
/* Verifica se a pilha esta' vazia. Devolve 1 se estiver, senao devolve 0. */ int pilhaCheia(int *topo, int *pilha){ if (*topo == (MAX-1)) return 1; else return 0;
}
7

Implementação Pilha (cont.)
/* Insere um elemento na pilha. */ void empilha(int *valor, int *topo, int *pilha)
{
if (pilhaCheia(topo, pilha)) overflow(); /* pilha cheia*/ else{ *topo = *topo + 1; pilha[*topo] = *valor;
}