Algoritmos e Estruturas de Dados IIEC012

Pilhas e FilasPilhas e Filas

Prof. César MeloTodos os créditos ao Prof. Leandro Galvão

Pilhas e FilasPilhas e Filas

Pilhas e filas são casos especiais das listas Pilhas e filas são casos especiais das listas encadeadas.encadeadas.

Ambas possuem regras rigorosas para Ambas possuem regras rigorosas para acessar os dados armazenados nelas.acessar os dados armazenados nelas.

As operações de recuperação de dados são As operações de recuperação de dados são destrutivas....destrutivas....

Pilha, característicasPilha, características

É uma das estruturas de dados mais simples;É uma das estruturas de dados mais simples;

Todo o acesso a seus elementos é feito através do Todo o acesso a seus elementos é feito através do seu topo;seu topo;

Quando um novo elemento é introduzido na pilha, Quando um novo elemento é introduzido na pilha, ele passa a ser o elemento do topo, e o único ele passa a ser o elemento do topo, e o único elemento que pode ser removido da pilha é o do elemento que pode ser removido da pilha é o do topo.topo.

PilhasPilhas

Implementa uma política “o primeiro que sai Implementa uma política “o primeiro que sai é o último que entrou (LIFO – last in, first é o último que entrou (LIFO – last in, first out)”.out)”.

Existem duas operações básicas que devem Existem duas operações básicas que devem ser implementadas numa estrutura de pilha: ser implementadas numa estrutura de pilha:

operação para operação para empilharempilhar ( (pushpush) um novo elemento, ) um novo elemento, inserindo-o no topo, inserindo-o no topo,

operação para operação para desempilhardesempilhar ( (poppop) um elemento, ) um elemento, removendo-o do toporemovendo-o do topo

PilhasPilhas:: :: PushPush

topo

k

m

x

topo

k

m

x

a

topo

k

m

x

a

b

push(a)

push(b)

PilhasPilhas:: :: PopPop

k

m

x

topo

topo

k

m

x

topo

k

m

x

aa

b

pop(b)

pop(a)

PilhasPilhas:: Operações básicas:: Operações básicas

Criar uma estrutura de pilha;Criar uma estrutura de pilha;

Inserir um elemento no topo (push);Inserir um elemento no topo (push);

Remover o elemento do topo (pop);Remover o elemento do topo (pop);

Verificar se a pilha está vazia;Verificar se a pilha está vazia;

Verificar se a pilha está cheia(se pilha Verificar se a pilha está cheia(se pilha estática)estática)

Liberar a estrutura de pilhaLiberar a estrutura de pilha

PilhasPilhas:: Implementação de pilha usando :: Implementação de pilha usando alocação dinâmicaalocação dinâmica

typedef struct noh TNo;struct noh { int info; TNo* prox;};

typedef struct pilha TPilha;struct pilha {

TNo* topo;};

PilhasPilhas:: Criar uma estrutura de pilha:: Criar uma estrutura de pilha

Mostrar a implementaçãoMostrar a implementação

PilhasPilhas:: Inserir o elemento do topo - :: Inserir o elemento do topo - push()push()

Mostrar a implementaçãoMostrar a implementação

PilhasPilhas:: Remover o elemento do topo - :: Remover o elemento do topo - pop()pop()

Mostrar a implementaçãoMostrar a implementação

PilhasPilhas:: Verificar se a pilha está vazia:: Verificar se a pilha está vazia

Mostrar a implementaçãoMostrar a implementação

PilhasPilhas:: Liberar a estrutura de pilha:: Liberar a estrutura de pilha

174

Mostrar a implementaçãoMostrar a implementação

QuestõesQuestões

FilasFilas

São São listas lineares listas lineares que adotam a política que adotam a política FIFOFIFO (First (First In First Out – o primeiro que entra é o primeiro que In First Out – o primeiro que entra é o primeiro que sai) para a manipulação de elementos.sai) para a manipulação de elementos.

As inserções são feitas no final da fila.As inserções são feitas no final da fila.

As remoções são feitas no início da fila.As remoções são feitas no início da fila.

A consulta na fila é feita desenfileirando elemento a A consulta na fila é feita desenfileirando elemento a elemento até encontrar o elemento desejado ou elemento até encontrar o elemento desejado ou chegar ao final da fila.chegar ao final da fila.

FilasFilas:: Aplicações:: Aplicações

Alocação de recursos para impressão de Alocação de recursos para impressão de documentos em uma impressora (impressão documentos em uma impressora (impressão de documentos).de documentos).

Atendimento de processos requisitados ao Atendimento de processos requisitados ao um sistema operacional(Software Básico).um sistema operacional(Software Básico).

Ordenação do encaminhamento dos pacotes Ordenação do encaminhamento dos pacotes em um roteador(redes de computadores).em um roteador(redes de computadores).

Buffer para gravação de dados em Buffer para gravação de dados em mídia(Computação Pessoal).mídia(Computação Pessoal).

FilasFilas:: Aplicações:: Aplicações

fila para pouso

fila para decolagem

Filas de tamanho variávelFilas de tamanho variável:: Inserção:: Inserção

B B

A A

X X

MM

K K

XX

MM

KK

A A

X X

MM

K K

AA

BB

Filas de tamanho variávelFilas de tamanho variável:: Remoção:: Remoção

B B

A A

X X

MM

K K

B B

A A

X X

B B

A A

X X

MM

kk

mm

Filas de tamanho fixoFilas de tamanho fixo

X X

MM

K K

A A

X X

MM

B B

A A

X X

AA KK

BB MM

FilasFilas:: Operações básicas:: Operações básicas

CriaçãoCriação

DestruiçãoDestruição

Inserção de um elementoInserção de um elemento

Remoção de um elementoRemoção de um elemento

Localização de um elemento para consulta ou Localização de um elemento para consulta ou alteração alteração

FilasFilas:: Criação de uma fila:: Criação de uma fila

typedef struct no TNo; struct no {    int info;    TNo* prox;};

typedef struct fila TFila; struct fila {    TNo* cabeca;    TNo* fim;    };

FilasFilas:: Inserção de um elemento:: Inserção de um elemento

Ver códigoVer código

FilasFilas:: Remoção de um elemento:: Remoção de um elemento

175

Ver códigoVer código