(20 pts) Questão 1:
Implemente o código que utilize duas pilhas para armazenar os dados como se estivessem sendo armazenados em uma Fila, porém usando a estrutura de pilha para isso.
d) Execute o código que você construiu, chamando as funções necessárias para realizar as operações descritas na letra
Utilize as funções int Vazia(TPilha Pilha){ abaixo como apoio:
return (Pilha. topo == Pilha. fundo);
ef struct
codigo:
Implemente o código que utilize duas pilhas para armazenar os dados como se estivessem sendo armazenados em uma Fila, porém usando a estrutura de pilha para isso.
d) Execute o código que você construiu, chamando as funções necessárias para realizar as operações descritas na letra
Utilize as funções int Vazia(TPilha Pilha){ abaixo como apoio:
ef struct
codigo:
Passo 1
Beleza, vamos começar entendendo o que a questão está pedindo. Temos que implementar uma fila usando duas pilhas. Isso faz parte da matéria de Estruturas de Dados, especificamente trabalhando com pilhas e filas. Para resolver isso, vamos precisar entender como pilhas e filas funcionam e como podemos usar duas pilhas para simular uma fila. Além disso, vamos precisar usar algumas funções básicas para manipular as pilhas, como verificar se estão vazias.
Passo 2
Primeiro, vamos relembrar o que são pilhas e filas. Uma pilha é uma estrutura de dados que segue o princípio LIFO (Last In, First Out), ou seja, o último elemento a entrar é o primeiro a sair. Já uma fila segue o princípio FIFO (First In, First Out), onde o primeiro elemento a entrar é o primeiro a sair.
Para simular uma fila usando duas pilhas, vamos precisar de duas pilhas auxiliares. A ideia é usar uma pilha para fazer os enfileiramentos (inserir elementos) e a outra para os desenfileiramentos (remover elementos). Isso porque, para manter a ordem da fila, precisamos inverter a ordem dos elementos ao removê-los.
Passo 3
Vamos começar definindo a estrutura da pilha em C. Geralmente, uma pilha pode ser representada com um vetor e um indicador para o topo da pilha.
#define MAX 100
typedef struct {
int elementos[MAX];
int topo;
int fundo;
} TPilha;
Aqui,
elementos
é o vetor que armazena os dados, topo
indica o topo da pilha, e fundo
indica a posição inicial.Passo 4
Agora, vamos implementar a função para verificar se a pilha está vazia. A função fornecida é:
int Vazia(TPilha Pilha){
return (Pilha.topo == Pilha.fundo);
}
Essa função retorna 1 (verdadeiro) se a pilha estiver vazia (ou seja, se o topo for igual ao fundo), e 0 (falso) caso contrário.
Passo 5
Vamos implementar as funções básicas da pilha: inicializar, empilhar (push) e desempilhar (pop).
void InicializarPilha(TPilha *Pilha){
Pilha->topo = -1;
Pilha->fundo = -1;
}
int Empilhar(TPilha *Pilha, int valor){
if (Pilha->topo < MAX - 1){
Pilha->topo++;
Pilha->elementos[Pilha->topo] = valor;
return 1; // Sucesso
}
return 0; // Falha, pilha cheia
}
int Desempilhar(TPilha *Pilha, int *valor){
if (!Vazia(*Pilha)){
*valor = Pilha->elementos[Pilha->topo];
Pilha->topo--;
return 1; // Sucesso
}
return 0; // Falha, pilha vazia
}
Aqui,
InicializarPilha
configura a pilha como vazia, Empilhar
adiciona um elemento no topo, e Desempilhar
remove o elemento do topo.Passo 6
Agora, vamos implementar a fila usando duas pilhas. Vamos chamar as duas pilhas de
Pilha1
e Pilha2
. A ideia é que, para enfileirar, empilhamos na Pilha1
, e para desenfileirar, transferimos todos os elementos da Pilha1
para a Pilha2
se Pilha2
estiver vazia, e então desempilhamos de Pilha2
.typedef struct {
TPilha Pilha1;
TPilha Pilha2;
} TFilaComDuasPilhas;
void InicializarFila(TFilaComDuasPilhas *Fila){
InicializarPilha(&(Fila->Pilha1));
InicializarPilha(&(Fila->Pilha2));
}
int Enfileirar(TFilaComDuasPilhas *Fila, int valor){
return Empilhar(&(Fila->Pilha1), valor);
}
int Desenfileirar(TFilaComDuasPilhas *Fila, int *valor){
if (Vazia(Fila->Pilha2)){
int temp;
while (!Vazia(Fila->Pilha1)){
Desempilhar(&(Fila->Pilha1), &temp);
Empilhar(&(Fila->Pilha2), temp);
}
}
return Desempilhar(&(Fila->Pilha2), valor);
}
Aqui,
Enfileirar
adiciona elementos na Pilha1
, e Desenfileirar
remove elementos da Pilha2
. Se Pilha2
estiver vazia, transferimos todos os elementos de Pilha1
para Pilha2
, invertendo a ordem e mantendo o comportamento de fila.Passo 7
Agora, vamos executar o código chamando as funções necessárias para realizar as operações. Vamos supor que na letra b do exercício, foram solicitadas operações de enfileirar alguns elementos e depois desenfileirar alguns deles.
#include <stdio.h>
// Suas funções e estruturas aqui
int main(){
TFilaComDuasPilhas Fila;
InicializarFila(&Fila);
// Enfileirando elementos
Enfileirar(&Fila, 10);
Enfileirar(&Fila, 20);
Enfileirar(&Fila, 30);
int valor;
// Desenfileirando elementos
if (Desenfileirar(&Fila, &valor)){
printf("Desenfileirado: %d\n", valor);
}
if (Desenfileirar(&Fila, &valor)){
printf("Desenfileirado: %d\n", valor);
}
return 0;
}
Nesse exemplo, enfileiramos os valores 10, 20 e 30. Depois, desenfileiramos dois elementos, que devem ser 10 e 20, seguindo a ordem da fila.
Resposta
Ao executar o código, a saída será:
Desenfileirado: 10
Desenfileirado: 20