Implementing ADTs using arrays · Implementando ADTs usando matrizes
| English | Português |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | overflow |
| underflow/ˌʌndəˈfləʊ/ | underflow (estouro negativo) |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | array circular |
| free list/friː lɪst/ | lista livre |
There is no such thing as a stack in memory
- Open a computer and look for the stack. You will not find one. Memory is one enormous array of numbered cells, and that is all there is.
- Every stack, every queue, every linked list is that array plus two or three integer variables that remember where things are. Push is "add one to a number and store"; dequeue is "read a cell and add one to a different number".
- The whole of this lesson is bookkeeping: which pointers, which checks, and what happens at the edges.
- The exam asks you to describe the declarations, walk the pointers through a few operations, and say why the checks are there.
Não existe tal coisa como uma pilha na memória
- Abra um computador e procure pela pilha. Você não encontrará nenhuma. A memória é um enorme array de células numeradas, e isso é tudo.
- Toda pilha, toda fila, toda lista encadeada é esse array mais duas ou três variáveis inteiras que lembram onde as coisas estão. Empilhar é "adicionar um a um número e armazenar"; desenfileirar é "ler uma célula e adicionar um a um número diferente".
- Toda esta lição é contabilidade: quais ponteiros, quais verificações e o que acontece nas bordas.
- O exame pede para descrever as declarações, percorrer os ponteiros através de algumas operações e dizer por que as verificações existem.
A stack in an array
- Hold the items in
Stack[1:MaxSize]with an integerTop, 0 when the stack is empty. - Push(x): if
Top = MaxSizethe stack is full, an overflow 溢出; otherwiseTop ← Top + 1andStack[Top] ← x. - Pop(): if
Top = 0the stack is empty, an underflow 下溢; otherwise returnStack[Top]andTop ← Top − 1.
The array never moves; only Top does
Uma pilha em um array
- Segure os itens em
Stack[1:MaxSize]com uma variável inteiraTop, 0 quando a pilha está vazia. - Empilhar(x): se
Top = MaxSizea pilha está cheia, um estouro overflow; caso contrárioTop ← Top + 1eStack[Top] ← x. - Desempilhar(): se
Top = 0a pilha está vazia, um subestouro underflow; caso contrário retorneStack[Top]eTop ← Top − 1.
O array nunca se move; apenas Top faz
Pushing an item onto a stack that is already full causes a stack ______. · Empilhar um item em uma pilha já cheia causa um estouro de pilha ______.
Overflow = push when Top = MaxSize; popping from an empty stack (Top = 0) is underflow. · Overflow = empilhar quando Topo = TamanhoMax; remover de uma pilha vazia (Topo = 0) é underflow.
Match each array-stack condition to what it means. · Combine cada condição de pilha baseada em matriz com o que ela significa.
Top counts the items: 0 = empty, MaxSize = full; the two error cases are underflow and overflow. · Topo conta os itens: 0 = vazio, TamanhoMax = cheio; os dois casos de erro são underflow e overflow.
Worked example: declare and initialise the stack
- Describe the declarations and initialisation needed to implement a stack of up to 50 integers using an array. [5]
- An array of 50 elements of type
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, to hold the items. - A constant or variable
MaxSizeset to 50, so that push can test for full. - An
INTEGERtop-of-stack pointer,Top, initialised to 0 to show the stack is empty; pop tests it for underflow, and push compares it withMaxSizefor overflow.
Exemplo resolvido: declarar e inicializar a pilha
- Descreva as declarações e inicialização necessárias para implementar uma pilha de até 50 inteiros usando um array. [5]
- Um array de 50 elementos do tipo
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, para segurar os itens. - Uma constante ou variável
MaxSizedefinida como 50, para que o push possa testar se está cheia. - Um ponteiro de topo-de-pilha
INTEGER,Top, inicializado como 0 para mostrar que a pilha está vazia; pop testa para subestouro, e push compara comMaxSizepara estouro.
Which belong in the declaration and initialisation of an array-based stack? Select all · todos that apply. · Quais pertencem à declaração e inicialização de uma pilha baseada em matriz? Selecione todos os que se aplicam.
A stack needs one pointer, Top. A front pointer belongs to a queue. · Uma pilha precisa de apenas um ponteiro, Topo. Um ponteiro frontal pertence a uma fila.
A queue in a plain array
- Two pointers:
Frontfor the next item to leave,Rearfor the next free space. Enqueue stores atRearand moves it on; dequeue reads atFrontand moves it on. - Both pointers only ever move forward, so after a few operations they march off the end of the array while the cells at the start sit empty and unusable.
- The fix is to let the pointers wrap around.
Uma fila em um array simples
- Dois ponteiros:
Frontpara o próximo item a sair,Rearpara o próximo espaço livre. Enfileirar armazena emReare o move; desenfileirar lê emFronte o move. - Ambos os ponteiros só se movem para frente, então após algumas operações eles marcham para fora do final do array enquanto as células no início ficam vazias e inutilizáveis.
- A solução é deixar os ponteiros voltarem.
The circular array
- A circular array 循环数组 wraps a pointer back to the first cell when it passes the last: with 1-based indices,
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x): check not full;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue(): check not empty; returnQueue[Front];Front ← (Front MOD MaxSize) + 1. - Keep a separate count: when the queue is completely full and when it is completely empty the two pointers are in the same relative position, so the pointers alone cannot tell the two apart.
After the last cell comes the first cell
O array circular
- Um array circular 循环数组 volta um ponteiro para a primeira célula quando passa a última: com índices baseados em 1,
Rear ← (Rear MOD MaxSize) + 1. - Enfileirar(x): verificar se não está cheia;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Desenfileirar(): verificar se não está vazia; retornarQueue[Front];Front ← (Front MOD MaxSize) + 1. - Mantenha um contador separado: quando a fila está completamente cheia e quando está completamente vazia, os dois ponteiros estão na mesma posição relativa, então os ponteiros sozinhos não podem distinguir os dois.
Após a última célula vem a primeira célula
Implementing ADTs with arrays · Implementando ADTs com matrizes
FIFO
A queue · fila is first-in-first-out — enqueue at the back, dequeue from the front. · Uma fila é primeira-a-entrar-primeiro-a-sair — enfileirar na parte traseira, desenfileirar pela frente.
Why use a circular array for a queue? · Por que usar uma matriz circular para uma fila?
A linear queue wastes the cells at the start as Front advances; wrapping with MOD reuses them. · Uma fila linear desperdiça as células no início conforme a Frente avança; a circulação com MOD as reutiliza.
A circular queue uses MOD so the front/rear pointers wrap around and reuse the cells freed at the start of the array. · Uma fila circular usa MOD para que os ponteiros frontal/traseiro circulem e reutilizem as células liberadas no início da matriz.
(pointer MOD MaxSize) + 1 wraps the index back to the first cell, so a linear queue no longer wastes the cells Front has passed. · (pointer MOD MaxSize) + 1 faz o índice voltar para a primeira célula, então uma fila linear não desperdiça mais as células que a Frente passou.
Worked example: walk the pointers
- With
MaxSize = 6: ifRear = 5, then(5 MOD 6) + 1 = 6, so the next item goes in cell 6. IfRear = 6, then(6 MOD 6) + 1 = 1: the pointer wraps to cell 1. - A circular queue is held in an array of size 5, indices 0 to 4, with
Front = 3,Rear = 3and one item stored. Two items are added, then two removed. With 0-based indices each move is(pointer + 1) MOD 5. - Adding twice moves
Rear: 3 → 4, then 4 → 0, because (4 + 1) MOD 5 = 0. Removing twice movesFront: 3 → 4 → 0. One item remains, at index 0, and the queue reused the cells freed at the start of the array.
Exemplo resolvido: percorrer os ponteiros
- Com
MaxSize = 6: seRear = 5, então(5 MOD 6) + 1 = 6, então o próximo item entra na célula 6. SeRear = 6, então(6 MOD 6) + 1 = 1: o ponteiro volta para a célula 1. - Uma fila circular é mantida em um array de tamanho 5, índices 0 a 4, com
Front = 3,Rear = 3e um item armazenado. Dois itens são adicionados, depois dois removidos. Com índices baseados em 0, cada movimento é(pointer + 1) MOD 5. - Adicionar duas vezes move
Rear: 3 → 4, depois 4 → 0, porque (4 + 1) MOD 5 = 0. Remover duas vezes moveFront: 3 → 4 → 0. Um item permanece, no índice 0, e a fila reutilizou as células liberadas no início do array.
A circular queue uses cells 1 to 6 and Rear = 6. After Rear ← (Rear MOD 6) + 1, where does the next item go? · Uma fila circular usa células 1 a 6 e Traseiro = 6. Após Traseiro ← (Traseiro MOD 6) + 1, onde vai o próximo item?
6 MOD 6 = 0, plus 1 gives 1. The pointer wraps to the start of the array. · 6 MOD 6 = 0, mais 1 dá 1. O ponteiro circula para o início da matriz.
Worked example: the enqueue algorithm in words
- Describe the algorithm for adding an item to a circular queue. [4]
- If the count equals the size, report that the queue is full and stop.
- Otherwise add one to the rear pointer; if it is now past the last index, set it to the first index.
- Store the item at the rear pointer and add one to the count.
Exemplo resolvido: o algoritmo de enfileirar em palavras
- Descreva o algoritmo para adicionar um item a uma fila circular. [4]
- Se o contador for igual ao tamanho, relate que a fila está cheia e pare.
- Caso contrário, adicione um ao ponteiro traseiro; se estiver além do último índice, defina-o para o primeiro índice.
- Armazene o item no ponteiro traseiro e adicione um ao contador.
Put the steps of adding to a circular queue in order. · Coloque os passos para adicionar a uma fila circular em ordem.
Check, move, wrap, store, count. The wrap is what makes the array circular. · Verifique, mova, circule, armazene, conte. A circulação é o que torna a matriz circular.
A linked list in an array
- Use an array of node records, each with a
Nextindex;-1marks the end. AHeadindex marks the first node,-1if the list is empty. - The unused slots are chained into a free list 空闲列表 from
FreeListHead, exactly as the data list chains its used ones.
- Insert: take the slot at
FreeListHead, set itsValueandNext, then rewire the previous node'sNextorHead. Delete: unlink the node and return its slot to the front of the free list.
Two lists share one array: the data list and the free list
Uma lista encadeada em um array
- Use um array de registros de nó, cada um com um índice de
Next;-1marca o fim. Um índice deHeadmarca o primeiro nó,-1se a lista estiver vazia. - As posições não usadas são encadeadas em uma lista livre 空闲列表 de
FreeListHead, exatamente como a lista de dados encadeia suas usadas.
TYPE TNode
DECLARE Value : INTEGER
DECLARE Next : INTEGER // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // -1 when empty
DECLARE FreeListHead : INTEGER // first unused slot
- Inserir: pegue a posição em
FreeListHead, defina seuValueeNext, depois reconecte o nó anterior'sNextouHead. Excluir: desvincule o nó e devolva sua posição à frente da lista livre.
Duas listas compartilham um array: a lista de dados e a lista livre
In an array-based linked list, the free list: · Em uma lista encadeada baseada em matriz, a lista livre:
The free list links the spare slots, so an insert can grab one and a delete can return one — like a second linked list of empties. · A lista livre conecta os slots extras, para que uma inserção possa pegar um e uma remoção possa devolvê-lo — como uma segunda lista de vazios.
Worked example: insert into the array-held list
DataandPointerarrays hold the list 1 → 3 → 4, withStart = 1; index 1 holdsD40, index 3 holdsD32, index 4 holdsD11with a null pointer. The free list starts at index 2 and continues 2 → 5. InsertD6betweenD32andD11.- Take the first free node, index 2, and set
FreeStartto its pointer, 5. StoreD6inData[2]. - Set
Pointer[2]to the valuePointer[3]held, which is 4. Then setPointer[3]to 2. - The list now reads 1 → 3 → 2 → 4 and the free list is 5 → null. The implementation, if asked: an array for the data, a parallel array (or record field) for the pointers, a start pointer, and a free-list pointer.
Exemplo resolvido: inserir na lista mantida em array
DataePointerarrays seguram a lista 1 → 3 → 4, comStart = 1; o índice 1 seguraD40, o índice 3 seguraD32, o índice 4 seguraD11com um ponteiro nulo. A lista livre começa no índice 2 e continua 2 → 5. InsiraD6entreD32eD11.- Pegue o primeiro nó livre, índice 2, e defina
FreeStartpara seu ponteiro, 5. ArmazeneD6emData[2]. - Defina
Pointer[2]para o valorPointer[3]segurado, que é 4. Em seguida, definaPointer[3]para 2. - A lista agora lê 1 → 3 → 2 → 4 e a lista livre é 5 → null. A implementação, se perguntada: um array para os dados, um array paralelo (ou campo de registro) para os ponteiros, um ponteiro de início e um ponteiro de lista livre.
In the worked example, after D6 is inserted the free list starts at index ____. · No exemplo resolvido, após D6 ser inserido, a lista livre começa no índice ____.
Index 2 was taken from the free list, so FreeStart moves to what index 2 pointed to, which was 5. · O índice 2 foi retirado da lista livre, então FreeStart move-se para o que o índice 2 apontava, que era 5.
When inserting into the list, the previous node's pointer should be changed before the new node's pointer is set. · Ao inserir na lista, o ponteiro do nó anterior deve ser alterado antes que o ponteiro do novo nó seja definido.
Set the new node's pointer to the old next node first. Rewiring the previous node first loses the address of the rest of the list. · Defina primeiro o ponteiro do novo nó para o antigo próximo nó. Reenviar o nó anterior primeiro faz perder o endereço do resto da lista.
Marks that slip away
- The checks come first: full before push or enqueue, empty before pop or dequeue. Describe them; they are marks.
- The wrap formula depends on the indices:
(Rear MOD MaxSize) + 1for 1-based,(Rear + 1) MOD Sizefor 0-based. Match the question's bounds. - The count is what tells a full circular queue from an empty one. Pointers alone cannot.
- Set the new node's
Nextbefore rewiring the previous node, and return a deleted node's slot to the free list, or the array slowly fills with unreachable cells.
Marcas que escapam
- As verificações vêm primeiro: cheia antes de push ou enqueue, vazia antes de pop ou dequeue. Descreva-as; elas são pontos.
- A fórmula de volta depende dos índices:
(Rear MOD MaxSize) + 1para baseados em 1,(Rear + 1) MOD Sizepara baseados em 0. Combine com os limites da questão. - O contador é o que distingue uma fila circular cheia de uma vazia. Sozinho os ponteiros não podem.
- Defina o novo nó's
Nextantes de reconectar o nó anterior, e devolva a posição de um nó excluído à lista livre, ou o array lentamente se enche de células inacessíveis.
You've got it
- stack in an array:
Stack[1:MaxSize]and aToppointer starting at 0;Top = MaxSizeis overflow,Top = 0is underflow - circular queue:
FrontandRearwrap withMOD; a separate count distinguishes full from empty - linked list in an array: node records with a
Nextindex, aHead, and a free list chaining the spare slots - every operation is check, then pointer arithmetic, then store or read; the ADT's behaviour is unchanged by how it is stored
Entendeu?
- stack em um array:
Stack[1:MaxSize]e um ponteiroTopcomeçando em 0;Top = MaxSizeé estouro,Top = 0é subfluxo - fila circular:
FronteRearembrulam comMOD; um count separado distingue cheio de vazio - lista encadeada em um array: registros de nó com um índice
Next, umHead, e uma lista livre encadeando as posições sobrando - cada operação é check, depois aritmética de ponteiro, depois store ou read; o comportamento da ETD não muda de como é armazenado