Implement Stack using Queues

Problem: Implement a stack using queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Approach: A simple approach will be to use two queues say queue1 and queue2. Here are the algorithms for different operations:

• Push: 
• IF queue1.Empty 
• queue1.Enqueue(element)
• WHILE NOT queue2.Empty
• queue1.Enqueue(queue2.Dequeue())
• ELSE IF queue2.Empty
• queue2.Enque(element)
• WHILE NOT queue1.Empty
• queue2.Enqueue(queue1.Dequeue())
• Pop:
• Returns Dequeue of queue1 / queue2 whichever is not empty
• Top:
• Returns Peek of queue1 / queue2 whichever is not empty
• Empty:
• Returns queue1.Empty AND queue2.Empty

That's all and it will work fine. The only problem is here we are using two queues. Can we reduce it? Answer is yes. How? Please look closely on the definition of Push operation, what we are trying to do is to push elements in reverse order using two queues. What if we can do it using one queue only? Here is how we can do it:

• Push: 
• queue.Enqueue(element)
• size = queue.Size
• WHILE size > 1 // Not going to enqueue current element again
• queue.Enqueue(queue.Deque())
• size = size - 1

You see we did the same thing using the same one queue. Rest of the operations are straight forward:

• Pop:
• Returns queue.Deque()
• Top:
• Returns queue.Peek()
• Empty:
• Returns queue.Empty()

Implementation in C#:

    public class MyStack

    {

        public MyStack()

        {

            this.queue = new Queue<int>();

        }

        public void Push(int x)

        {

            this.queue.Enqueue(x);

            int currQSize = this.queue.Count;

            

            // Re push every element except the current

            while(currQSize > 1)

            {

                this.queue.Enqueue(this.queue.Dequeue());

                --currQSize;

            }

        }

       public int Pop()

        {

            if (this.queue.Count > 0)

            {

                return this.queue.Dequeue();

            }

            return -1;

        }

        public int Top()

        {

            if (this.queue.Count > 0)

            {

                return this.queue.Peek();

            }

            return -1;

        }

        public bool Empty()

        {

            return this.queue.Count == 0;

        }

        private Queue<int> queue;

    }

Complexity: O(n) for Push and O(1) for rest of the operations.