Implementando ADTs usando matrizes
Introduzido| English | Significado |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | transbordo |
| underflow/ˌʌndəˈfləʊ/ | estouro de pilha |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | array circular |
| free list/friː lɪst/ | lista livre |
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.
Uma pilha em um array
- Segure os itens em
Stack[1:MaxSize]com uma variável inteiraTop, 0 quando a pilha está vazia. - Push(x): se
Top = MaxSizea pilha está cheia, ocorre um estouro; caso contrário, retornaTop ← Top + 1eStack[Top] ← x. - Pop(): se
Top = 0a pilha estiver vazia, ocorre um underflow; caso contrário, retornaStack[Top]eTop ← Top − 1.

O array nunca se move; apenas Top faz
Empilhar um item em uma pilha já cheia causa um estouro de pilha ______.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Overflow = empilhar quando Topo = TamanhoMax; remover de uma pilha vazia (Topo = 0) é underflow.
Combine cada condição de pilha baseada em matriz com o que ela significa.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Topo conta os itens: 0 = vazio, TamanhoMax = cheio; os dois casos de erro são underflow e 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.
Quais pertencem à declaração e inicialização de uma pilha baseada em matriz? Selecione todos os que se aplicam.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Uma pilha precisa de apenas um ponteiro, Topo. Um ponteiro frontal pertence a uma fila.
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.
O array circular
- Uma matriz circular reinicia o ponteiro para a primeira célula ao passar da ú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
Implementando ADTs com matrizes
FIFO
Uma fila é primeira-a-entrar-primeiro-a-sair — enfileirar na parte traseira, desenfileirar pela frente.
Por que usar uma matriz circular para uma fila?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Uma fila linear desperdiça as células no início conforme a Frente avança; a circulação com MOD as reutiliza.
Uma fila circular usa MOD para que os ponteiros frontal/traseiro circulem e reutilizem as células liberadas no início da matriz.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
(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.
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.
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?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
6 MOD 6 = 0, mais 1 dá 1. O ponteiro circula para o início da matriz.
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.
Coloque os passos para adicionar a uma fila circular em ordem.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Verifique, mova, circule, armazene, conte. A circulação é o que torna a matriz circular.
Uma lista encadeada em um array
- Use um array de registros de nó, cada um com um índice de
NextIndex;-1marca o fim. Um índice deHeadmarca o primeiro nó,-1se a lista estiver vazia. - Os slots não utilizados são encadeados em uma lista de espaços livres a partir de
FreeListHead, exatamente como a lista de dados encadeia os ocupados.
TYPE TNode
DECLARE Value : INTEGER
DECLARE NextIndex : 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 seuValueeNextIndex, depois reconecte o nó anterior'sNextIndexouHead. 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
Em uma lista encadeada baseada em matriz, a lista livre:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.
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.
No exemplo resolvido, após D6 ser inserido, a lista livre começa no índice ____.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
O índice 2 foi retirado da lista livre, então FreeStart move-se para o que o índice 2 apontava, que era 5.
Ao inserir na lista, o ponteiro do nó anterior deve ser alterado antes que o ponteiro do novo nó seja definido.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.
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
NextIndexantes 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.
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
NextIndex, 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