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:
- O que significa LIFO (Last In, First Out) – regra básica de pilha.
- 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:
– 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 vetorA
e um índicetop
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
– Vantagem: simples, acesso direto.
– Desvantagem: se você tentar empilhar mais de
Resumo das características:
– 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?
– 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 faztopo = novo_nó
. - pop(): retira o nó em
topo
, faztopo = topo→ponteiro_anter
.
Resposta
Os dois tipos básicos de pilha são:
- Pilha Estática (vetor de tamanho fixo)
- Pilha Dinâmica (lista encadeada, tamanho variável)