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.

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.

Exercícios relacionados