Implemente duas pilhas usando um mesmo array (estrutura compartilhada) de tamanho n de forma que o overflow não acontece enquanto o número de elementos das duas pilhas juntas não ultrapassar n. As operações de push e pop devem ter complexidade O(1) .

Passo 1

O enunciado pede uma estrutura de duas pilhas que compartilhem um único array de tamanho n, tal que não haja overflow enquanto o total de elementos nas duas pilhas for \le n, e com operações de push e pop em O(1). O conteúdo principal é estrutura de dados (pilha) e gerenciamento de índices.

Passo 2

Vamos representar as duas pilhas num array chamado \text{arr}[0\ldots n-1]. Usaremos dois índices:
  • \text{top1} aponta para o topo da pilha 1 e cresce da esquerda para a direita.
  • \text{top2} aponta para o topo da pilha 2 e cresce da direita para a esquerda.

Passo 3

Inicialização: \text{top1} \leftarrow -1 \text{top2} \leftarrow n Isso faz com que, inicialmente, a pilha 1 esteja “vazia” à esquerda e a pilha 2 “vazia” à direita.

Passo 4

Operação push1 x (empilha em pilha 1):
Se \text{top1} + 1 = \text{top2} então
overflow (não há espaço)
Senão
\text{top1} \leftarrow \text{top1} + 1 \text{arr}[\text{top1}] \leftarrow x

Passo 5

Operação push2 x (empilha em pilha 2):
Se \text{top1} = \text{top2} - 1 então
overflow
Senão
\text{top2} \leftarrow \text{top2} - 1 \text{arr}[\text{top2}] \leftarrow x

Passo 6

Operação pop1() (desempilha de pilha 1):
Se \text{top1} = -1 então
underflow (pilha 1 vazia)
Senão
v \leftarrow \text{arr}[\text{top1}] \text{top1} \leftarrow \text{top1} - 1
retorne v

Passo 7

Operação pop2() (desempilha de pilha 2):
Se \text{top2} = n então
underflow (pilha 2 vazia)
Senão
v \leftarrow \text{arr}[\text{top2}] \text{top2} \leftarrow \text{top2} + 1
retorne v

Resposta

Implementamos duas pilhas em um único array de tamanho n usando dois índices \text{top1} e \text{top2} que crescem em direções opostas. As operações de push e pop têm complexidade O(1) e garantem que não ocorra overflow enquanto \#\text{elementos}_1 + \#\text{elementos}_2 \le n.

Exercícios relacionados