você deve primeiro implementar uma fila usando duas pilhas. Em seguida, processe a…
- User
você deve primeiro implementar uma fila usando duas pilhas. Em seguida, processe a consultas, em que cada consulta é um dos seguintes 3 tipos:
1 x: Enfileirar o elemento x no final da fila. 2: Retirar da fila o elemento na frente da fila. 3: Mostre o elemento na frente da fila. Formato de entrada
A primeira linha contém um único número inteiro, q, denotando o número de consultas. Cada linha i das q linhas subsequentes contém uma única consulta no padrão descrito acima no problema. Todas as três consultas começam com um número inteiro que indica o tipo da consulta, mas apenas a primeira consulta é seguida por um valor adicional x separado por espaço, indicando o valor a ser enfileirado.
Formato de saída
Para cada consulta do tipo 3, imprima o valor do elemento na frente da fila em uma nova linha. As consultas de tipo 1 e 2 não necessitam imprimir nada.
Ajuda Você pode utilizar duas pilhas. Vamos chamar a primeira pilha de “deposito” e a segunda de “prateleira”. Se precisar colocar algo, você coloca no deposito. Se precisar pegar algo você pega da prateleira. Se a prateleira estiver vazia, você retira tudo do deposito para a prateleira. Observe que agora o depósito foi invertido e a primeira a ser inserida no depósito é a última da prateleira. Atenção: nessa primeira questão é para, de fato, implementar a estrutura de dados FILA do zero usando duas Pilhas. Por esse motivo é que a questão espera três arquivos. Um é o arquivo main.cpp, outro é o Queue.cpp e outro o Queue.h
- Assistant
Segue abaixo a implementação da fila usando duas pilhas. Os arquivos estão separados como solicitado:
Queue.h:
#ifndef QUEUE_H #define QUEUE_H #include <stack> class Queue { public: void enqueue(int x); void dequeue(); int front(); private: std::stack<int> deposito; std::stack<int> prateleira; void transferirDepositoParaPrateleira(); }; #endifQueue.cpp:
#include "Queue.h" void Queue::enqueue(int x) { deposito.push(x); } void Queue::dequeue() { if (prateleira.empty()) { transferirDepositoParaPrateleira(); } if (!prateleira.empty()) { prateleira.pop(); } } int Queue::front() { if (prateleira.empty()) { transferirDepositoParaPrateleira(); } return prateleira.empty() ? -1 : prateleira.top(); } void Queue::transferirDepositoParaPrateleira() { while (!deposito.empty()) { prateleira.push(deposito.top()); deposito.pop(); } }main.cpp:
#include <iostream> #include "Queue.h" using namespace std; int main() { int q; cin >> q; Queue fila; while (q--) { int tipo; cin >> tipo; if (tipo == 1) { int x; cin >> x; fila.enqueue(x); } else if (tipo == 2) { fila.dequeue(); } else if (tipo == 3) { cout << fila.front() << endl; } } return 0; }Para testar, basta compilar e executar o programa main.cpp usando um compilador C++ (como o g++) e fornecer os dados de entrada de acordo com o formato mencionado.