Estrutura de Dados.

Pilha

• É uma lista linear em que todas as inserções, retiradas e, geralmente, todos os acessos são feitos em apenas um extremo da lista.

• Os itens são colocados um sobre o outro. O item inserido mais recentemente está no topo e o inserido menos recentemente no fundo.

• O modelo intuitivo é o de um monte de pratos em uma prateleira, sendo conveniente retirar ou adicionar pratos na parte superior.

• Esta imagem está freqüentemente associada com a teoria de autômato, na qual o topo de uma pilha é considerado como o receptáculo de uma cabeça de leitura/gravação que pode empilhar e
desempilhar itens da pilha.


• Propriedade: o último item inserido é o primeiro item que pode ser retirado da lista. São chamadas listas lifo (“last-in, first-out”).

• Existe uma ordem linear para pilhas, do “mais recente para o menos recente”.

• É ideal para estruturas aninhadas de profundidade imprevisível.

• Uma pilha contém uma seqüência de obrigações adiadas. A ordem de remoção garante que as estruturas mais internas serão processadas antes das mais externas.


• As pilhas ocorrem em estruturas de natureza recursiva (como árvores). Elas são utilizadas para implementar a recursividade.


• Conjunto de operações:
1. FPVazia(Pilha). Faz a pilha ficar vazia.
2. Vazia(Pilha). Retorna true se a pilha está vazia; caso contrário,
retorna false.
3. Empilha(x, Pilha). Insere o item x no topo da pilha.
4. Desempilha(Pilha, x). Retorna o item x no topo da pilha, retirando-o
da pilha.
5. Tamanho(Pilha). Esta função retorna o número de itens da pilha.


• As duas representações mais utilizadas são as implementações por meio de arranjos e de apontadores.

Fila

• É uma lista linear em que todas as inserções são realizadas em um extremo da lista, e todas as retiradas e, geralmente, os acessos são realizados no outro extremo da lista.

• O modelo intuitivo de uma fila é o de uma fila de espera em que as pessoas no início da fila são servidas primeiro e as pessoas que chegam entram no fim da fila.

• São chamadas listas fifo (“first-in”, “first-out”).

• Existe uma ordem linear para filas que é a “ordem de chegada”.

• São utilizadas quando desejamos processar itens de acordo com a ordem “primeiro-que-chega, primeiro-atendido”.

• Sistemas operacionais utilizam filas para regular a ordem na qual tarefas devem receber processamento e recursos devem ser alocados a processos.


• Conjunto de operações:
1. FFVazia(Fila). Faz a fila ficar vazia.
2. Enfileira(x, Fila). Insere o item x no final da fila.
3. Desenfileira(Fila, x). Retorna o item x no início da fila, retirando-o
da fila.
4. Vazia(Fila). Esta função retorna true se a fila está vazia; senão
retorna false.


• Os itens são armazenados em posições contíguas de memória.

• A operação Enfileira faz a parte de trás da fila expandir-se.

• A operação Desenfileira faz a parte da frente da fila contrair-se.

• A fila tende a caminhar pela memória do computador, ocupando espaço na parte de trás e descartando espaço na parte da frente.

• Com poucas inserções e retiradas, a fila vai ao encontro do limite do espaço da memória alocado para ela.

• Solução: imaginar o array como um círculo. A primeira posição segue a última.


• As duas representações mais utilizadas são as implementações por meio de arranjos e de apontadores.