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 50 elementos (limite por pilha).
  • Em nenhum momento as duas pilhas juntas terão mais do que 80 elementos (limite combinado).
  • Objetivo: usar apenas 80 posições no vetor (em vez de 100) 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 80 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 é -1 (vazia) e ao empilhar incrementa-se o índice e grava-se o valor no vetor.
  • Ideia para duas pilhas num mesmo vetor de 80 posições: pilhas crescendo de extremos opostos.
    • A pilha 1 cresce da esquerda para a direita (começando em índice inicial -1 e avançando para 0,1,2,\dots).
    • A pilha 2 cresce da direita para a esquerda (começando em índice inicial 80 e avançando para 79,78,\dots).
      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:
    top_1 < top_2
    onde top_1 é índice do topo da pilha 1 e top_2 é índice do topo da pilha 2 (com convenção de vazio: top_1=-1, top_2=80).
  • Por que 80 posições bastam?
    O enunciado garante que \text{tamanho}_1 \le 50, \text{tamanho}_2 \le 50 e \text{tamanho}_1 + \text{tamanho}_2 \le 80. Logo, o número total de elementos nunca excederá 80, portanto um vetor de 80 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 N=80 posições;
    • top_1: índice do topo da pilha 1 (inicialmente -1);
    • top_2: índice do topo da pilha 2 (inicialmente N);
    • opcionalmente count_1 e count_2 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).
  • Condições de erro (quando não é possível empilhar):
    • overflow por limite individual: se count_1 = 50 ao tentar empilhar na pilha 1, rejeitar (mesmo se houver espaço combinadamente).
    • overflow por espaço compartilhado: se top_1 + 1 = top_2 (ou top_2 - 1 = top_1), o vetor está cheio: rejeitar.
    • análogo para a pilha 2: se count_2 = 50 rejeitar; se top_2 - 1 = top_1 rejeitar.
  • Condições de desempilhar:
    • underflow: se count_i = 0 para a pilha i, não há elemento para desempilhar.
  • Operações atômicas (complexidade):
    • Todas as operações (push/pop) serão O(1) — apenas atualização de índices e leitura/escrita do vetor.

Passo 4

Passo a passo de cada operação (explicação detalhada para saber o que fazer na prova)
  • Inicialização:
    • N=80.
    • top_1 \leftarrow -1.
    • top_2 \leftarrow N.
    • count_1 \leftarrow 0.
    • count_2 \leftarrow 0.
  • Empilhar na pilha 1 (push1 de um valor x):
    1. Verificar o limite individual: se count_1 = 50 então erro de overflow por limite da pilha 1.
    2. Verificar espaço compartilhado: se top_1 + 1 = top_2 então erro de overflow por vetor cheio.
    3. Caso ok: incrementar top_1 \leftarrow top_1 + 1.
    4. Armazenar arr[top_1] \leftarrow x.
    5. Incrementar count_1 \leftarrow count_1 + 1.
    6. Retornar sucesso.
  • Desempilhar da pilha 1 (pop1):
    1. Verificar underflow: se count_1 = 0 então erro (pilha vazia).
    2. Ler x \leftarrow arr[top_1].
    3. Decrementar top_1 \leftarrow top_1 - 1.
    4. Decrementar count_1 \leftarrow count_1 - 1.
    5. Retornar x.
  • Empilhar na pilha 2 (push2 de x):
    1. Verificar o limite individual: se count_2 = 50 então erro de overflow por limite da pilha 2.
    2. Verificar espaço compartilhado: se top_2 - 1 = top_1 então erro de overflow por vetor cheio.
    3. Caso ok: decrementar top_2 \leftarrow top_2 - 1.
    4. Armazenar arr[top_2] \leftarrow x.
    5. Incrementar count_2 \leftarrow count_2 + 1.
    6. Retornar sucesso.
  • Desempilhar da pilha 2 (pop2):
    1. Verificar underflow: se count_2 = 0 então erro (pilha vazia).
    2. Ler x \leftarrow arr[top_2].
    3. Incrementar top_2 \leftarrow top_2 + 1.
    4. Decrementar count_2 \leftarrow count_2 - 1.
    5. Retornar x.
Observações práticas:
  • Os cheques de top_1 + 1 = top_2 e top_2 - 1 = top_1 são equivalentes; basta checar uma forma (por exemplo top_1 + 1 = top_2) para detectar que o array não tem mais posições livres.
  • Guardar count_1 e count_2 permite verificar rapidamente o limite individual de 50. Alternativamente, pode-se calcular count_1 = top_1 + 1 e count_2 = N - top_2, mas manter contadores explicita a intenção.

Passo 5

Exemplo rápido (simular mentalmente para fixar o método)
  • Estado inicial:
    • top_1=-1, top_2=80, count_1=0, count_2=0.
  • Empilhar 3 elementos na pilha 1: cada push1 faz top_1 passar para 0,1,2 e count_1 ir para 1,2,3. Os elementos ocupam arr[0],arr[1],arr[2].
  • Empilhar 2 elementos na pilha 2: cada push2 faz top_2 passar para 79,78 e count_2 ir para 1,2. Os elementos ocupam arr[79],arr[78].
  • Se agora tentarmos empilhar até que top_1 + 1 = top_2, significa que não há mais células livres.
  • Em qualquer momento, antes de empilhar na pilha 1, checar se count_1 = 50. Mesmo que o vetor ainda tenha espaço físico, não é permitido exceder 50 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: 0 = sucesso, -1 = pilha vazia, -2 = overflow por limite individual, -3 = overflow por falta de espaço conjunto), ou lançar exceção conforme a linguagem.
  • Tempo das operações: O(1) (constante), porque só se faz um teste e atualizações de índices.
  • Uso de memória: exatamente N=80 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 50 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 top_1+1=top_2 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;
}
*/

Exercícios relacionados