Quais os tipos de pilhas?

Passo 1

Beleza! A questão é “Quais os tipos de pilhas?”, num contexto de Estruturas de Dados. Vamos revisar o que é pilha (o conteúdo) e depois identificar as implementações que existem. Pra resolver isso, a gente vai precisar entender:
  1. O que significa LIFO (Last In, First Out) – regra básica de pilha.
  2. Como a pilha pode ser armazenada na memória: com tamanho fixo (vetor) ou variando de tamanho (lista).

Passo 2

Antes de falar dos tipos, bora lembrar o que é uma pilha.
– Pilha é uma estrutura de dados que segue LIFO: o último elemento que entrou é sempre o primeiro a sair.
– Operações principais:
  • push(x): empilha o elemento x no topo.
  • pop(): tira o elemento do topo.
  • top() ou peek(): vê, sem remover, o elemento que está no topo.
    Em pseudocódigo, se estivermos usando um vetor A e um índice top que aponta pra posição atual, teríamos algo como:
    push(x):
top ← top + 1  
A[top] ← x
pop():
retorno ← A[top]  
top ← top − 1  
return retorno

Passo 3

Tipo de pilha 1 – Pilha Estática
– Implementação: usa um vetor de tamanho fixo, digamos A[1..N].
– Vantagem: simples, acesso direto.
– Desvantagem: se você tentar empilhar mais de N elementos, dá estouro (overflow). Se você nunca encher, parte da memória fica perdida.
Resumo das características:
  • Complexidade das operações: O(1) para push e pop.
  • Tamanho máximo fixo definido em compilação ou na criação, por exemplo N = 100.

Passo 4

Tipo de pilha 2 – Pilha Dinâmica
– Implementação: usa lista encadeada (cada nó guarda um valor e o ponteiro pro “nó anterior”).
– Vantagem: cresce e diminui conforme a gente precisa, sem tamanho máximo pré-definido (exceto pela memória disponível).
– Desvantagem: ocupa mais memória por causa dos ponteiros; acesso indireto pode ser um pouco mais lento que vetor.
Como seria em linhas gerais?
  • Cada nó tem (valor, ponteiro_anter).
  • push(x): cria um novo nó onde ponteiro_anter = topo e faz topo = novo_nó.
  • pop(): retira o nó em topo, faz topo = topo→ponteiro_anter.

Resposta

Os dois tipos básicos de pilha são:
  1. Pilha Estática (vetor de tamanho fixo)
  2. Pilha Dinâmica (lista encadeada, tamanho variável)

Exercícios relacionados