Pilhas
Estrutura de Dados
Marco Antonio Montebello Júnior
[email protected]
Pilhas




Estrutura de dados variável
LIFO – Last In, First Out (Último a entrar é o
primeiro a sair)
FILO = First In, Last Out (Primeiro que entra é
o último a sair)
Aplicações:


Análise de expressões
Conversão de notações
Introdução a Computação
Representando Pilhas com
Vetor

Vetor


Pilha




Possui uma quantidade prévia de elementos
É dinâmica
Aumenta e diminui conforme empilhamos e
desempilhamos os elementos
Pilhas e Vetores são estruturas diferentes
Iremos utilizar inicialmente vetores para
representarmos as pilhas
Introdução a Computação
Pilhas
ENTRADA
SAÍDA
TOPO
Elemento 2
Elemento 1
BASE
Introdução a Computação
Representado a Pilha

Vamos utilizar uma estrutura (struct) para
representar a nossa pilha que será chamada de
stack
#define MAXPILHA 100
struct stack
{
int Topo;
int Item[MAXPILHA];
};
Introdução a Computação
Representado a Pilha

Levando em consideração a estrutura criada,
podemos declarar uma pilha da seguinte
maneira:
struct stack s;
Introdução a Computação
Entendimento da Estrutura

Item


Vetor onde os elementos que são empilhados são
armazenados
Topo


Armazena a posição que se encontra o último
elemento da pilha
Quando a pilha estiver vazia o topo é igual à -1
Introdução a Computação
Manipulação de Pilhas
Iniciando uma Pilha



Inicializa uma Pilha
O topo da pilha passa a ter o valor -1, o qual
indica que a mesma está vazia
O vetor não precisa ser inicializado com 0’s
(zeros)
void IniciaPilha(struct stack *ps);
IniciaPilha(&s);
Introdução a Computação
Manipulação de Pilhas
Verificando Limites

Pilha Vazia


Verifica se a pilha está vazia
Retorna:


True – Quando estiver realmente vazia (1)
False – Quando não estiver vazia (0)
int iPilhaVazia(struct stack *ps);
iRet = iPilhaVazia(&s);
Introdução a Computação
Manipulação de Pilhas
Verificando Limites

Pilha Cheia


Verifica se a pilha está cheia
Retorna:


True – Quando estiver realmente cheia (1)
False – Quando não estiver cheia (0)
int iPilhaCheia(struct stack *ps);
iRet = iPilhaCheia(&s);
Introdução a Computação
Manipulação de Pilhas
Empilhando um Elemento (push)



Adiciona um elemento no topo da pilha
É chamada de PUSH
Deve-se sempre verificar se a pilha já não está
cheia
int iPush(struct stack *ps, int iVal);
iRet = iPush(&s, iNum);
Introdução a Computação
Manipulação de Pilhas
Desempilhando um Elemento (pop)



Retira um elemento do topo da pilha
É chamada de POP
Deve-se verificar se a pilha não está vazia
int iPop(struct stack *ps);
iRet = iPop(&s);
Introdução a Computação
Manipulação de Pilhas
Consultando o Topo da Pilha

Consulta o elemento do topo da pilha sem
desempilhar o mesmo
int iElemTopo(struct stack *ps);
iRet = iElemTopo(&s);
Introdução a Computação
Exemplo de Pilhas

Exemplo do Trem

Demonstrar a execução do programa de
Pilhas
Introdução a Computação
Exercícios

Utilizando as funções de PUSH e POP de pilhas,
coloque na ordem determinada as letras que se
encontrar em uma Pilha P1 na Pilha P2, pode ser
utilizada uma variável auxiliar para realizar as trocas

Frase Original: AES-SI
Introdução a Computação
Exercícios

Utilizando pilhas, crie um algoritmo que
reordene um conjunto de dados fornecido pelo
usuário tal que o primeiro e o último elementos
devem ser trocados de posição e todos os
elementos entre o primeiro e o último deve
também ser trocados relativamente
Ex.:
{12345}
{54321}
Introdução a Computação
Exercícios

Utilizando pilhas, crie um algoritmo que
converta um número decimal para binário.
Ps.: A conversão de números binários para
decimal se dá através da divisão sucessiva
dos resultados até que o mesmo seja 0 ou 1
Exemplo: (100011)2 = (35)10
Introdução a Computação
Exercícios

Um palavra é considerada palíndroma se ela pode se
lida da esquerda para a direita ou da direita para a
esquerda com o mesmo significado. Neste caso não
podemos considerar as acentuações, as letras
maiúsculas ou minúsculas, os espaços e os caracteres
especiais. Exemplos:





Subi no Onibus
Radar
Ana
Go dog
Utilizando pilhas, desenvolva um algoritmo que
determine se uma expressão é palíndroma ou não.
Introdução a Computação