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. Prepare
  2. Data Structures
  3. Queues
  4. Queue using Two Stacks
  5. Discussions

Queue using Two Stacks

  • pradeep_tarakar
     + 0 comments

    Approach: * take 2 stacks one for enque and another for deque. * if operation is enqueue simply push to first stack * if operation is dequeue - check if there are elements in 2nd stack if not copy all elements from 1st stack and pop the top. Otherwise simply pop 2nd stack top * if operation is front - follow above step instead of popping print the top.

    Gist is: stack 2 will have a top element to pop or print. We only copy stack 1 elements into stack 2 when it is empty.

    int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    
    stack<int> st1; // for enqueue
    stack<int> st2; // for dequeue
    int num_of_queries = 0;
    
    cin >> num_of_queries;
    
    for(int i=0; i < num_of_queries; i++){
        int op;
        cin >> op;
        
        if(op == 1){
            int data;
            cin >> data;
            st1.push(data);
            continue;
        }
        if(op == 2){
           if(!st2.empty()){
             st2.pop();
           }else{
            while(!st1.empty()){
                st2.push(st1.top());
                st1.pop();
            }
            st2.pop();
           } 
           continue;
        }
        
        if(op == 3){
            if(!st2.empty()){
                cout << st2.top()<<endl;
            }else{
                while(!st1.empty()){
                    st2.push(st1.top());
                    st1.pop();
                }
                cout << st2.top() <<endl;
            }
        }
    }
    
    return 0;
}