Projete um TAD (defina as operações) que use uma lista duplamente encadeada que possa funcionar como uma pilha.
Passo 1
O problema pede para projetar um TAD Pilha usando uma lista duplamente encadeada. O conteúdo envolve o conceito de Tipo Abstrato de Dados, especialmente pilha (LIFO), e lista duplamente encadeada. Vamos definir a estrutura interna e as operações necessárias para fazer essa pilha funcionar.
Passo 2
Para a implementação interna, a pilha será representada por uma struct que mantém um ponteiro para o nó do topo. Cada nó terá um campo de dado genérico e dois ponteiros: um para o próximo nó e outro para o anterior. Essa organização permite inserções e remoções eficientes sempre no início da lista.
Passo 3
Precisamos de uma operação de criação da pilha, que inicializa o ponteiro do topo como NULL, e de uma operação para verificar se a pilha está vazia, testando se o topo é NULL.
Passo 4
Para empilhar (push), vamos criar um novo nó, atribuir o dado, ajustar seu ponteiro next para o nó que era topo e, se esse nó existir, ajustar o ponteiro prev dele para o novo nó. Em seguida, atualizamos o topo para esse novo nó.
Passo 5
Para desempilhar (pop), primeiro verificamos se a pilha não está vazia. Retiramos o nó do topo guardando seu dado, atualizamos o topo para next, ajustamos o prev do novo topo para NULL (se existir), e liberamos o nó removido, retornando o dado.
Passo 6
Para consultar o elemento do topo (topo), basta retornar o dado do nó apontado pelo topo, depois de verificar que a pilha não está vazia.
Passo 7
Por fim, a operação de liberação percorre a pilha desde o topo, removendo e desalocando cada nó, e então desaloca a própria struct da pilha para evitar vazamento de memória.
Resposta
TAD Pilha {
// Estrutura interna
struct Node { T dado; Node *prev, *next; };
struct Pilha { Node *topo; };
// Estrutura interna
struct Node { T dado; Node *prev, *next; };
struct Pilha { Node *topo; };
// Operações abstratas
Pilha* criaPilha(); // inicializa pilha vazia
bool vazia(Pilha *p); // retorna true se p->topo == NULL
void push(Pilha *p, T x); // empilha x no topo
T pop(Pilha *p); // desempilha e retorna o valor do topo
T topo(Pilha *p); // retorna o valor do topo sem remover
void libera(Pilha *p); // libera todos os nós e a pilha
Pilha* criaPilha(); // inicializa pilha vazia
bool vazia(Pilha *p); // retorna true se p->topo == NULL
void push(Pilha *p, T x); // empilha x no topo
T pop(Pilha *p); // desempilha e retorna o valor do topo
T topo(Pilha *p); // retorna o valor do topo sem remover
void libera(Pilha *p); // libera todos os nós e a pilha
// Invariantes: todas as operações checam vazia§ antes de pop/topo
}
}