Please enable JavaScript.
Coggle requires JavaScript to display documents.
Estruturas Semelhantes a Listas - Coggle Diagram
Estruturas Semelhantes a Listas
Pilhas
É um tipo mais simples de lista na qual elementos só podem ser adicionados ou removidos por uma das extremidades.
Seguem o padrão LIFO (do inglês Last-In, First-Out), ou seja, podemos de fato associá-las a uma pilha de elementos nos quais, após empilhados, devemos retirar inicialmente os elementos mais do topo para que a estrutura permaneça em pé.
Definições
Top
element
Elemento mais ao topo da pilha, ou seja, aquele que está acessível no presente momento.
Push
Ação de inserir um elemento ao topo da pilha. Neste caso um elemento não é
inserted
, mas
pushed
Pop
Ação de retirar um elemento do topo da pilha. Neste caso um elemento não é
removed
, mas
popped
.
Pilhas baseadas em
arrays
Assim como nas listas baseadas em arrays, as pilhas também são inicializadas com um tamanho fixo.
Uma decisão importante a ser tomada é sobre qual extremidade do array será seu topo.
Método 01 (menos eficiente temporalmente):
definir o
top element
como a posição 0 do array, já que cada adição ou remoção deslocaria toda a lista a direita.
Método 02 (mais eficiente temporalmente):
definir o
top element
como a posição
(n -1)
do array - sendo
n
o número de elementos da pilha, assim toda adição ou remoção sempre terá o mesmo custo.
Pilhas baseadas em
listas
Possuem uma implementação bastante simplificada, onde todas as operações de inserção e remoção são realizadas com base no nó
top
da pilha (ou o que seria um nó
head
de listas).
Comparações
Operações de remoção e adição possuem o mesmo custo para ambos os tipos de implementação.
Relativo ao gasto de memória são semelhantes as listas, logo uma pilha demasiadamente extensa e com poucos elementos, baseada em uma implementação de array, pode ser mais custosa quando comparada a uma baseada em lista.
Filas
Assim como pilhas, as filas são um tipo de lista que promovem um acesso de maneira restrita aos elementos ali armazenados.
Filas seguem um padrão de armazenamento FIFO (do inglês First-In, First-Out), ou seja, podemos de fato associá-las as filas que observamos no dia a dia, nas quais aqueles que chegam primeiro são também os primeiros a serem atendidos.
Definições
enqueue
Operação de adição de um elemento na fila.
dequeue
Operação de remoção de um elemento da fila.
Assim como nas pilhas, os métodos de inserção e remoção obtém novas nomenclaturas. Porém de maneira distinta, nas filas os elementos sempre são adicionados ao final e removidos do começo.
Filas baseadas em
arrays
O primeiro ponto a notar é que a implementação de filas baseadas em arrays é um pouco complexa e pode não ser tão eficiente
A própria definião sobre em qual posição do array armazenar os elementos e qual será o final da fila possuem contrapontos:
Primeiro elemento do array sendo final da fila (pos. 0):
neste caso a operação de retirada torna-se bastante eficiente, porém para adicionar qualquer elemento na fila teremos que deslocar todos os elementos da fila 1 posição a direita no array.
Último elemento do array sendo o final da fila (pos. n - 1):
aqui a operação de adicionar elementos torna-se eficiente, mas a remoção é prejudicada já que precisariamos deslocar todos os elementos da fila 1 posição a esquerda do array.
Uma terceira opção seria utilizar
arrays circulares
onde removeriamos a propriedade de que os
n elementos
da fila precisam estar nas
n primeras
posições do array (de forma a agrupar essa fila numa posição mais central do array), assim ambas as operações de
enqueue
e
dequeue
seriam otimizadas, mas surge a problemática de ter de tornar um
"array circular"
para que posições disponíveis não sejam ignoradas em determinadas situações.
Filas baseadas em
listas
Filas baseadas em listas nada mais são do que uma adaptação das Listas Ligadas.
Neste caso, os métodos
front
e
rear
são ponteiros que apontarão para o início e o final da fila, respectivamente.
No início da fila, os ponteiros
front
e
rear
apontaram para o nó
header
da fila. Ao passo que elementos forem adicionados, o ponteiro de
rear
acompanhará o último elemento da fila enquanto o de
front
permanecerá sempre apontando para o nó
header
.
As operações de
enqueue
e
dequeue
sempre serão realizadas com base nos ponteiros de
rear
e
front
, respectivamente.