Questão 751555

Uma lista ligada é uma estrutura de dados na qual os objetos estão organizados em ordem linear. Entretanto, diferentemente de um arranjo, no qual a ordem linear é determinada pelos índices do arranjo, a ordem em uma lista ligada é determinada por um ponteiro em cada objeto. Uma lista pode ter uma entre várias formas. Ela pode ser simplesmente ligada ou duplamente ligada, pode ser ordenada ou não e pode ser circular ou não.

Pilhas e filas são conjuntos dinâmicos nos quais o elemento removido do conjunto pela operação DELETE é especificado previamente e a ordem de remoção é determinada pela própria estrutura da pilha ou fila. Em uma pilha, o elemento eliminado do conjunto é o mais recentemente inserido: a pilha implementa uma política de último a entrar, primeiro a sair ou LIFO (last-in, first-out).

Designamos a operação INSERT em uma fila por ENQUEUE (ENFILEIRAR) e a operação DELETE por DEQUEUE (DESINFILEIRAR); assim como a operação em pilhas POP, DEQUEUE não adota nenhum argumento de elemento. A propriedade FIFO de uma fila faz com que ela funcione como uma fileira de pessoas em uma caixa registradora. A fila tem um início (ou cabeça) e um fim (ou cauda). Quando um elemento é inserido na fila, ocupa seu lugar no fim da fila, exatamente como um cliente que acabou de chegar ocupa um lugar no final da fileira.

Se uma lista é ordenada, a ordem linear da lista corresponde à ordem linear de chaves armazenadas em elementos da lista; então, o elemento mínimo é o fim da lista, e o elemento máximo é o início. Se a lista é não ordenada, os elementos podem aparecer em qualquer ordem. Em uma lista circular, o ponteiro posterior ao início da lista aponta para o fim, e o ponteiro anterior ao fim da lista aponta para o início. Podemos imaginar uma lista circular como um anel de elementos.