Pilhas e filas: por que o Swift não tem um tipo Stack

Ao começar a estudar estruturas de dados, os dois primeiros irmãos que você encontra são a pilha (Stack) e a fila (Queue).

Os conceitos levam cinco minutos. Mas, no Swift, surge uma dúvida: a biblioteca padrão tem Array, Dictionary e Set, mas não tem os tipos Stack nem Queue. Este artigo explica por quê e como trabalhar sem eles.

A armadilha de desempenho (removeFirst()) ao imitar filas com arrays causa muitos timeouts em desafios de programação, por isso será tratada separadamente.

A pilha deste artigo é uma estrutura de dados, não uma área de alocação de memória. A diferença entre os nomes aparece em Pilha de memória vs. heap; a próxima etapa, filas com prioridade, está em Heap e fila de prioridade.

---

O conceito se resume a pratos e uma fila

Uma pilha é LIFO (Last In, First Out). O último item inserido sai primeiro. Pense em uma pilha de pratos: push no topo e pop pelo topo. Remover pelo meio quebra a regra.

Uma fila é FIFO (First In, First Out). O primeiro item inserido sai primeiro. É como uma fila no caixa: enqueue atrás e dequeue na frente.

Cada uma tem apenas duas operações.

	Inserir	Remover	Consultar
Pilha	push	pop	peek(top)
Fila	enqueue	dequeue	front

Por que isso importa? Porque essa regra simples sustenta várias partes do desenvolvimento iOS.

• Pilha de chamadas: chamadas e retornos de funções são exatamente push/pop. Quando a recursão se aprofunda, o crash se chama stack overflow por um motivo.
• UINavigationController: pushViewController / popViewController — transições de tela são literalmente uma pilha.
• Desfazer (undo): comandos são empilhados e revertidos na ordem inversa.
• DispatchQueue do GCD (Grand Central Dispatch): como o nome indica, é uma fila. Tarefas em uma serial queue executam na ordem de inserção.
• BFS/DFS: em grafos, usar uma fila resulta em BFS (Breadth-First Search, busca em largura); usar uma pilha resulta em DFS (Depth-First Search, busca em profundidade). Escolher a estrutura é escolher o algoritmo.

---

Por que o Swift não tem Stack

A resposta curta: Array já é uma pilha perfeita.

var stack: [Int] = []
stack.append(3)      // push — O(1)
stack.append(7)
let top = stack.last // peek — O(1)
let popped = stack.popLast() // pop — O(1), Se estiver vazio nil

Inserir e remover no fim de um array custa O(1); mais precisamente, amortized O(1), pois a expansão só custa quando o buffer interno enche. Um tipo separado apenas envolveria Array, então a biblioteca padrão decidiu não adicioná-lo.

Se quiser deixar a intenção explícita, uma camada fina é o padrão.

struct Stack<Element> {
    private var storage: [Element] = []
    var isEmpty: Bool { storage.isEmpty }
    var top: Element? { storage.last }
    mutating func push(_ element: Element) { storage.append(element) }
    mutating func pop() -> Element? { storage.popLast() }
}

Isso bloqueia subscript e força pelo tipo a regra da pilha: “proibido acessar o meio”.

---

Criar uma fila com array é uma armadilha

Uma fila criada com a mesma lógica de uma pilha fica assim.

var queue: [Int] = []
queue.append(1)              // enqueue — O(1), Sem problema
let first = queue.removeFirst() // dequeue — O(n), Aqui está a armadilha

removeFirst() remove o primeiro elemento e ** desloca todos os demais uma posição para a frente.** Com 100 mil elementos, um dequeue causa 100 mil movimentações. Repetir isso milhares de vezes, como no BFS, torna tudo O(n²) e causa timeout em desafios de programação.

Há três soluções.

1. Avançar o início por índice (o padrão em desafios)

var queue: [Int] = []
var head = 0
// enqueue
queue.append(5)
// dequeue
let value = queue[head]
head += 1

Em vez de remover, mova apenas a posição de leitura. dequeue vira O(1); a memória do início usado permanece, mas isso quase sempre basta em desafios.

2. Criar uma fila com duas pilhas (clássico de entrevistas)

Ao inserir, empilhe em in. Ao remover, se out estiver vazio, transfira todo o conteúdo de in invertido e faça pop. Cada elemento se move no máximo duas vezes, resultando em amortized O(1). Essa também é a resposta padrão para “implemente uma fila com pilhas”.

3. Deque do swift-collections (a resposta para produção)

O pacoteswift-collections mantido pela Apple oferece Deque, baseado em buffer circular; portanto, inserções e remoções nas duas extremidades custam O(1).

import DequeModule

var queue: Deque<Int> = []
queue.append(1)            // enqueue
let v = queue.popFirst()   // dequeue — O(1)

A API é quase igual à do Array, então a troca custa pouco. Em produção, use isso quando precisar de uma fila.

---

Como decidir qual usar

Quando houver dúvida, faça uma pergunta: “Devo processar primeiro o que chegou por último ou o que chegou primeiro?”

• Desfazer, validar parênteses, retroceder por caminhos visitados e busca em profundidade → mais recente primeiro → pilha
• Fila de tarefas, processamento de eventos, saída da impressora e busca em largura → ordem de chegada → fila

Validar parênteses é um uso clássico de pilhas: faça push ao encontrar um parêntese de abertura, pop ao encontrar um de fechamento e confirme o par. Se a pilha estiver vazia no fim, a expressão é válida. Compiladores verificam chaves pelo mesmo princípio.

---

Resumo

• Pilha é LIFO; fila é FIFO — pratos e fila de caixa explicam todo o conceito.
• Pilha de chamadas, pilha de navegação e undo são pilhas; DispatchQueue, processamento de eventos e BFS são filas. Elas já estão espalhadas pelo desenvolvimento iOS.
• O Swift não tem Stack porque append/popLast do Array já formam uma pilha O(1).
• Ao criar uma fila com array, removeFirst() custa O(n) — uma causa comum de timeout em desafios.
• As soluções são um índice head, duas pilhas ou, em produção, o Deque do swift-collections.
• Escolher pilha ou fila depende de uma pergunta: priorizar o mais recente ou a ordem de chegada?

No próximo artigo, continuaremos com suas aplicações: heap e fila de prioridade, além da tabela hash por trás de Dictionary.