Abstract Data Types — stack, queue, linked list · Tipos de Dados Abstratos — pilha, fila, lista encadeada
| English | Português |
|---|---|
| queue/kjuː/ | fila |
| push/pʊʃ/ | empurrão |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | tipo abstrato de dado |
| stack/stæk/ | pilha |
| linked list/lɪŋkt lɪst/ | lista ligada |
| LIFO/ˈlaɪfəʊ/ | LIFO |
| pop/pɒp/ | pop |
| pointer/ˈpɔɪntə/ | ponteiro |
| FIFO/ˈfaɪfəʊ/ | FIFO |
| enqueue/enˈkjuː/ | enqueue |
| dequeue/diːˈkjuː/ | dequeue |
| node/nəʊd/ | nó |
| traverse/trəˈvɜːs/ | percorrer |
The Back button and the printer queue
- Every page you visit is pushed onto a pile; the Back button takes the top one off. The page you left most recently is the first you return to.
- Down the corridor, a printer works through jobs in the order they arrived. The document sent first comes out first, however small the ones behind it.
- Two structures, opposite rules, and you use both before break. Neither says how it is stored; each says only what its operations do.
- That is an abstract data type 抽象数据类型. This lesson is the three the syllabus names, the operations on each, and how to justify one for a situation.
O botão Voltar e a fila de impressão
- Cada página visitada é empilhada; o botão Voltar retira a superior. A página que você deixou mais recentemente é a primeira que retorna.
- No corredor, uma impressora processa trabalhos pela ordem de chegada. O documento enviado primeiro sai primeiro, independentemente de quão pequenos sejam os seguintes.
- Duas estruturas, regras opostas, e você usa ambas antes do intervalo. Nenhuma diz como é armazenada; cada uma diz apenas o que suas operações fazem.
- Isso é um tipo de dado abstrato 抽象数据类型. Esta lição são os três que o currículo nomeia, as operações em cada um, e como justificar um para uma situação.
What an ADT is
- An abstract data type (ADT) is a collection of data together with a set of operations on that data. That one sentence is the one-mark definition.
- It is defined by what the operations do, not by how the data is stored. The implementation is hidden, so it can change without affecting the code that uses it.
- A stack, a queue, a linked list, a binary tree and an array are all ADTs.
O que é um TDA
- Um tipo de dado abstrato (TDA) é um conjunto de dados junto com um conjunto de operações sobre esses dados. Essa única frase é a definição de uma marca.
- É definido pelo o que as operações fazem, não por como os dados são armazenados. A implementação é ocultada, então pode mudar sem afetar o código que o utiliza.
- Uma pilha, uma fila, uma lista ligada, uma árvore binária e um array são todos TDAs.
An Abstract Data Type (ADT) is defined by: · Um Tipo de Dados Abstrato (ADT) é definido por:
An ADT specifies the operations (the interface); the implementation is hidden and can change freely. · Um ADT especifica as operações (a interface); a implementação é ocultada e pode ser alterada livremente.
The stack
- A stack 栈 is a list in which items are added to and removed from the same end, the top, so the last item added is the first removed: LIFO 后进先出.
- Operations: push 入栈 adds to the top, pop 出栈 removes from the top, peek looks at the top, and tests for empty and full.
- Uses: undo history, the Back button, the return addresses of function calls, checking brackets, backtracking.
Everything happens at the top
A pilha
- Uma pilha 栈 é uma lista em que itens são adicionados e removidos na mesma extremidade, o topo, então o último item adicionado é o primeiro removido: LIFO后进先出.
- Operações: push 入栈 adiciona no topo, pop 出栈 remove do topo, peek olha para o topo, e testa se está vazio ou cheio.
- Usos: histórico de desfazer, botão Voltar, endereços de retorno de chamadas de função, verificação de colchetes, retrocesso.
Tudo acontece no topo
A stack works in which order? · Uma pilha funciona em qual ordem?
A stack is LIFO: the most recently pushed item is the first to be popped. · Uma pilha é LIFO: o item empilhado mais recentemente é o primeiro a ser removido.
Worked example: trace the stack
- A stack holds, from the bottom,
'P' 'N' 'Z' 'X' 'Y' 'W'; the top pointer is at'W'. The operationsPOP,POP,PUSH 'A',PUSH 'B',POPare performed. What does the stack hold, and where is the pointer? - The two pops remove
'W'then'Y'. The pushes put'A'then'B'in their places. The last pop removes'B'. - The stack holds
'P' 'N' 'Z' 'X' 'A', with the pointer at'A'. The item on the stack longest is the bottom one,'P'; five more pops are possible, and a sixth would be an error, which is why pop tests for empty first.
Exemplo resolvido: rastrear a pilha
- Uma pilha contém, da base,
'P' 'N' 'Z' 'X' 'Y' 'W'; o ponteiro do topo está em'W'. As operaçõesPOP,POP,PUSH 'A',PUSH 'B',POPsão executadas. O que a pilha contém e onde está o ponteiro? - Os dois pops removem
'W'então'Y'. Os pushes colocam'A'então'B'em seus lugares. O último pop remove'B'. - A pilha contém
'P' 'N' 'Z' 'X' 'A', com o ponteiro em'A'. O item na pilha por mais tempo é o da base,'P'; cinco mais pops são possíveis, e um sexto seria um erro, que é por que pop testa se está vazio primeiro.
A stack holds P N Z X Y W (top is W). After POP, POP, PUSH 'A', PUSH 'B', POP, which item is on top? · Uma pilha contém P N Z X Y W (topo é W). Após POP, POP, PUSH 'A', PUSH 'B', POP, qual item está no topo?
W and Y are popped, A then B pushed, B popped. The top is A, above X. · W e Y são removidos, A então B é empilhado, B é removido. O topo é A, acima de X.
The queue
- A queue 队列 is a list in which items are added at the rear and removed from the front, so the first item added is the first removed: FIFO 先进先出.
- Operations: enqueue 入队 adds at the rear, dequeue 出队 removes from the front, and tests for empty and full.
- Uses: print spooling, keyboard buffers, scheduling, customers in a shop, breadth-first search.
Join at the back, leave from the front
A fila
- Uma fila 队列 é uma lista em que itens são adicionados na parte traseira e removidos da frente, então o primeiro item adicionado é o primeiro removido: FIFO先进先出.
- Operações: enqueue 入队 adiciona na parte traseira, dequeue 出队 remove da frente, e testa se está vazio ou cheio.
- Usos: spooling de impressão, buffers de teclado, agendamento, clientes em uma loja, busca em largura.
Entre pela parte de trás, saia pela frente
Stacks, queues & linked lists · Pilhas, filas e listas encadeadas
LIFO vs FIFO
A stack · pilha is last-in-first-out; push and pop happen at the same end (the top). · Uma pilha é last-in-first-out (último a entrar, primeiro a sair); push e pop ocorrem na mesma extremidade (o topo).
A queue is first-in-first-out: items are removed from the ______ and added at the rear. · Uma fila é primeira-a-entrar-primeira-a-sair: os itens são removidos da ______ e adicionados na parte traseira.
FIFO: dequeue from the front, enqueue at the rear — like a line of people. · FIFO: dequeue da frente, enqueue na parte traseira — como uma fila de pessoas.
Worked example: describe adding to and removing from a queue
- Adding: check that the queue is not full; store the item at the position given by the rear pointer; move the rear pointer on (and add one to the count).
- Removing: check that the queue is not empty; read the item at the front pointer; move the front pointer on (and subtract one from the count).
- State the convention you use: if the rear pointer marks the next free space, store first and then move; if it marks the last item, move first and then store. Either scores, if you are consistent.
Exemplo resolvido: descrever adição e remoção de uma fila
- Adicionando: verifique se a fila não está cheia; armazene o item na posição dada pelo ponteiro traseiro; mova o ponteiro traseiro (e adicione um à contagem).
- Removendo: verifique se a fila não está vazia; leia o item no ponteiro frontal; mova o ponteiro frontal (e subtraia um da contagem).
- Declare a convenção que você usa: se o ponteiro traseiro marca o próximo espaço livre, armazene primeiro e depois mova; se marca o último item, mova primeiro e depois armazene. Ambas marcam pontos, se você for consistente.
Put the steps of adding an item to a queue in order (rear pointer marks the next free space). · Coloque os passos para adicionar um item a uma fila em ordem (o ponteiro traseiro marca o próximo espaço livre).
The check comes first; then store, then move, under this convention. Say which convention you use. · O verificação vem primeiro; depois armazena, depois move, sob esta convenção. Diga qual convenção você usa.
The linked list
- A linked list 链表 is a list in which each node 节点 holds a data item and a pointer 指针 to the next node, with a start pointer to the first node. The last node's pointer is a sentinel such as
NULL. - Operations: insert, delete, search, and traverse 遍历, following the pointers from the head to visit every node in order.
- Advantage over an array: inserting or deleting is cheap, just rewire pointers, and the list grows as needed. Disadvantage: no random access; reaching the tenth node means following nine pointers.
A value and an arrow, repeated
A lista ligada
- Uma lista ligada 链表 é uma lista em que cada nó 节点 contém um item de dados e um ponteiro 指针 para o próximo nó, com um ponteiro inicial para o primeiro nó. O ponteiro do último nó é um sentinela como
NULL. - Operações: inserir, deletar, buscar e percorrer 遍历, seguindo os ponteiros da cabeça para visitar cada nó na ordem.
- Vantagem sobre um array: inserir ou deletar é barato, basta reencaminhar ponteiros, e a lista cresce conforme necessário. Desvantagem: sem acesso aleatório; alcançar o décimo nó significa seguir nove ponteiros.
Um valor e uma seta, repetido
A linked list: nodes joined by pointers · Uma lista encadeada: nós unidos por ponteiros
Each node stores a value and a pointer to the next node. Inserting or deleting just re-links pointers — no items shift along, unlike an array. · Cada nó armazena um valor e um ponteiro para o próximo nó. Inserir ou deletar apenas religa ponteiros — nenhum item se move, diferentemente de uma matriz.
Each node of a linked list holds: · Cada nó de uma lista encadeada contém:
A node stores its value plus a pointer (reference) to the next node; the head marks the start, NULL the end. · Um nó armazena seu valor mais um ponteiro (referência) para o próximo nó; a cabeça marca o início, NULL o fim.
A linked list makes inserting/deleting cheap (just rewire pointers) but random access slow (you must follow pointers from the head). · Uma lista encadeada torna inserções/remoções baratas (apenas reenviar ponteiros), mas acesso aleatório lento (você deve seguir os ponteiros desde a cabeça).
That is the array-vs-list trade-off: arrays give O(1) index access; lists give cheap insert/delete. · Esse é o compromisso entre matriz e lista: matrizes oferecem acesso por índice O(1); listas oferecem inserção/remoção barata.
Worked example: add a node in order
- Describe how a new value is inserted into a linked list that is kept in ascending order. [4]
- Traverse the list from the head, following the pointers, until the node before the position is found: the last node whose value is smaller than the new one.
- Take a free node and store the new value in it. Set the new node's pointer to the address the previous node currently points to.
- Then set the previous node's pointer to the new node. If the new value belongs at the front, it is the head pointer that changes instead.
Exemplo resolvido: adicionar um nó em ordem
- Descreva como um novo valor é inserido em uma lista encadeada mantida em ordem crescente. [4]
- Percorra a lista desde o cabeçalho, seguindo os ponteiros, até encontrar o nó antes da posição: o último nó cujo valor é menor que o novo.
- Pegue um nó livre e armazene o novo valor nele. Defina o ponteiro do novo nó para o endereço ao qual o nó anterior atualmente aponta.
- Em seguida, defina o ponteiro do nó anterior para o novo nó. Se o novo valor pertence à frente, é o ponteiro de cabeçalho que muda em vez disso.
Put the steps of inserting a value into an ordered linked list in order. · Coloque os passos para inserir um valor em uma lista encadeada ordenada em ordem.
Find, fill, point the new node forward, then rewire the previous node. Reversing the last two loses the rest of the list. · Encontre, preencha, aponte o novo nó para frente, depois reenvie o nó anterior. Inverter os últimos dois faz perder o resto da lista.
Justifying the choice
- Items must be handled in the order they arrived, print jobs, key presses, customers: a queue, because it is first in, first out.
- The most recent item must be handled first, undo, going back, nested calls: a stack, because it is last in, first out.
- Items are frequently inserted or deleted in the middle of an ordered collection, and the size is unknown: a linked list, because only pointers change and nothing is shifted.
- Name the structure, name its rule, tie the rule to the situation.
Justificando a escolha
- Os itens devem ser processados na ordem de chegada, trabalhos de impressão, teclas pressionadas, clientes: uma fila, porque é primeiro a entrar, primeiro a sair.
- O item mais recente deve ser processado primeiro, desfazer, voltar, chamadas aninhadas: uma pilha, porque é último a entrar, primeiro a sair.
- Os itens são frequentemente inseridos ou deletados no meio de uma coleção ordenada, e o tamanho é desconhecido: uma lista encadeada, porque apenas ponteiros mudam e nada é transferido.
- Nomeie a estrutura, nomeie sua regra, vincule a regra à situação.
Match each ADT to its rule and a typical use. · Combine cada ADT com sua regra e um uso típico.
Stack = last-in-first-out; queue = first-in-first-out; a linked list chains nodes with pointers. · Pilha = último-a-entrar-primeiro-a-sair; fila = primeiro-a-entrar-primeiro-a-sair; uma lista encadeada encadeia nós com ponteiros.
Print jobs must be printed in the order they were sent. Which ADT, and why? · Trabalhos de impressão devem ser impressos na ordem em que foram enviados. Qual ADT e por quê?
Order of arrival is the FIFO rule. A stack would print the most recent job first. · A ordem de chegada segue a regra FIFO. Uma pilha imprimiria o trabalho mais recente primeiro.
ADT versus implementation
- The ADT is the behaviour: push and pop, enqueue and dequeue, insert and traverse.
- The implementation is the storage: in this course, an array plus a few pointer variables (next lesson).
- A question about the ADT wants operations and rules; a question about implementation wants arrays, pointers and the checks.
ETD versus implementação
- A ETD é o comportamento: empilhar e desempilhar, enfileirar e desenfileirar, inserir e percorrer.
- A implementação é o armazenamento: neste curso, um array mais algumas variáveis de ponteiro (próxima aula).
- Uma pergunta sobre a ETD quer operações e regras; uma pergunta sobre implementação quer arrays, ponteiros e as verificações.
Marks that slip away
- Push and enqueue test for full first; pop and dequeue test for empty first. Write the check into the description.
- Inserting into a linked list: set the new node's pointer before changing the previous node's, or the rest of the list is lost.
- A stack changes at one end, a queue at both. "Remove from the top of the queue" is a stack answer.
- Expand the abbreviations once: LIFO, last in first out; FIFO, first in first out.
Marcas que escapam
- Empilhar e enfileirar testam cheia primeiro; desempilhar e desenfileirar testam vazia primeiro. Escreva a verificação na descrição.
- Inserir em uma lista encadeada: defina o ponteiro do nó novo antes de mudar o do nó anterior, senão o resto da lista é perdido.
- Uma pilha muda em uma extremidade, uma fila em ambas. "Remover do topo da fila" é resposta de pilha.
- Expanda as abreviações uma vez: LIFO, last in first out; FIFO, first in first out.
You've got it
- an ADT is a collection of data together with a set of operations on it; behaviour, not storage
- stack: add and remove at the top, LIFO, push and pop · queue: add at the rear, remove at the front, FIFO, enqueue and dequeue
- linked list: nodes of value + pointer from a head pointer; cheap insert and delete, slow random access; traverse by following pointers
- justify by rule: order of arrival → queue; most recent first → stack; frequent insertion in the middle → linked list
Entendeu?
- uma ETD é um conjunto de dados junto com um conjunto de operações sobre ele; comportamento, não armazenamento
- pilha: adicionar e remover no topo, LIFO, push e pop · fila: adicionar na traseira, remover na frente, FIFO, enqueue e dequeue
- lista encadeada: nós de valor + ponteiro de um ponteiro de cabeçalho; inserção e deleção baratas, acesso aleatório lento; percorra seguindo ponteiros
- justifique pela regra: ordem de chegada → fila; mais recente primeiro → pilha; inserção frequente no meio → lista encadeada