Suponha que um dado problema requer o uso de duas pilhas, onde cada pilha suporta no máximo 50 elementos e em nenhum momento as duas pilhas terão juntas mais do que 80 elementos. Assim, é possível implementar as duas pilhas em um único vetor usando apenas 80 posições ao invés de 100 . Implemente a estrutura de dados e as funções de empilhar e desempilhar para estas duas pilhas.
Passo 1
O que o enunciado pede e quais são os dados importantes:
- Pede para implementar duas pilhas (operadores empilhar e desempilhar) usando um único vetor.
- Cada pilha pode ter no máximo
elementos (limite por pilha). - Em nenhum momento as duas pilhas juntas terão mais do que
elementos (limite combinado). - Objetivo: usar apenas
posições no vetor (em vez de ) e implementar as operações básicas das duas pilhas.
Resumo das perguntas que precisamos responder:
- Como organizar a memória (estruturas) para suportar as duas pilhas em um único vetor de
posições? - Como implementar as funções de empilhar (push) e desempilhar (pop) para cada pilha, incluindo checagens de erro (overflow/underflow)?
- Garantir que as operações sejam eficientes (tempo constante) e que os limites por pilha e combinados sejam respeitados.
Passo 2
Conceito básico e ideia de solução (explicação didática e intuitiva)
-
O que é uma pilha?
Uma pilha é uma estrutura LIFO (last in, first out): o último elemento inserido é o primeiro a sair. As duas operações básicas são:- empilhar (push): inserir um elemento no topo;
- desempilhar (pop): remover e retornar o elemento no topo.
-
Como normalmente se implementa uma pilha numa array?
Usa-se um índice que aponta para o topo. Por exemplo, para uma pilha que cresce da esquerda para a direita, o topo inicial é(vazia) e ao empilhar incrementa-se o índice e grava-se o valor no vetor. -
Ideia para duas pilhas num mesmo vetor de
posições: pilhas crescendo de extremos opostos. - A pilha 1 cresce da esquerda para a direita (começando em índice inicial
e avançando para ). - A pilha 2 cresce da direita para a esquerda (começando em índice inicial
e avançando para ).
Assim, as pilhas usam o espaço livre do meio de forma dinâmica: se uma cresce muito, a outra só fica com o restante espaço. Mantemos a condição invariantes:
ondeé índice do topo da pilha 1 e é índice do topo da pilha 2 (com convenção de vazio: , ). - A pilha 1 cresce da esquerda para a direita (começando em índice inicial
-
Por que
posições bastam?
O enunciado garante que, e . Logo, o número total de elementos nunca excederá , portanto um vetor de posições tem espaço suficiente para armazenar ambos os conjuntos de elementos sob essa restrição combinada.
Passo 3
Invariantes e checagens que precisamos implementar (regras concretas)
-
Variáveis a manter:
- vetor de armazenamento com
posições; -
: índice do topo da pilha 1 (inicialmente ); -
: índice do topo da pilha 2 (inicialmente ); - opcionalmente
e para rastrear o número de elementos em cada pilha (pode-se derivar esses contadores dos topes, mas guardar facilita checar o limite por pilha).
- vetor de armazenamento com
-
Condições de erro (quando não é possível empilhar):
- overflow por limite individual: se
ao tentar empilhar na pilha 1, rejeitar (mesmo se houver espaço combinadamente). - overflow por espaço compartilhado: se
(ou ), o vetor está cheio: rejeitar. - análogo para a pilha 2: se
rejeitar; se rejeitar.
- overflow por limite individual: se
-
Condições de desempilhar:
- underflow: se
para a pilha , não há elemento para desempilhar.
- underflow: se
-
Operações atômicas (complexidade):
- Todas as operações (push/pop) serão
— apenas atualização de índices e leitura/escrita do vetor.
- Todas as operações (push/pop) serão
Passo 4
Passo a passo de cada operação (explicação detalhada para saber o que fazer na prova)
-
Inicialização:
-
. -
. -
. -
. -
.
-
-
Empilhar na pilha 1 (push1 de um valor
): - Verificar o limite individual: se
então erro de overflow por limite da pilha 1. - Verificar espaço compartilhado: se
então erro de overflow por vetor cheio. - Caso ok: incrementar
. - Armazenar
. - Incrementar
. - Retornar sucesso.
- Verificar o limite individual: se
-
Desempilhar da pilha 1 (pop1):
- Verificar underflow: se
então erro (pilha vazia). - Ler
. - Decrementar
. - Decrementar
. - Retornar
.
- Verificar underflow: se
-
Empilhar na pilha 2 (push2 de
): - Verificar o limite individual: se
então erro de overflow por limite da pilha 2. - Verificar espaço compartilhado: se
então erro de overflow por vetor cheio. - Caso ok: decrementar
. - Armazenar
. - Incrementar
. - Retornar sucesso.
- Verificar o limite individual: se
-
Desempilhar da pilha 2 (pop2):
- Verificar underflow: se
então erro (pilha vazia). - Ler
. - Incrementar
. - Decrementar
. - Retornar
.
- Verificar underflow: se
Observações práticas:
- Os cheques de
e são equivalentes; basta checar uma forma (por exemplo ) para detectar que o array não tem mais posições livres. - Guardar
e permite verificar rapidamente o limite individual de . Alternativamente, pode-se calcular e , mas manter contadores explicita a intenção.
Passo 5
Exemplo rápido (simular mentalmente para fixar o método)
-
Estado inicial:
-
, , , .
-
-
Empilhar 3 elementos na pilha 1: cada push1 faz
passar para e ir para . Os elementos ocupam . -
Empilhar 2 elementos na pilha 2: cada push2 faz
passar para e ir para . Os elementos ocupam . -
Se agora tentarmos empilhar até que
, significa que não há mais células livres. -
Em qualquer momento, antes de empilhar na pilha 1, checar se
. Mesmo que o vetor ainda tenha espaço físico, não é permitido exceder na pilha individual.
Passo 6
Detalhes de implementação e considerações práticas (para a prova ou código real)
- É uma boa prática retornar códigos de erro nas operações (por exemplo:
= sucesso, = pilha vazia, = overflow por limite individual, = overflow por falta de espaço conjunto), ou lançar exceção conforme a linguagem. - Tempo das operações:
(constante), porque só se faz um teste e atualizações de índices. - Uso de memória: exatamente
posições mais algumas variáveis inteiras para índices/contadores. - Testes que você pode fazer na prova: tente uma sequência que leva uma pilha ao limite de
enquanto a outra tem alguns elementos, para verificar que o código bloqueia corretamente por limite individual; e tente encher o vetor a ponto de para ver o overflow compartilhado.
Resposta
/* Implementação em C de duas pilhas compartilhando um único vetor de N = 80 posições.
Cada pilha admite no máximo M = 50 elementos. */
#include <stdio.h>
#define N 80 /* tamanho do vetor compartilhado */
#define M 50 /* limite por pilha */
typedef struct {
int arr[N];
int top1; /* índice do topo da pilha 1; -1 quando vazia */
int top2; /* índice do topo da pilha 2; N quando vazia */
int count1; /* número de elementos na pilha 1 */
int count2; /* número de elementos na pilha 2 */
} TwoStacks;
/* Inicializa a estrutura */
void initTwoStacks(TwoStacks *s) {
s->top1 = -1;
s->top2 = N;
s->count1 = 0;
s->count2 = 0;
}
/* Códigos de retorno padrão:
0 = sucesso
-1 = underflow (pilha vazia)
-2 = overflow por limite individual (>= M)
-3 = overflow por falta de espaço compartilhado (arr cheio)
*/
/* Empilha x na pilha 1 */
int push1(TwoStacks *s, int x) {
if (s->count1 == M) return -2; /* limite individual atingido */
if (s->top1 + 1 == s->top2) return -3; /* sem espaço no vetor */
s->top1 += 1;
s->arr[s->top1] = x;
s->count1 += 1;
return 0;
}
/* Empilha x na pilha 2 */
int push2(TwoStacks *s, int x) {
if (s->count2 == M) return -2; /* limite individual atingido */
if (s->top2 - 1 == s->top1) return -3; /* sem espaço no vetor */
s->top2 -= 1;
s->arr[s->top2] = x;
s->count2 += 1;
return 0;
}
/* Desempilha da pilha 1; elemento removido é colocado em *out */
int pop1(TwoStacks *s, int *out) {
if (s->count1 == 0) return -1; /* pilha 1 vazia */
*out = s->arr[s->top1];
s->top1 -= 1;
s->count1 -= 1;
return 0;
}
/* Desempilha da pilha 2; elemento removido é colocado em *out */
int pop2(TwoStacks *s, int *out) {
if (s->count2 == 0) return -1; /* pilha 2 vazia */
*out = s->arr[s->top2];
s->top2 += 1;
s->count2 -= 1;
return 0;
}
/* Funções utilitárias opcionais */
int isEmpty1(TwoStacks *s) { return s->count1 == 0; }
int isEmpty2(TwoStacks *s) { return s->count2 == 0; }
int size1(TwoStacks *s) { return s->count1; }
int size2(TwoStacks *s) { return s->count2; }
/* Exemplo de uso (não obrigatório):
int main() {
TwoStacks s;
initTwoStacks(&s);
push1(&s, 10);
push2(&s, 20);
int v;
pop1(&s, &v); printf("pop1: %d\n", v);
pop2(&s, &v); printf("pop2: %d\n", v);
return 0;
}
*/