Listas, deques, pilhas e filas

Ligações sem perder nós

• Frente: cria o nó já com a ligação antiga, depois muda primeiro.
• Remoção: altera primeiro a ligação de entrada, depois liberta. A ligação pode ser primeiro ou anterior.seguinte.
• Ao apagar todos os iguais, revê a mesma ligação. Em [5,5,3], avançar logo perdia o segundo 5.
• Posição k pede 0<=k<tamanho. Achar a ligação custa $O(k+1)$; religar custa $O(1)$.

Dupla remove nó conhecido em $O(1)$ mas localiza por índice em $O(n)$. Circular com sentinela termina ao voltar à sentinela.

Cortar e juntar

• separar(resto,k) quer destino vazio e distinto. k<=0 leva tudo; k>=n leva nada. Corta com nulo e reparte tamanhos.
• Intercala ordenadas: escolhe a menor frente, esquerda no empate, e liga o resto quando uma acaba. Sem criar nós, auxiliar $O(1)$.
• Custo de pior caso $O(a+b)$ para entradas de tamanhos $a$ e $b$. Não é $\Theta$ por entrada: intercalar [1] com [2,\dots,n] faz uma comparação e depois liga o resto.

Pilha, fila e deque

Depois de 4, 7, 2	Sai primeiro	Resto
Pilha	2	7, 4
Fila	4	7, 2

Deque aceita ambas as extremidades. Array circular usa (inicio+i)%capacidade com tamanho guardado.

Duas pilhas fazem uma fila

entrada recebe; saida tem o mais antigo no topo.

1. Só transfere tudo quando saida está vazia.
2. Vazia nas duas significa fila vazia.

1. Entram 3 e 5
   entrada: 3, 5saída: vazia
   Retirar transfere e devolve 3.
2. Entra 8
   entrada: 8saída: 5
   Devolve 5 sem mexer em 8.
3. Esvazia saída
   entrada: vaziasaída: vazia
   Transfere 8. Ordem: 3, 5, 8.

Cada elemento muda de pilha uma vez por passagem. m operações custam $O(m)$: $O(1)$ amortizado.

Parênteses e próximos maiores

• Fecha só com topo correspondente e pilha não vazia. ([)] falha apesar das contagens.
• Próximo estritamente maior: guarda índices sem resposta por ordem não crescente. Cada índice entra e sai uma vez, logo $O(n)$.

Código e traços.