Implement a Queue using 2 Stacks

Question

Tim · Accepted Answer

Here is an idea:


    public class StacksQueue
    {
        private readonly Stack stack1 = new Stack();
        private readonly Stack stack2 = new Stack();
        private Stack dequeueStack;
        private Stack queueStack;

        private Stack secondaryStack
        {
            get
            {
                if (object.ReferenceEquals(queueStack, stack1))
                {
                    return stack2;
                }
                else
                {
                    return stack1;
                }
            }
        }

        public StacksQueue()
        {
            queueStack = stack1;
        }

        public void Queue(T item)
        {
            int count = 0;
            while (queueStack.Count > 0)
            {
                secondaryStack.Push(queueStack.Pop());
                count++;
            }

            queueStack.Push(item);

            for (int i = 0; i < count; i++)
            {
                queueStack.Push(secondaryStack.Pop());
            }

            if (dequeueStack == null)
            {
                dequeueStack = queueStack;
            }

            queueStack = secondaryStack;
        }

        public T Dequeue()
        {
            if (dequeueStack == null)
            {
                throw new InvalidOperationException("Trying to dequeue from queue which is empty");
            }

            T result = dequeueStack.Pop();

            if (object.ReferenceEquals(dequeueStack, stack1))
            {
                dequeueStack = stack2;
            }
            else
            {
                dequeueStack = stack1;
            }

            if (dequeueStack.Count == 0)
            {
                dequeueStack = null;
            }

            return result;
        }
    }

Bearfoot · Answer

Hi, here is a smart solution in java based on shan.phreak solution : 

class Queue {

        Stack stack1 = new Stack();
        Stack stack2 = new Stack();

        public void push(Integer value){
            while (!stack2.isEmpty()){
                stack1.push(stack2.pop());
            }
            stack1.push(value);
        }

        public Integer dequeue(){
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }

Ashritha · Answer

class stack2queue():
    def __init__(self):
        self.instack = []
        self.outstack =[]
    def enqueue(self, item):
        return self.instack.append(item)

    def dequeue(self):
        if not  self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())
        return self.outstack.pop()

a = stack2queue()
a.enqueue(0)
a.enqueue(1)
a.enqueue(2)
a.enqueue(3)
a.enqueue(4)


print(a.dequeue())
print(a.dequeue())
print(a.dequeue())

shan.phreak · Answer

Until the first de-queue operation, keep pushing one of the stacks, say stack1, for every enqueue operation. When you encounter the first dequeue operation, then pop stack1 into stack2. Now, pop stack2, to get the dequeued element. Henceforth, on every dequeue operation, pop stack2, and on every enqueue operation, push stack1. At some point, stack2 might become empty, but this brings you back to the first stage !

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches