Implementação de duas pilhas em um único array
Gabarito: letra A. A estratégia clássica para implementar duas pilhas em um único array sem desperdício de espaço é posicionar a primeira pilha no início do array (crescendo para a direita) e a segunda no final (crescendo para a esquerda), utilizando dois ponteiros que se movem em direção um ao outro. Dessa forma, o transbordo só ocorre quando o total de elementos atinge n, e as operações PUSH e POP são executadas em O(1), pois envolvem apenas a manipulação dos ponteiros.
O problema exige que nenhuma pilha transborde a menos que o array esteja completamente cheio e que PUSH/POP sejam O(1). A abordagem de duas extremidades atende perfeitamente, sendo a solução mais eficiente e amplamente conhecida.
Estratégia | Descrição | Eficiência O(1) | Transbordo só quando array cheio | Correta? |
|---|
A | Dois ponteiros: um no início (pilha 1) e um no final (pilha 2), movendo-se um em direção ao outro | Sim (incremento/decremento de ponteiro) | Sim (ponteiros se cruzam apenas quando total = n) | ✅ Gabarito |
B | Um ponteiro no início para ambas as pilhas, com inserção na primeira e remoção na segunda | Não (exige deslocamento/reordenação) | Não (gerenciamento inviável) | ❌ |
C | Divisão do array em duas metades fixas; elementos movidos entre metades conforme necessário | Não (movimentação não é O(1)) | Não (desperdício de espaço) | ❌ |
D | Array circular com ambas as pilhas crescendo em direções opostas; insere na pilha com mais espaço | Sim (verificação O(1)) | Parcial (pode não usar todo o array sem lógica extra) | ❌ |
E | Metade esquerda para pilha 1, metade direita para pilha 2; tamanhos mudam dinamicamente | Não (exige realocação) | Não (desperdício ou realocação) | ❌ |
Alternativa A — ✅ Correta ⟵ GABARITO
Usa dois ponteiros: um no início (pilha 1) e um no final (pilha 2). As pilhas crescem uma em direção à outra. Enquanto os ponteiros não se cruzarem, há espaço disponível. O transbordo ocorre apenas quando o array está cheio. PUSH e POP são O(1) (apenas incremento/decremento do ponteiro e atribuição).
Alternativa B — ❌ Incorreta
Usar um único ponteiro no início para ambas as pilhas exigiria deslocamento de elementos ou reordenação constante, o que não é O(1). Além disso, não há como gerenciar duas pilhas independentes com um só ponteiro sem custos adicionais.
Alternativa C — ❌ Incorreta
Dividir o array em duas metades fixas causa desperdício de espaço: se uma pilha crescer além da metade, a outra pilha pode ter espaço ocioso, mas não é possível usar esse espaço sem mover elementos. Mover elementos entre metades não é O(1) e quebra a eficiência.
Alternativa D — ❌ Incorreta
Um array circular com ambas as pilhas crescendo em direções opostas é complexo e a regra de “inserir na pilha com mais espaço” exige verificação a cada PUSH, o que ainda é O(1), mas a abordagem não é a mais direta e pode levar a situações em que o array não é totalmente utilizado sem lógica adicional. A solução canônica é a da alternativa A.
Alternativa E — ❌ Incorreta
Semelhante à alternativa C, mas com “tamanhos que podem mudar dinamicamente”. Na prática, isso exigiria realocar ou mover elementos quando uma pilha invade a área da outra, o que não é O(1).
Gabarito: letra A