Tipos de Dados Abstratos — pilha, fila, lista encadeada
Introduzido| English | Significado |
|---|---|
| queue/kjuː/ | fila |
| push/pʊʃ/ | empilhar |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | tipo de dado abstrato |
| stack/stæk/ | pilha |
| linked list/lɪŋkt lɪst/ | lista encadeada |
| LIFO/ˈlaɪfəʊ/ | LIFO |
| pop/pɒp/ | desempilhar |
| pointer/ˈpɔɪntə/ | ponteiro |
| FIFO/ˈfaɪfəʊ/ | FIFO |
| enqueue/enˈkjuː/ | enfilhar |
| dequeue/diːˈkjuː/ | desenfilhar |
| node/nəʊd/ | nó |
| traverse/trəˈvɜːs/ | percorrer |
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.
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.
Um Tipo de Dados Abstrato (ADT) é definido por:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Um ADT especifica as operações (a interface); a implementação é ocultada e pode ser alterada livremente.
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
Uma pilha funciona em qual ordem?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Uma pilha é LIFO: o item empilhado mais recentemente é o primeiro a ser removido.
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.
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?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
W e Y são removidos, A então B é empilhado, B é removido. O topo é A, acima de X.
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
Pilhas, filas e listas encadeadas
LIFO vs FIFO
Uma pilha é last-in-first-out (último a entrar, primeiro a sair); push e pop ocorrem na mesma extremidade (o topo).
Uma fila é primeira-a-entrar-primeira-a-sair: os itens são removidos da ______ e adicionados na parte traseira.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
FIFO: dequeue da frente, enqueue na parte traseira — como uma fila de pessoas.
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.
Coloque os passos para adicionar um item a uma fila em ordem (o ponteiro traseiro marca o próximo espaço livre).
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
O verificação vem primeiro; depois armazena, depois move, sob esta convenção. Diga qual convenção você usa.
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
Uma lista encadeada: nós unidos por ponteiros
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.
Cada nó de uma lista encadeada contém:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.
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).
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Esse é o compromisso entre matriz e lista: matrizes oferecem acesso por índice O(1); listas oferecem inserção/remoção barata.
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.
Coloque os passos para inserir um valor em uma lista encadeada ordenada em ordem.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Encontre, preencha, aponte o novo nó para frente, depois reenvie o nó anterior. Inverter os últimos dois faz perder o resto da lista.
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.
Combine cada ADT com sua regra e um uso típico.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Pilha = último-a-entrar-primeiro-a-sair; fila = primeiro-a-entrar-primeiro-a-sair; uma lista encadeada encadeia nós com ponteiros.
Trabalhos de impressão devem ser impressos na ordem em que foram enviados. Qual ADT e por quê?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
A ordem de chegada segue a regra FIFO. Uma pilha imprimiria o trabalho mais recente primeiro.
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.
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.
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