Implemente uma pilha utilizando uma lista ligada simples. As operações PUSH e POP devem ter complexidade temporal \mathrm{O}(1).

Passo 1

O enunciado pede: implementar uma pilha (estrutura LIFO — last in, first out) usando uma lista ligada simples de modo que as operações PUSH e POP tenham complexidade temporal \mathrm{O}(1).
Informações relevantes dadas pelo enunciado:
  • Implementar uma pilha usando uma lista ligada simples.
  • As operações PUSH e POP devem ser \mathrm{O}(1).
  • Não foi exigida uma linguagem específica, então a solução pode ser apresentada em pseudocódigo e em uma/duas linguagens de implementação para exemplificar.
O que será entregue:
  • Explicação didática do que é uma lista ligada simples e por que ela pode suportar push/pop em \mathrm{O}(1).
  • Algoritmo passo a passo para PUSH e POP (pseudocódigo).
  • Implementações exemplo (Python e C) mostrando claramente como obter \mathrm{O}(1) em PUSH e POP.
  • Tratamento de casos extremos (pilha vazia).

Passo 2

O que é uma lista ligada simples (no nível prático)?
  • Uma lista ligada simples é formada por nós (nodes). Cada nó contém:
    • um campo com o valor armazenado (por exemplo, um inteiro ou um ponteiro para um objeto),
    • um campo ponteiro chamado next que aponta para o próximo nó da lista (ou para NULL/None se não houver próximo).
  • A lista não tem armazenamento contíguo na memória; cada nó aponta para o próximo.
Estrutura conceitual de um nó (em palavras):
  • Node:
    • value — o dado guardado
    • next — referência para o próximo Node
Essa estrutura permite inserir ou remover um nó no começo da lista em um número fixo de operações sobre ponteiros — por isso essas operações são constantes em tempo.

Passo 3

O que é uma pilha (LIFO) e as operações que precisamos suportar:
  • Push(x): colocar o elemento x no topo da pilha.
  • Pop(): remover e retornar o elemento que está no topo da pilha.
  • (Opcional) Top/Peek(): ler o elemento do topo sem removê-lo.
  • isEmpty(): testar se a pilha está vazia.
Requisito de complexidade:
  • Queremos que Push e Pop façam um número constante de operações independente do número de elementos n já presentes. Ou seja, cada uma deve ser \mathrm{O}(1).

Passo 4

Escolha de representação concreta que garante \mathrm{O}(1):
  • Representar o topo da pilha como o início (head) da lista ligada simples.
  • Por quê? Para inserir (push) no começo, basta:
    1. alocar um novo nó,
    2. apontar new.next para o head atual,
    3. atualizar head = new.
      São 3 operações de ponteiro/atribuição — constante.
  • Para remover (pop) do começo:
    1. guardar o valor de head,
    2. fazer head = head.next,
    3. liberar o nó antigo (em linguagens com free) ou deixá-lo para o garbage collector,
    4. retornar o valor guardado.
      Também são poucas operações fixas — constante.
  • Se em vez do início usássemos o fim (tail) numa lista ligada simples sem ponteiro para o antecessor, push/pop exigiriam percorrer a lista ou ter ponteiro duplo, tornando as operações possivelmente \mathrm{O}(n). Por isso usar o início (head) é a escolha correta.

Passo 5

Pseudocódigo das estruturas e operações (passo a passo, bem mastigado):
Definição de Node:
  • Node:
    • value
    • next
Definição de Stack:
  • Stack:
    • head // referência para o nó do topo (início da lista)
    • size // (opcional) número de elementos
Inicialização:
  • criar Stack com head = NULL e size = 0
PUSH(x):
  1. criar um novo Node new
  2. new.value = x
  3. new.next = head
  4. head = new
  5. size = size + 1
    Complexidade: cada passo é uma atribuição ou alocação; o número de passos não depende de n. Logo \mathrm{O}(1).
POP():
  1. se head == NULL então a pilha está vazia -> sinalizar erro / retornar valor especial
  2. out = head.value // guardar o valor a ser retornado
  3. tmp = head
  4. head = head.next
  5. liberar memória de tmp (ou deixar o GC cuidar)
  6. size = size - 1
  7. retornar out
    Complexidade: número fixo de atribuições e um possível free; também \mathrm{O}(1).
