Skip to content
The Chat Archive
gpt-4-0314· OpenAI WildChat-4.8M (AI2)

você deve primeiro implementar uma fila usando duas pilhas. Em seguida, processe a…

  1. 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

  2. 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();
    };
    
    #endif
    

    Queue.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.