Aula 8 Pilha Sequencial A.pdf

Prévia do material em texto

Pilha - Alocac¸a˜o Sequencial
Professor:
Silvio Luiz Bragatto Boss
e-mail:
silvioboss@utfpr.edu.br
Universidade Tecnolo´gica Federal do Parana´ - UTFPR
Coordenac¸a˜o de Informa´tica - COINF
Curso de Engenharia de Computac¸a˜o
Disciplina de Estrutura de Dados I
Pilha
Suma´rio
1 Pilha
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha
Pilha e´ uma estrutura de dados cujo funcionamento e´
inspirado em uma pilha “natural”;
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha
Pilha e´ uma estrutura de dados cujo funcionamento e´
inspirado em uma pilha “natural”;
Exemplo: Pilha de pratos.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha
Pilha e´ uma estrutura de dados cujo funcionamento e´
inspirado em uma pilha “natural”;
Exemplo: Pilha de pratos.
Na pilha (stack) as operac¸o˜es de inserc¸a˜o e remoc¸a˜o sa˜o
efetuadas apenas no final (topo) da pilha:
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha
Pilha e´ uma estrutura de dados cujo funcionamento e´
inspirado em uma pilha “natural”;
Exemplo: Pilha de pratos.
Na pilha (stack) as operac¸o˜es de inserc¸a˜o e remoc¸a˜o sa˜o
efetuadas apenas no final (topo) da pilha:
Itens ADICIONADOS no topo da pilha.
Itens REMOVIDOS do topo da pilha.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha
Pilhas sa˜o chamadas de listas LIFO (last-in, first-out);
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha
Pilhas sa˜o chamadas de listas LIFO (last-in, first-out);
O u´ltimo elemento a ser inserido sera´ o primeiro a ser retirado;
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha
Pilhas sa˜o chamadas de listas LIFO (last-in, first-out);
O u´ltimo elemento a ser inserido sera´ o primeiro a ser retirado;
Pilhas sa˜o u´teis para processar estruturas aninhadas.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha
Pilhas sa˜o chamadas de listas LIFO (last-in, first-out);
O u´ltimo elemento a ser inserido sera´ o primeiro a ser retirado;
Pilhas sa˜o u´teis para processar estruturas aninhadas.
Exemplo:
expresso˜es alge´bricas;
func¸o˜es de programa que chamam outras func¸o˜es.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha
Pilhas sa˜o chamadas de listas LIFO (last-in, first-out);
O u´ltimo elemento a ser inserido sera´ o primeiro a ser retirado;
Pilhas sa˜o u´teis para processar estruturas aninhadas.
Exemplo:
expresso˜es alge´bricas;
func¸o˜es de programa que chamam outras func¸o˜es.
Pilhas sa˜o utilizadas para implementar algoritmos de ana´lise
sinta´tica e de avaliac¸a˜o de expresso˜es, utilizados em
compiladores e interpretadores.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Inserc¸a˜o e Exclusa˜o de Elementos em uma Pilha
(a) Pilha vazia.
(b) Insere o item ‘A’ na pilha.
(c) Insere o item ‘B’ na pilha.
(d) Retira o item ‘B’ na pilha.
(e) Insere o item ‘C’ na pilha.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha como um TDA
TDA - Tipo abstrato de dado
Um TDA engloba a definic¸a˜o do tipo do dado e das operac¸o˜es
relacionadas com este tipo.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha como um TDA
TDA - Tipo abstrato de dado
Um TDA engloba a definic¸a˜o do tipo do dado e das operac¸o˜es
relacionadas com este tipo.
Um TDA para a estrutura pilha, envolve a declarac¸a˜o do tipo
de dado pilha e das operac¸o˜es realizadas sobre a pilha.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Modelagem da Pilha - alocac¸a˜o sequencial/encadeada
Representac¸a˜o Sequencial
Utiliza vetores (estruturas esta´ticas);
Vetores possuem um espac¸o limitado para o armazenamento
de dados;
Necessa´rio definir um espac¸o o suficiente para conter a pilha;
A alocac¸a˜o sequencial exige uma a´rea cont´ıgua de memo´ria.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Modelagem da Pilha - alocac¸a˜o sequencial/encadeada
Representac¸a˜o Sequencial
Utiliza vetores (estruturas esta´ticas);
Vetores possuem um espac¸o limitado para o armazenamento
de dados;
Necessa´rio definir um espac¸o o suficiente para conter a pilha;
A alocac¸a˜o sequencial exige uma a´rea cont´ıgua de memo´ria.
Representac¸a˜o Encadeada
Utiliza a alocac¸a˜o dinaˆmica de memo´ria.
Ponteiros sa˜o utilizados para identificar a sequeˆncia de
elementos da pilha.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Aspecto Estrutural
Utiliza um vetor para armazenar as informac¸o˜es da pilha;
Necessita de um indicador da posic¸a˜o atual do topo (final) da
pilha.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Aspecto Estrutural
Utiliza um vetor para armazenar as informac¸o˜es da pilha;
Necessita de um indicador da posic¸a˜o atual do topo (final) da
pilha.
Pilha pode ser representada por uma estrutura que conte´m:
Uma matriz de itens da pilha;
I´ndice para o topo da pilha.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha - Representac¸a˜o Sequencial
Pseudoco´digo
constante Maxpilha = 100;
tipo Pilha {
inteiro item[Maxpilha];
inteiro topo;
}
Pilha aPilha;
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Pilha - Representac¸a˜o Sequencial
Exemplo de Implementac¸a˜o
#define MAX 100
typedef struct{
int item[MAX];
int topo;
}Pilha;
...
Pilha p;
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Aspecto Funcional
Operac¸o˜es da Pilha
Inicializar a pilha;
Adicionar um item na pilha;
Remover um item da pilha;
Testar se a pilha esta´ vazia;
Testar se a pilha esta´ cheia.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Algoritmo inicializaPilha
Pseudoco´digo
FUNC¸~AO inicializaPilha(Pilha aPilha)
inicio
aPilha.topo <- 0;
fim;
Exemplo de implementac¸a˜o
void iniPilha(Pilha *p) {
p->topo = 0;
}
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Algoritmo pilhaVazia
Pseudoco´digo
inteiro FUNC¸~AO pilhaVazia(Pilha aPilha)
inicio
SE (aPilha.topo = 0)
RETORNE(Verdadeiro);
SEN~AO
RETORNE(Falso);
fim;
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Algoritmo pilhaVazia
Exemplo de Implementac¸a˜o
int vaziaPilha(Pilha *p) {
if (p->topo == 0)
return(1);
else
return(0);}
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Algoritmo pilhaCheia
Pseudoco´digo
inteiro FUNC¸~AO pilhaCheia(Pilha aPilha)
inicio
SE (aPilha.topo = Maxpilha)
RETORNE(Verdadeiro);
SEN~AO
RETORNE(Falso);
fim;
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Algoritmo emPilha
Procedimentos Realizados
Verifica se ha´ espac¸o, ou seja, se a pilha na˜o esta´ cheia;
Adiciona o novo dado;
Incrementa o topo da pilha.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Algoritmo emPilha
Procedimentos Realizados
Verifica se ha´ espac¸o, ou seja, se a pilha na˜o esta´ cheia;
Adiciona o novo dado;
Incrementa o topo da pilha.
Paraˆmetros
O dado a ser inserido;
A pilha.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Algoritmo emPilha
Procedimentos Realizados
Verifica se ha´ espac¸o, ou seja, se a pilha na˜o esta´ cheia;
Adiciona o novo dado;
Incrementa o topo da pilha.
Paraˆmetros
O dado a ser inserido;
A pilha.
Constante utilizada pelo algoritmo
constante ErroPilhaCheia = -1
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Algoritmo emPilha
Pseudoco´digo
inteiro FUNC¸~AO emPilha(Pilha aPilha, inteiro dado)
inicio
SE (PilhaCheia)
RETORNE(ErroPilhaCheia);
SEN~AO
aPilha.item[aPilha.topo] <- dado;
aPilha.topo <- aPilha.topo + 1;
RETORNE(aPilha.topo);FIM SE
fim;
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Algoritmo desemPilha
Procedimentos Realizados
Verifica se ha´ elementos na pilha, ou seja, se a pilha na˜o esta´
vazia;
Decrementa o topo da pilha;
Retorna o elemento do topo da pilha.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Algoritmo desemPilha
Procedimentos Realizados
Verifica se ha´ elementos na pilha, ou seja, se a pilha na˜o esta´
vazia;
Decrementa o topo da pilha;
Retorna o elemento do topo da pilha.
Paraˆmetros
A pilha.
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Algoritmo desemPilha
Procedimentos Realizados
Verifica se ha´ elementos na pilha, ou seja, se a pilha na˜o esta´
vazia;
Decrementa o topo da pilha;
Retorna o elemento do topo da pilha.
Paraˆmetros
A pilha.
Constante Utilizada pelo Algoritmo
constante ErroPilhaVazia = -2;
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX
Pilha
Algoritmo desemPilha
Pseudoco´digo
inteiro FUNC¸~AO desemPilha (Pilha aPilha)
inicio
SE (PilhaVazia)
RETORNE(ErroPilhaVazia);
SEN~AO
aPilha.topo <- aPilha.topo - 1;
RETORNE(aPilha.item[aPilha.topo]);
FIM SE
fim;
Silvio Luiz Bragatto Boss UTFPR
Pilha LATEX