Stacks · Pilhas
What is an ADT?
- An Abstract Data Type (ADT) is a collection of data plus a set of operations on it.
- You use the operations and ignore how it is built inside.
- A stack, a queue, and a linked list are all ADTs.
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.
A stack is LIFO
- A stack is Last In, First Out (LIFO).
- The last item you add is the first one you take off.
- Think of a stack of plates: you take the top plate first.
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 and pop with a list
- We can build a stack from a Python list.
- push =
stack.append(x)— add to the end (the top). - pop =
stack.pop()— remove and return the end (the top).
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 and empty
- peek at the top without removing it:
stack[-1]. - A stack is empty when
len(stack) == 0. - Popping an empty stack is an error, so check first.
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?
In Cambridge pseudocode
- The exam builds a stack from an array plus a
toppointer (an index).
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
Common mistakes
- A stack is last-in, first-out: push to the top, pop from the top.
- Check it is not empty before you pop.
Erros comuns
- Uma stack é last-in, first-out: push no topo, pop do topo.
- Verifique se não está vazia antes de fazer pop.
Now you try
- Use a list as your stack (
appendto push,popto remove). - Press Check answer to test your code.
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 · Uma pilha é LIFO
A stack pushes and pops at one end — last in, first out. · Uma pilha empilha e desempilha em uma extremidade — último a entrar, primeiro a sair.
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].) · Comece com uma pilha vazia. Empilhe 1, depois 2, depois 3. Depois desempilhe uma vez, armazenando o valor removido em top. (top deve ser 3 e a pilha deve ser [1, 2].)
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Use a stack to reverse the list items. Push every item onto a stack, then pop them all into result. (result should be [3, 2, 1].) · Use uma pilha para reverter a lista items. Empilhe todos os itens em uma pilha, depois desempilhe todos eles em result. (result deve ser [3, 2, 1].)
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write top(stack) that returns · decrescentes the top item (the last one) without removing it. If the stack is empty, return None. · Escreva top(stack) que retorna o item superior (o último) sem removê-lo. Se a pilha estiver vazia, retorne None.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.