Introdução
Você está trabalhando em um projeto para desenvolver um sistema de agendamento de trens para uma rede ferroviária movimentada.
Você ficou responsável por desenvolver um protótipo para as rotas de trem do sistema de agendamento.
Cada rota é uma sequência de estações de trem em que um determinado trem para.
Instruções
Sua equipe decidiu usar uma lista duplamente encadeada para representar cada rota de trem no cronograma.
Cada estação ao longo da rota do trem será representada por um nó na lista encadeada.
Você não precisa se preocupar com os horários de chegada e de partida nas estações.
Cada estação será representada simplesmente por um número.
As rotas podem ser estendidas, adicionando estações ao início ou ao fim de uma rota.
Também podem ser encurtadas, removendo estações do início ou do fim de uma rota.
Às vezes uma estação é fechada e, nesse caso, ela precisa ser removida da rota, mesmo que não esteja no início nem no fim dela.
O tamanho de uma rota não é medido pela distância que o trem percorre, mas por quantas estações ele para.
A lista encadeada é uma estrutura de dados fundamental na ciência da computação, frequentemente usada na implementação de outras estruturas de dados.
Como o nome sugere, é uma lista de nós que estão ligados entre si.
É uma lista de "nós", em que cada nó se liga ao seu vizinho ou aos seus vizinhos.
Em uma lista simplesmente encadeada, cada nó se liga apenas ao nó que vem depois dele.
Em uma lista duplamente encadeada, cada nó se liga tanto ao nó que vem antes quanto ao nó que vem depois.
Se você quiser se aprofundar em listas encadeadas, confira este artigo, que explica o assunto com desenhos bem explicativos.
Como este exercício está estruturado na trilha de C++
Embora listas encadeadas possam ser implementadas de várias maneiras, com diversas estruturas de dados subjacentes, pedimos aqui que você implemente sua lista encadeada de forma orientada a objetos.
No arquivo linked_list_test.cpp, você vai ver que uma classe List com template é chamada.
Esperamos que você escreva essa classe com as seguintes funções membro:
-
push adiciona um elemento ao final da lista,
-
pop remove e retorna o último elemento da lista,
-
shift remove e retorna o primeiro elemento da lista,
-
unshift adiciona um elemento ao início da lista, e
-
count retorna o número total de elementos da lista atual.
Por fim, além dos métodos acima, gostaríamos que você implementasse erase.
erase receberá um argumento, que é o valor a ser removido da lista encadeada.
Se o valor aparecer mais de uma vez, apenas a primeira ocorrência deve ser removida.
Ela deve retornar se um elemento foi excluído ou não.
Embora isso não seja testado, talvez você queira lançar uma exceção se pop e shift forem chamados em uma List vazia.
Fonte
Tópico clássico da ciência da computação
