Pilhas
O que é um ADT?
- Um Abstract Data Type (ADT) é uma coleção de dados mais um conjunto de operações sobre ela.
- Você usa as operações e ignora como é construído internamente.
- Uma stack, uma queue e uma linked list são todos ADTs.
Uma stack é LIFO
- Uma stack é Last In, First Out (LIFO).
- O último item que você adiciona é o primeiro que retira.
- Pense em uma pilha de pratos: você pega o prato de cima primeiro.
push e pop com uma lista
- Podemos construir uma stack a partir de uma lista Python.
- push =
stack.append(x)— adicionar ao final (o topo). - pop =
stack.pop()— remove e retorna o final (o topo).
stack = []
stack.append("a")
stack.append("b")
print(stack.pop())
print(stack)
peek e empty
- peek no topo sem removê-lo:
stack[-1]. - Uma stack está empty quando
len(stack) == 0. - Fazer pop em uma stack vazia é um erro, então verifique antes.
stack = [10, 20, 30]
print(stack[-1]) # peek the top
print(len(stack) == 0) # is it empty?
Em pseudocódigo do Cambridge
- O exame constrói uma stack a partir de um array mais um ponteiro
top(um índice).
DECLARE stack : ARRAY[1:10] OF INTEGER
DECLARE top : INTEGER
top ← 0 // 0 means empty
// push value
top ← top + 1
stack[top] ← value
// pop into value
value ← stack[top]
top ← top - 1
Erros comuns
- Uma stack é last-in, first-out: push no topo, pop do topo.
- Verifique se não está vazia antes de fazer pop.
Agora você tenta
- Use uma lista como sua stack (
appendpara push,poppara remover). - Clique em Check answer para testar seu código.
A stack is LIFO
A stack pushes and pops at one end — last in, first out.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Start with an empty stack. Push 1, then 2, then 3. Then pop once, storing the removed value in top. (top should be 3 and the stack should be [1, 2].)
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Use a stack to inverso the list items. Push every item onto a stack, then pop them all into result. (result should be [3, 2, 1].)
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Write top(stack) that decrescentes the top item (the last one) without removing it. If the stack is empty, return None.
Clique em Executar para ver a saída aqui.