Implemente uma pilha utilizando uma lista ligada simples. As operações PUSH e POP devem ter complexidade temporal
.
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
.
Informações relevantes dadas pelo enunciado:
- Implementar uma pilha usando uma lista ligada simples.
- As operações PUSH e POP devem ser
. - 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
. - Algoritmo passo a passo para PUSH e POP (pseudocódigo).
- Implementações exemplo (Python e C) mostrando claramente como obter
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
nextque aponta para o próximo nó da lista (ou paraNULL/Nonese 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
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
já presentes. Ou seja, cada uma deve ser .
Passo 4
Escolha de representação concreta que garante
:
- Representar o topo da pilha como o início (head) da lista ligada simples.
- Por quê? Para inserir (push) no começo, basta:
- alocar um novo nó,
- apontar
new.nextpara oheadatual, - atualizar
head = new.
São 3 operações de ponteiro/atribuição — constante.
- Para remover (pop) do começo:
- guardar o valor de
head, - fazer
head = head.next, - liberar o nó antigo (em linguagens com free) ou deixá-lo para o garbage collector,
- retornar o valor guardado.
Também são poucas operações fixas — constante.
- guardar o valor de
- 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
. 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):
- criar um novo Node
new new.value = xnew.next = headhead = newsize = size + 1
Complexidade: cada passo é uma atribuição ou alocação; o número de passos não depende de. Logo .
POP():
- se
head == NULLentão a pilha está vazia -> sinalizar erro / retornar valor especial out = head.value// guardar o valor a ser retornadotmp = headhead = head.next- liberar memória de
tmp(ou deixar o GC cuidar) size = size - 1- retornar
out
Complexidade: número fixo de atribuições e um possível free; também.
PEEK()/TOP():
- se
head == NULLentão erro - retornar
head.value
Complexidade:.
IS_EMPTY():
- retornar
head == NULL(ousize == 0),.
Passo 6
Prova informal de que PUSH e POP são
:
- 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
. - Portanto o tempo não cresce com
; é constante, i.e. .
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.
Noneoufalsejunto 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.
- em linguagens com gerenciamento manual (C), é obrigatório
- 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):- criar nó A com value=10, next = NULL (head era NULL)
- head → A
- Executar
push(20):- criar nó B com value=20, next = head (aponta para A)
- head → B
- Executar
pop():- out = head.value = 20
- head = head.next (agora head → A)
- 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.
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