Projete um algoritmo e descreva as estruturas de dados para implementar operações de desfazer/refazer…

Questão

Projete um algoritmo e descreva as estruturas de dados para implementar operações de desfazer/refazer (undo/redo) em um editor de texto simples. Explique como registrar cada operação, aplicar undo e redo e a complexidade envolvida.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Use duas pilhas: undo_stack e redo_stack. Representar cada operação como um delta (tipo da operação, posição, conteúdo afetado) e também seu inverso. Ao executar uma edição: aplicar o delta no texto, empilhar o delta inverso em undo_stack e limpar redo_stack. Para undo: desempilhar inverso de undo_stack, aplicar no texto e empilhar o inverso desse inverso em redo_stack (ou seja, o delta original). Para redo: desempilhar de redo_stack, aplicar e empilhar o inverso em undo_stack. Essa abordagem permite O(k) por operação, onde k é o tamanho do delta (tipicamente O(1) para uma inserção/exclusão de caractere); operações de push/pop em pilha são O(1). Para reduzir memória, armazenar deltas compactos (por exemplo, intervalos e strings) e, se necessário, criar checkpoints periódicos para limitar profundidade histórica.

Explicação

A utilização de duas pilhas permite gerenciar eficientemente as operações de desfazer e refazer, garantindo que cada ação possa ser revertida ou repetida de forma organizada. A representação das operações como deltas facilita a aplicação das mudanças no texto e a recuperação do estado anterior, mantendo a complexidade das operações em níveis aceitáveis. Além disso, a estratégia de armazenamento compacto e a criação de checkpoints ajudam a otimizar o uso de memória e a performance do algoritmo.

Raio-X da questão

Questões parecidas com resolução

• Crie e descreva um algoritmo, em linguagem simples ou pictográfica, que ajude uma criança a decidir se deve levar um…
• Crie um algoritmo em linguagem oral ou escrita que controle a rega de um vaso por 7 dias: diariamente verificar se…
• Projete em pseudocódigo um algoritmo que reconstrua uma mensagem a partir de pacotes recebidos onde cada pacote contém…
• Elabore em pseudocódigo um algoritmo que, dado um vetor de registros 'tarefas' (descricao, duracao_horas, prioridade) e…
• Elabore em pseudocódigo um algoritmo que, dado um array de registros 'alunos' com campos (nome, notas[4]…
• Projete em pseudocódigo um algoritmo de triagem para uma fila digital cujas variáveis são prioridade (inteiro 1–5, 1 =…

Todas as questões de Algoritmos