informática

ESTRUTURAS DE DADOS
UNIDADE II – PILHAS E
FILAS
Curso: Bacharelado em Ciência da
Computação.
Prof. MsC. Dário Russillo. email: [e-mail]

2.1

INTRODUÇÃO



Em algumas aplicações é imposto um critério que restringe a INSERÇÃO e REMOÇÃO de elementos (nós) que compõem um conjunto de dados (listas).



O critério escolhido impõe uma ordem ao conjunto de dados.



Os dois critérios mais utilizados são:
LIFO (“Last In First Out): o primeiro nó a ser retirado é o último que tiver sido inserido.
Ex: pilha vertical de pratos.



FIFO (“First In First Out”): o primeiro nó a ser retirado é o primeiro que tiver sido inserido.
Ex: funcionamento de uma fila de pessoas.



2.1 Introdução


As estruturas lineares com disciplina de acesso são: 




Pilhas (stacks) usa o critério LIFO
Filas (queue)  usa o critério FIFO

Estas estruturas dinâmicas podem utilizar o armazenamento: Sequencial, pois a INSERÇÃO/REMOÇÃO são realizados somente nas extremidades da lista, sem a necessidade de movimentar os nós.
 Encadeado, que utilizar indicadores especiais denominados ponteiros. 



Para as pilhas, apenas um ponteiro precisa ser considerado, pois as duas operações são realizadas na mesma extremidade. 2.1 Introdução


Outra operação (além da remoção e inserção) realizada em pilhas e filas é a operação de CONSULTA.

Algumas aplicações práticas:
 Pilhas
Desfazer de editor de texto.
 Histórico de páginas em browser.
 Acesso a última ligação efetuada pelo celular.




Filas
Fila de espera de documentos a serem impressos.
 Fila do lote de restituição de imposto de renda da receita federal.  Serviços (“jobs”) submetidos e lidos pelos sistemas operacionais são colocados em uma fila de espera para serem executados (na ordem em que entraram).


2.2 PILHAS


Definição:
É um tipo especial de lista linear em que todas as operações de inserção e remoção são realizadas
numa