Pilha e fila

Filas

Uma Fila é uma estrutura de dados do tipo FIFO (First In First Out), cujo funcionamento é inspirado no de uma fila “natural”, na qual o primeiro elemento a ser inserido é sempre o primeiro elemento a ser retirado. Um exemplo de uma fila é o caso de uma “fila de supermercado”.

A implementação de uma fila como um “tipo abstrato de dados”, permite a definição abstratas dos aspectos essenciais de comportamento e funcionamento de um objeto sem definição de qualquer aspecto de implementação. Uma fila tem por norma as seguintes funcionalidades:
Colocar e retirar dados da fila. add – guardar um elemento na fila remove – retirar um elemento da fil top – retornar o elemento do topo da fila
Testar se a fila está vazia ou cheia. full – Verificar se a fila está cheia (não pode guardar mais elementos). empty – Verificar se a fila está vazia (não contém elementos)
Inicializar ou limpar: construct – Colocar a fila num estado “pronto” a ser utilizada A implementação de uma fila pode ser efeituada através da utilização de diferentes estruturas de dados (vectores, listas ligadas, árvores, etc.). De seguida, apresenta-se duas implementação de uma fila através da utilização de vectores e listas ligadas.
Características das filas:
Os dados são armazenados pela ordem de entrada
Tipos de filas:
Filas de espera (aqueles) com duplo fim (deque “double-ended aquele)
Filas de espera com prioridades (priority queues)

Implementação das filas: usando vectores / arrays (circulares ou não) utilizando um apontador para nós de informação (lista ligada)

Pilhas

O funcionamento de uma pilha consiste numa estratégia chamada LIFO (last in, first out – último a entrar, primeiro a sair). Além disso, o único elemento que se pode acessar na pilha é o elemento do topo da mesma, ou seja, o último a ser empilhado. Pense numa pilha de pratos. Quando se vai lavá-los, você não começa retirando o que está mais abaixo, e sim o que está no topo da pilha. É basicamente assim