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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Queue using Two Stacks
  2. Discussions

Queue using Two Stacks

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 64 Discussions, By:

votes

Please Login in order to post a comment

  • rishabhj928
    6 months ago+ 2 comments

    import sys
    queue = []
    for _ in range(int(input().strip())):
        q = input()
        if q[0] == "1":
            queue.append(int(q.split(" ")[1]))
        if q[0] == "2":
            queue.pop(0)
        if q[0] == "3":
            print(queue[0])
    				
    
    10|
    Permalink
  • patimen
    9 months ago+ 2 comments

    Not sure everyone here is understanding the assignment. Here it is in Kotlin:

    class Queue2s<T> {
        val stack1 = Stack<T>()
        val stack2 = Stack<T>()
        fun enqueue(value:T) {
            if (stack2.isEmpty() && stack1.isEmpty())
                stack1.push(value)
            else           
                stack2.push(value)
        }
        
        fun dequeue():T {
            if (stack1.isEmpty())
                moveStack()
             return stack1.pop()
        }
        
        fun peek():T {
            if (stack1.isEmpty())
                moveStack()
            return stack1.peek()
        }
        
        fun moveStack() {
            while (stack2.isNotEmpty()){
                stack1.push(stack2.pop())
            }
        }
    }
    
    9|
    Permalink
  • ausporras
    6 months ago+ 1 comment

    What are the benefits to using two stacks for this as opposed to one? I wrote it with one stack and was able to pass all the tests, but i'm assuming my design is inefficient in some way? Or just not the point of this problem? Just feel like i'm missing something because I didn't expect mine to pass with only one stack, just tried it for fun.

    Current complexity with one queue is O(n) complexity for dequeue from popping the first element/shifting the rest, O(1) for both enqueue and print.

    6|
    Permalink
  • 5h4nt0
    6 months ago+ 0 comments

    C++

    Enqueue - if both stack is empty then push s1 otherwise push into s2.

    Dequeue - if s1 is empty, then move all items into s1 from s2's top. Then just pop the s1's top value.

    Front Element - if s1 is empty, then move all items into s1 from s2's top. Then just print the s1's top value.

    typedef struct
    {
        stack<int> s1, s2;
    
        void enQueue(int x)
        {
            if (s1.empty() && s2.empty())
            {
                s1.push(x);
            }
            else
            {
                s2.push(x);
            }
        }
    
        void deQueue()
        {
            if (s1.empty())
            {
                while (!s2.empty())
                {
                    s1.push(s2.top());
                    s2.pop();
                }
            }
            s1.pop();
        }
    
        void frontEle()
        {
            if (s1.empty())
            {
                while (!s2.empty())
                {
                    s1.push(s2.top());
                    s2.pop();
                }
            }
            cout << s1.top() << "\n";
        }
    
    } Queue;
    
    5|
    Permalink
  • guerrandw
    8 months ago+ 1 comment

    C++

    This was a great learning experience and I want to share it with you.

    First of all this is an exercise and in practice it is slow as it is O(1) for enqueue and O(n) for dequeuing. A more optimal solution would be to use the linked list data structure.

    Second of all please watch this video as it helped me wrap my mind around the core concept: https://www.youtube.com/watch?v=AN0axYeLue0. All rights reserved to the creator.

    Thirdly, have fun with it and try to go through my solution step by step. It is by no means the best implementation but it passes the tests in a decent amount of time.

    Good luck with your learning!

    #include <bits/stdc++.h>
    using namespace std;
    
    template <typename T>
    class Queue{
    private:
        stack<T> s1;
        stack<T> s2;
    public:
        bool isEmpty(){
            return s1.empty() && s2.empty();
        }
    
        int size(){
            return s1.size() + s2.size();
        }
    
        void enqueue(T x){
            s1.push(x);
        }
    
        void dequeue(){
            if(s2.empty()) {
                while(!s1.empty()) {
                   s2.push(s1.top());
                   s1.pop();
                }
            }
            s2.pop();
        }
    
        T front(){
            if(s2.empty()) {
                while (!s1.empty()) {
                    s2.push(s1.top());
                    s1.pop();
                }
            }
            return s2.top();
        }
    
    };
    
    int main(){
        int q, type, x; cin >> q;
        Queue<int> queue; 
        for(int i=0; i<q; ++i){
            cin >> type;
            switch(type){
                case 1:
                    cin >> x;
                    queue.enqueue(x);
                    break;
                case 2:
                    queue.dequeue();
                    break;
                case 3:
                    cout << queue.front() << "\n";
                    break;
                default:
                    continue;
            }
        }
        return 0;
    }
    
    5|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature