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.
Comentários
Postar um comentário