PEEK()/TOP():
  1. se head == NULL então erro
  2. retornar head.value
    Complexidade: \mathrm{O}(1).
IS_EMPTY():
  • retornar head == NULL (ou size == 0), \mathrm{O}(1).

Passo 6

Prova informal de que PUSH e POP são \mathrm{O}(1):
  • Em cada operação apenas se realizam:
    • criação de um nó (alocação constante),
    • um número fixo de atribuições de ponteiro e variáveis,
    • possivelmente liberação de um nó.
  • Não há laços (loops) nem recursão que dependam de n.
  • Portanto o tempo não cresce com n; é constante, i.e. \mathrm{O}(1).

Passo 7

Casos extremos e detalhes práticos (importante para a prova):
  • POP em pilha vazia: escolha de comportamento possível:
    • lançar uma exceção / erro,
    • retornar um valor especial (por ex. None ou false junto com saída),
    • documentar bem o contrato da função.
  • Gerenciamento de memória:
    • em linguagens com gerenciamento manual (C), é obrigatório free/free() ao remover nó para evitar vazamento de memória.
    • em Python/Java, o garbage collector cuida, mas é bom remover referências.
  • Tipo genérico: a implementação pode usar um tipo genérico para os valores (templates, void* em C, generics em Java, etc.), aqui os exemplos usarão tipos simples (ex.: int) para clareza.

Passo 8

Exemplo passo a passo (pequeno) para fixar:
  • Começo: pilha vazia, head = NULL.
  • Executar push(10):
    1. criar nó A com value=10, next = NULL (head era NULL)
    2. head → A
  • Executar push(20):
    1. criar nó B com value=20, next = head (aponta para A)
    2. head → B
  • Executar pop():
    1. out = head.value = 20
    2. head = head.next (agora head → A)
    3. retorna 20
      Resultado: sequência de retornos segue LIFO: últimos inseridos são os primeiros removidos.

Passo 9

Implementações de exemplo
  • Abaixo são apresentadas duas implementações simples e claras: uma em Python (mais curta, para entender o fluxo) e outra em C (mostrando alocação/liberação explícita). Ambas usam o início da lista (head) como topo da pilha, garantindo que PUSH e POP sejam \mathrm{O}(1).

Resposta

Implementação em Python:
class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

class Stack:
    def __init__(self):
        self.head = None
        self.size = 0

    def is_empty(self):
        return self.head is None

    def push(self, value):
        # Cria um novo nó cujo next aponta para o head atual
        new_node = Node(value, self.head)
        # Atualiza o head para o novo nó
        self.head = new_node
        self.size += 1

    def pop(self):
        if self.head is None:
            raise IndexError("pop from empty stack")
        # Guarda o valor do topo
        value = self.head.value
        # Remove o nó do topo apontando head para o próximo
        self.head = self.head.next
        self.size -= 1
        return value

    def peek(self):
        if self.head is None:
            raise IndexError("peek from empty stack")
        return self.head.value
Implementação em C (valores do tipo int):
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int value;
    struct Node* next;
} Node;

typedef struct Stack {
    Node* head;
    int size;
} Stack;

Stack* stack_create(void) {
    Stack* s = malloc(sizeof(Stack));
    if (!s) exit(EXIT_FAILURE);
    s->head = NULL;
    s->size = 0;
    return s;
}

bool stack_is_empty(Stack* s) {
    return s->head == NULL;
}

void stack_push(Stack* s, int value) {
    Node* node = malloc(sizeof(Node));
    if (!node) exit(EXIT_FAILURE);
    node->value = value;
    node->next = s->head;
    s->head = node;
    s->size++;
}

bool stack_pop(Stack* s, int* out) {
    if (s->head == NULL) return false; // pilha vazia
    Node* node = s->head;
    *out = node->value;
    s->head = node->next;
    free(node);
    s->size--;
    return true;
}

void stack_free(Stack* s) {
    while (s->head != NULL) {
        Node* tmp = s->head;
        s->head = s->head->next;
        free(tmp);
    }
    free(s);
}
Observação final: ambos os exemplos usam inserção e remoção no início da lista ligada (campo head), garantindo que push e pop sejam executados em tempo constante \mathrm{O}(1).

Exercícios relacionados