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
, tal que não haja overflow enquanto o total de elementos nas duas pilhas for
, e com operações de push e pop em
. O conteúdo principal é estrutura de dados (pilha) e gerenciamento de índices.
Passo 2
Vamos representar as duas pilhas num array chamado
. Usaremos dois índices:
-
aponta para o topo da pilha 1 e cresce da esquerda para a direita. -
aponta para o topo da pilha 2 e cresce da direita para a esquerda.
Passo 3
Inicialização:
Isso faz com que, inicialmente, a pilha 1 esteja “vazia” à esquerda e a pilha 2 “vazia” à direita.
Passo 4
Operação push1
(empilha em pilha 1):
Se então
overflow (não há espaço)
Senão
Se
overflow (não há espaço)
Senão
Passo 5
Operação push2
(empilha em pilha 2):
Se então
overflow
Senão
Se
overflow
Senão
Passo 6
Operação pop1() (desempilha de pilha 1):
Se então
underflow (pilha 1 vazia)
Senão
retorne
Se
underflow (pilha 1 vazia)
Senão
retorne
Passo 7
Operação pop2() (desempilha de pilha 2):
Se então
underflow (pilha 2 vazia)
Senão
retorne
Se
underflow (pilha 2 vazia)
Senão
retorne
Resposta
Implementamos duas pilhas em um único array de tamanho
usando dois índices
e
que crescem em direções opostas. As operações de push e pop têm complexidade
e garantem que não ocorra overflow enquanto
.