03 Pilhas e Filas

Prévia do material em texto

Gerson Borges
Gerson da Silva Borges
gerson.borges@prof.una.br
1Algoritmos e Programação
PILHAS
• Uma pilha é uma lista liner em que 
todas as inserções, retiradas e 
acessos são feitas pelas 
extremidades da lista.
• Pilhas são usadas em aplicações 
que somente necessitam acesso 
pelos seus extremos.
• Os itens são colocados uns sobre 
os outros como numa pilha de 
pratos.
Gerson Borges 2
• Propriedade:
• O último item inserido é o primeiro item 
que pode ser retirado da lista.
(LIFO last-in first-out) 
• A ordem linear de uma pilha vai do 
mais recente para o menos recente.
• Ideal para estruturas aninhadas de 
profundidade imprevisível,situação em 
que é necessário garantir que 
subestruturas mais internas sejam 
processadas antes da estrutura que as 
contenha.
Algoritmos e Programação
PILHAS
• Algoritmos recursivos são
exemplos.
Gerson Borges 3
• Propriedade:
• O último item inserido é o primeiro item 
que pode ser retirado da lista.
(LIFO last-in first-out) 
• A ordem linear de uma pilha vai do 
mais recente para o menos recente.
• Ideal para estruturas aninhadas de 
profundidade imprevisível,situação em
que é necessário garantir que
subestruturas mais internas sejam
processadas antes da estrutura que as 
contenha.
Algoritmos e Programação
LISTAS ENCADEADAS
typedef struct
{ TipoChave Chave;
/* outros componentes */
} TipoItem;
typedef struct Celula_str *Apontador;
typedef struct Celula_str
{ TipoItem Item;
Apontador Prox;
} Celula;
typedef struct
{ Apontador Primeiro, Ultimo;
} TipoLista;
Gerson Borges 4
Chave
Item
Célula
prox
últimoprimeiro
Lista
Algoritmos e Programação
LISTAS ENCADEADAS
void FLVazia(TipoLista *Lista)
{
Lista->Primeiro = (Apontador) 
malloc(sizeof(Celula));
Lista->Ultimo = Lista->Primeiro;
Lista->Primeiro->Prox = NULL;
}
int Vazia(TipoLista Lista)
{
return (Lista.Primeiro == Lista.Ultimo);
}
Gerson Borges 5
prox
últimoprimeiro
Lista
Algoritmos e Programação
LISTAS ENCADEADAS
void Insere(TipoItem x, TipoLista *Lista)
{
Lista->Ultimo->Prox = (Apontador) 
malloc(sizeof(Celula));
Lista->Ultimo = Lista->Ultimo->Prox;
Lista->Ultimo->Item = x;
Lista->Ultimo->Prox = NULL;
}
Gerson Borges 6
prox
últimoprimeiro
Lista
prox
Algoritmos e Programação
LISTAS ENCADEADAS
void Retira(Apontador p, TipoLista *Lista, TipoItem *Item)
{
/* O item a ser retirado e o seguinte ao apontado por p */
Apontador q;
if (Vazia(*Lista) || p == NULL || p->Prox == NULL) 
{ cout << "Lista vazia ou posicao nao existe\n";
return;
}
q = p->Prox;
*Item = q->Item;
p->Prox = q->Prox;
if (p->Prox == NULL)
Lista->Ultimo = p;
free(q);
}
Gerson Borges 7Algoritmos e Programação
LISTAS ENCADEADAS
void Imprime(TipoLista Lista)
{
Apontador Aux;
Aux = Lista.Primeiro->Prox;
while (Aux != NULL) 
{
cout << Aux->Item.Chave;
Aux = Aux->Prox;
}
}
Gerson Borges 8Algoritmos e Programação