Responda aos seguintes itens. Utilize uma lista encadeada simples para implementar a pilha e a fila. Declare a estrutura heterogênea utilizada.
a) O que é um tipo abstrato de dado?
b) Descreva as características de uma pilha.
c) Implemente a função de inserção em uma pilha.
d) Implemente a função de remoção em uma pilha.
e) Implemente uma função que imprima os elementos de uma pilha começando do topo.
f) Descreva as características de uma fila.
g) Implemente a função de inserção em uma fila.
h) Implemente a função de remoção em uma fila.
i) Implemente uma função que imprima os elementos de uma fila.
Implemente a função main que oferece ao usuário as operações acima.
a) O que é um tipo abstrato de dado?
b) Descreva as características de uma pilha.
c) Implemente a função de inserção em uma pilha.
d) Implemente a função de remoção em uma pilha.
e) Implemente uma função que imprima os elementos de uma pilha começando do topo.
f) Descreva as características de uma fila.
g) Implemente a função de inserção em uma fila.
h) Implemente a função de remoção em uma fila.
i) Implemente uma função que imprima os elementos de uma fila.
Implemente a função main que oferece ao usuário as operações acima.
Passo 1
Beleza, vamos lá! Você me enviou um exercício que envolve implementar uma pilha e uma fila usando uma lista encadeada simples. O conteúdo está relacionado a Estruturas de Dados, especificamente a Tipos Abstratos de Dados (TAD) como pilhas e filas. Para resolver isso, vamos precisar entender o que são esses TADs, suas características, e como implementar as operações básicas usando programação, provavelmente em C ou outra linguagem que suporte estruturas.
Passo 2
a) O que é um tipo abstrato de dado?
Um Tipo Abstrato de Dado (TAD) é uma forma de organizar e estruturar dados, definindo quais operações podem ser realizadas sobre eles sem especificar como essas operações são implementadas internamente. É como um contrato que diz o que o dado pode fazer, mas não como ele faz. Por exemplo, uma pilha é um TAD que permite inserir e remover elementos seguindo a ordem LIFO (Last In, First Out), mas não detalha como exatamente essa inserção e remoção ocorrem.
Passo 3
b) Descreva as características de uma pilha.
Uma pilha é uma estrutura de dados que segue o princípio LIFO (Last In, First Out), ou seja, o último elemento inserido é o primeiro a ser removido. As principais características de uma pilha são:
- Operação de Inserção (Push): Adiciona um elemento no topo da pilha.
- Operação de Remoção (Pop): Remove o elemento do topo da pilha.
- Topo (Top): Referência ao elemento que está no topo da pilha.
- Restrição de Acesso: Apenas o elemento do topo pode ser acessado diretamente.
Passo 4
c) Implemente a função de inserção em uma pilha.
Vamos implementar a função de inserção, que geralmente é chamada de
push
. Primeiro, precisamos definir a estrutura da pilha usando uma lista encadeada simples.#include <stdio.h>
#include <stdlib.h>
// Estrutura do Nodo
typedef struct Nodo {
int dado;
struct Nodo* proximo;
} Nodo;
// Estrutura da Pilha
typedef struct Pilha {
Nodo* topo;
} Pilha;
// Função de criação da pilha
Pilha* criarPilha() {
Pilha* pilha = (Pilha*) malloc(sizeof(Pilha));
pilha->topo = NULL;
return pilha;
}
// Função de inserção (push)
void push(Pilha* pilha, int valor) {
Nodo* novoNodo = (Nodo*) malloc(sizeof(Nodo));
novoNodo->dado = valor;
novoNodo->proximo = pilha->topo;
pilha->topo = novoNodo;
printf("Elemento %d inserido na pilha.\n", valor);
}
Aqui, criamos um nodo que contém o dado e o ponteiro para o próximo elemento. A pilha mantém o ponteiro para o topo. A função
push
adiciona um novo nodo no topo.Passo 5
d) Implemente a função de remoção em uma pilha.
Agora, vamos implementar a função de remoção, chamada
pop
, que remove o elemento do topo da pilha.// Função de remoção (pop)
int pop(Pilha* pilha) {
if (pilha->topo == NULL) {
printf("Pilha vazia! Não tem o que remover.\n");
return -1; // Indicador de erro
}
Nodo* temp = pilha->topo;
int valor = temp->dado;
pilha->topo = pilha->topo->proximo;
free(temp);
printf("Elemento %d removido da pilha.\n", valor);
return valor;
}
A função
pop
verifica se a pilha está vazia. Se não estiver, ela remove o nodo do topo, atualiza o ponteiro do topo e retorna o valor removido.Passo 6
e) Implemente uma função que imprima os elementos de uma pilha começando do topo.
Vamos criar uma função para imprimir todos os elementos da pilha a partir do topo.
// Função para imprimir a pilha
void imprimirPilha(Pilha* pilha) {
Nodo* atual = pilha->topo;
if (atual == NULL) {
printf("Pilha vazia!\n");
return;
}
printf("Elementos da pilha (do topo): ");
while (atual != NULL) {
printf("%d ", atual->dado);
atual = atual->proximo;
}
printf("\n");
}
Essa função percorre a lista encadeada começando do topo e imprime cada elemento até chegar ao final (onde o próximo é
NULL
).Passo 7
f) Descreva as características de uma fila.
Uma fila é uma estrutura de dados que segue o princípio FIFO (First In, First Out), ou seja, o primeiro elemento inserido é o primeiro a ser removido. As principais características de uma fila são:
- Operação de Inserção (Enqueue): Adiciona um elemento no final da fila.
- Operação de Remoção (Dequeue): Remove o elemento da frente da fila.
- Frente (Front): Referência ao primeiro elemento da fila.
- Final (Rear): Referência ao último elemento da fila.
- Restrição de Acesso: Apenas os elementos da frente podem ser removidos diretamente.
Passo 8
g) Implemente a função de inserção em uma fila.
Vamos implementar a função de inserção, chamada
enqueue
. Primeiro, definimos a estrutura da fila usando uma lista encadeada simples.// Estrutura da Fila
typedef struct Fila {
Nodo* frente;
Nodo* traseira;
} Fila;
// Função de criação da fila
Fila* criarFila() {
Fila* fila = (Fila*) malloc(sizeof(Fila));
fila->frente = fila->traseira = NULL;
return fila;
}
// Função de inserção (enqueue)
void enqueue(Fila* fila, int valor) {
Nodo* novoNodo = (Nodo*) malloc(sizeof(Nodo));
novoNodo->dado = valor;
novoNodo->proximo = NULL;
if (fila->traseira == NULL) {
fila->frente = fila->traseira = novoNodo;
printf("Elemento %d inserido na fila.\n", valor);
return;
}
fila->traseira->proximo = novoNodo;
fila->traseira = novoNodo;
printf("Elemento %d inserido na fila.\n", valor);
}
Aqui, a fila mantém dois ponteiros: um para a frente e outro para a traseira. A função
enqueue
adiciona um novo nodo na traseira.Passo 9
h) Implemente a função de remoção em uma fila.
Agora, vamos implementar a função de remoção, chamada
dequeue
, que remove o elemento da frente da fila.// Função de remoção (dequeue)
int dequeue(Fila* fila) {
if (fila->frente == NULL) {
printf("Fila vazia! Não tem o que remover.\n");
return -1; // Indicador de erro
}
Nodo* temp = fila->frente;
int valor = temp->dado;
fila->frente = fila->frente->proximo;
if (fila->frente == NULL) {
fila->traseira = NULL;
}
free(temp);
printf("Elemento %d removido da fila.\n", valor);
return valor;
}
A função
dequeue
verifica se a fila está vazia. Se não estiver, ela remove o nodo da frente, atualiza os ponteiros e retorna o valor removido.Passo 10
i) Implemente uma função que imprima os elementos de uma fila.
Vamos criar uma função para imprimir todos os elementos da fila a partir da frente.
// Função para imprimir a fila
void imprimirFila(Fila* fila) {
Nodo* atual = fila->frente;
if (atual == NULL) {
printf("Fila vazia!\n");
return;
}
printf("Elementos da fila (da frente): ");
while (atual != NULL) {
printf("%d ", atual->dado);
atual = atual->proximo;
}
printf("\n");
}
Essa função percorre a lista encadeada começando da frente e imprime cada elemento até o final.
Passo 11
Implementação da função main que oferece ao usuário as operações acima.
Vamos criar uma função
main
que apresenta um menu ao usuário para escolher as operações de pilha e fila.int main() {
Pilha* pilha = criarPilha();
Fila* fila = criarFila();
int escolha, valor;
do {
printf("\nEscolha a operação:\n");
printf("1. Push na Pilha\n");
printf("2. Pop da Pilha\n");
printf("3. Imprimir Pilha\n");
printf("4. Enqueue na Fila\n");
printf("5. Dequeue da Fila\n");
printf("6. Imprimir Fila\n");
printf("0. Sair\n");
printf("Sua escolha: ");
scanf("%d", &escolha);
switch(escolha) {
case 1:
printf("Digite o valor para inserir na pilha: ");
scanf("%d", &valor);
push(pilha, valor);
break;
case 2:
pop(pilha);
break;
case 3:
imprimirPilha(pilha);
break;
case 4:
printf("Digite o valor para inserir na fila: ");
scanf("%d", &valor);
enqueue(fila, valor);
break;
case 5:
dequeue(fila);
break;
case 6:
imprimirFila(fila);
break;
case 0:
printf("Saindo...\n");
break;
default:
printf("Opção inválida! Tente novamente.\n");
}
} while(escolha != 0);
// Liberar memória restante
while(pilha->topo != NULL) {
pop(pilha);
}
free(pilha);
while(fila->frente != NULL) {
dequeue(fila);
}
free(fila);
return 0;
}
Esse
main
cria uma pilha e uma fila, apresenta um menu para o usuário escolher as operações e executa conforme a escolha. Também inclui a liberação de memória ao encerrar.Resposta
Através dos passos acima, implementamos uma pilha e uma fila utilizando listas encadeadas simples, incluindo todas as operações básicas como inserção, remoção e impressão. Além disso, criamos uma função
main
que permite ao usuário interagir com essas estruturas de dados de forma amigável.