We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Queue using Two Stacks
  2. Discussions

Queue using Two Stacks

  • udemezuu
     + 0 comments

    Here is my c++ solution

    The idea behind moving items from stack 1 to stack 2 only when stack 2 is empty is because any item pushed unto stack 1 is the latest.

    When stack 2 is empty, and stack 1 is inverted unto stack 2 the oldest item is at the top of stack 2. Stack 2 keeps the order of oldest to newer from top to bottom.

    That way any item newer than bottom of stack 2 will be placed on stack 1.

    struct Queue {
   stack<long> s1, s2;

    // Enqueue an item to the queue
    void enQueue(long x)
    {

        // Push item into the first stack
        s1.push(x);
    }

    // Dequeue an item from the queue
    void deQueue()
    {

        int output ;
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        s2.pop();

    }

    int printFront(){
        long x = 0;
        if (s2.empty()){
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
       
        x = s2.top();
        
        return x;
    }
};

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
        Queue q;
    long input;
     int numQueries;
    long elementEnqueue;
    long printedOut;
    string outString;
    cin >> numQueries;
   vector<long>outputs;

    for(int i = 0; i<numQueries; i++){

        cin >> input;

        if(input == 1){
            cin >> elementEnqueue;
            q.enQueue(elementEnqueue);
        }
        if(input == 2){
             q.deQueue();
        }
        if(input == 3){
           printedOut = q.printFront();
           outputs.push_back(printedOut);
        }
    }

    for(int i = 0; i < outputs.size(); i++){
        cout << outputs[i] << endl;
    }
   

    return 0;
}