How to implement a queue using two stacks?

Question

Suppose we have two stacks and no other temporary variable.

Is to possible to "construct" a queue data structure using only the two stacks?

Solution 1

Keep 2 stacks, let's call them inbox and outbox.

Enqueue:

• Push the new element onto inbox

Dequeue:

• If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox

• Pop and return the top element from outbox

Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.

Here's an implementation in Java:

public class Queue<E>
{

    private Stack<E> inbox = new Stack<E>();
    private Stack<E> outbox = new Stack<E>();

    public void queue(E item) {
        inbox.push(item);
    }

    public E dequeue() {
        if (outbox.isEmpty()) {
            while (!inbox.isEmpty()) {
               outbox.push(inbox.pop());
            }
        }
        return outbox.pop();
    }

}

Solution 2

A - How To Reverse A Stack

To understand how to construct a queue using two stacks, you should understand how to reverse a stack crystal clear. Remember how stack works, it is very similar to the dish stack on your kitchen. The last washed dish will be on the top of the clean stack, which is called as Last In First Out (LIFO) in computer science.

Lets imagine our stack like a bottle as below;

If we push integers 1,2,3 respectively, then 3 will be on the top of the stack. Because 1 will be pushed first, then 2 will be put on the top of 1. Lastly, 3 will be put on the top of the stack and latest state of our stack represented as a bottle will be as below;

Now we have our stack represented as a bottle is populated with values 3,2,1. And we want to reverse the stack so that the top element of the stack will be 1 and bottom element of the stack will be 3. What we can do ? We can take the bottle and hold it upside down so that all the values should reverse in order ?

Yes we can do that, but that's a bottle. To do the same process, we need to have a second stack that which is going to store the first stack elements in reverse order. Let's put our populated stack to the left and our new empty stack to the right. To reverse the order of the elements, we are going to pop each element from left stack, and push them to the right stack. You can see what happens as we do so on the image below;

So we know how to reverse a stack.

B - Using Two Stacks As A Queue

On previous part, I've explained how can we reverse the order of stack elements. This was important, because if we push and pop elements to the stack, the output will be exactly in reverse order of a queue. Thinking on an example, let's push the array of integers {1, 2, 3, 4, 5} to a stack. If we pop the elements and print them until the stack is empty, we will get the array in the reverse order of pushing order, which will be {5, 4, 3, 2, 1} Remember that for the same input, if we dequeue the queue until the queue is empty, the output will be {1, 2, 3, 4, 5}. So it is obvious that for the same input order of elements, output of the queue is exactly reverse of the output of a stack. As we know how to reverse a stack using an extra stack, we can construct a queue using two stacks.

Our queue model will consist of two stacks. One stack will be used for enqueue operation (stack #1 on the left, will be called as Input Stack), another stack will be used for the dequeue operation (stack #2 on the right, will be called as Output Stack). Check out the image below;

Our pseudo-code is as below;

---

Enqueue Operation

Push every input element to the Input Stack

Dequeue Operation

If ( Output Stack is Empty)
    pop every element in the Input Stack
    and push them to the Output Stack until Input Stack is Empty

pop from Output Stack

---

Let's enqueue the integers {1, 2, 3} respectively. Integers will be pushed on the Input Stack (Stack #1) which is located on the left;

Then what will happen if we execute a dequeue operation? Whenever a dequeue operation is executed, queue is going to check if the Output Stack is empty or not(see the pseudo-code above) If the Output Stack is empty, then the Input Stack is going to be extracted on the output so the elements of Input Stack will be reversed. Before returning a value, the state of the queue will be as below;

Check out the order of elements in the Output Stack (Stack #2). It's obvious that we can pop the elements from the Output Stack so that the output will be same as if we dequeued from a queue. Thus, if we execute two dequeue operations, first we will get {1, 2} respectively. Then element 3 will be the only element of the Output Stack, and the Input Stack will be empty. If we enqueue the elements 4 and 5, then the state of the queue will be as follows;

Now the Output Stack is not empty, and if we execute a dequeue operation, only 3 will be popped out from the Output Stack. Then the state will be seen as below;

Again, if we execute two more dequeue operations, on the first dequeue operation, queue will check if the Output Stack is empty, which is true. Then pop out the elements of the Input Stack and push them to the Output Stack unti the Input Stack is empty, then the state of the Queue will be as below;

Easy to see, the output of the two dequeue operations will be {4, 5}

C - Implementation Of Queue Constructed with Two Stacks

Here is an implementation in Java. I'm not going to use the existing implementation of Stack so the example here is going to reinvent the wheel;

C - 1) MyStack class : A Simple Stack Implementation

public class MyStack<T> {

    // inner generic Node class
    private class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    private Node<T> head;
    private int size;

    public void push(T e) {
        Node<T> newElem = new Node(e);

        if(head == null) {
            head = newElem;
        } else {
            newElem.next = head;
            head = newElem;     // new elem on the top of the stack
        }

        size++;
    }

    public T pop() {
        if(head == null)
            return null;

        T elem = head.data;
        head = head.next;   // top of the stack is head.next

        size--;

        return elem;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void printStack() {
        System.out.print("Stack: ");

        if(size == 0)
            System.out.print("Empty !");
        else
            for(Node<T> temp = head; temp != null; temp = temp.next)
                System.out.printf("%s ", temp.data);

        System.out.printf("\n");
    }
}

C - 2) MyQueue class : Queue Implementation Using Two Stacks

public class MyQueue<T> {

    private MyStack<T> inputStack;      // for enqueue
    private MyStack<T> outputStack;     // for dequeue
    private int size;

    public MyQueue() {
        inputStack = new MyStack<>();
        outputStack = new MyStack<>();
    }

    public void enqueue(T e) {
        inputStack.push(e);
        size++;
    }

    public T dequeue() {
        // fill out all the Input if output stack is empty
        if(outputStack.isEmpty())
            while(!inputStack.isEmpty())
                outputStack.push(inputStack.pop());

        T temp = null;
        if(!outputStack.isEmpty()) {
            temp = outputStack.pop();
            size--;
        }

        return temp;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

}

C - 3) Demo Code

public class TestMyQueue {

    public static void main(String[] args) {
        MyQueue<Integer> queue = new MyQueue<>();

        // enqueue integers 1..3
        for(int i = 1; i <= 3; i++)
            queue.enqueue(i);

        // execute 2 dequeue operations 
        for(int i = 0; i < 2; i++)
            System.out.println("Dequeued: " + queue.dequeue());

        // enqueue integers 4..5
        for(int i = 4; i <= 5; i++)
            queue.enqueue(i);

        // dequeue the rest
        while(!queue.isEmpty())
            System.out.println("Dequeued: " + queue.dequeue());
    }

}

C - 4) Sample Output

Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5

Solution 3

You can even simulate a queue using only one stack. The second (temporary) stack can be simulated by the call stack of recursive calls to the insert method.

The principle stays the same when inserting a new element into the queue:

• You need to transfer elements from one stack to another temporary stack, to reverse their order.
• Then push the new element to be inserted, onto the temporary stack
• Then transfer the elements back to the original stack
• The new element will be on the bottom of the stack, and the oldest element is on top (first to be popped)

A Queue class using only one Stack, would be as follows:

public class SimulatedQueue<E> {
    private java.util.Stack<E> stack = new java.util.Stack<E>();

    public void insert(E elem) {
        if (!stack.empty()) {
            E topElem = stack.pop();
            insert(elem);
            stack.push(topElem);
        }
        else
            stack.push(elem);
    }

    public E remove() {
        return stack.pop();
    }
}

Solution 4

The time complexities would be worse, though. A good queue implementation does everything in constant time.

Edit

Not sure why my answer has been downvoted here. If we program, we care about time complexity, and using two standard stacks to make a queue is inefficient. It's a very valid and relevant point. If someone else feels the need to downvote this more, I would be interested to know why.

A little more detail: on why using two stacks is worse than just a queue: if you use two stacks, and someone calls dequeue while the outbox is empty, you need linear time to get to the bottom of the inbox (as you can see in Dave's code).

You can implement a queue as a singly-linked list (each element points to the next-inserted element), keeping an extra pointer to the last-inserted element for pushes (or making it a cyclic list). Implementing queue and dequeue on this data structure is very easy to do in constant time. That's worst-case constant time, not amortized. And, as the comments seem to ask for this clarification, worst-case constant time is strictly better than amortized constant time.

Solution 5

Let queue to be implemented be q and stacks used to implement q be stack1 and stack2.

q can be implemented in two ways:

Method 1 (By making enQueue operation costly)

This method makes sure that newly entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.

enQueue(q, x)
1) While stack1 is not empty, push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it.

Method 2 (By making deQueue operation costly)

In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.

enQueue(q,  x)
 1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
 1) If both stacks are empty then error.
 2) If stack2 is empty
   While stack1 is not empty, push everything from stack1 to stack2.
 3) Pop the element from stack2 and return it.

Method 2 is definitely better than method 1. Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty.

View more solutions

Comments

[Daniel Spiewak]

Not in the average case. Brian's answer describes a queue which would have amortized constant enqueue and dequeue operations.

[Tyler]

That's true. You have average case & amortized time complexity the same. But the default is usually worst-case per-operation, and this is O(n) where n is the current size of the structure.

[Daniel Spiewak]

Worst case can also be amortized. For example, mutable dynamic arrays (vectors) are usually considered to have constant insertion time, even though an expensive resize-and-copy operation is required every so often.

[Tyler]

"Worst-case" and "amortized" are two different types of time complexity. It doesn't make sense to say that "worst-case can be amortized" -- if you could make the worst-case = the amortized, then this would be a significant improvement; you would just talk about worst-case, with no averaging.

[Tyler]

The worst-case time complexity is still O(n). I persist in saying this because I hope no students out there (this sounds like a homework/educational question) think this is an acceptable way to implement a queue.

[Dave L.]

It is true that the worst-case time for a single pop operation is O(n) (where n is the current size of the queue). However, the worst-case time for a sequence of n queue operations is also O(n), giving us the amortized constant time. I wouldn't implement a queue this way, but it's not that bad.

[Brian R. Bondy]

Good point, but I wasn't trying to optimize as much as I was trying to write a solution that can be easily understood while answering the question " Is to possible".

[Roozbeh15]

If outbox is not empty, do you have to empty it out? Assuming we have new elements coming in all the time continuously?

[Flash]

@Rooozbeh15 : No need to empty the outbox. The dequeue operation will take the element from the outbox only. The inbox is used for accomodating the incoming elements.

[Antti Huima]

Maybe the code looks elegant but it is very inefficient (O(n**2) insert) and it still has two stacks, one in the heap and one in the call stack, as @pythonquick points out. For a non-recursive algorithm, you can always grab one "extra" stack from the call stack in languages supporting recursion.

[smandape]

@Dave L.: I am a beginner in Computers. Can you explain how the worst-case time complexity for enqueue is O(n). I thought it to be O(1), constant time. This will be of great help to me.

[Dave L.]

For enqueue, it's always a single push operation, which should be O(1). It's a dequeue operation that can take O(n) in the worst case.

[Thomas Ahle]

@Tyler If your stack is array based, as most are, you will always get O(n) worst case for a single operation.

[Tyler]

@ThomasAhle You can easily implement an O(1) worst-case stack with a linked list. I'm pretty sure this is how the C++ STL's stack is implemented. The deque is the default backing structure for an STL stack, and I think they use a linked list for deque, not an array.

[Thomas Ahle]

@Tyler: Check sgi.com/tech/stl/Deque.html . Deque "suports random access to elements" . Hence both deque and stack are array based. This is because it gives you better locality of reference and hence is faster in practice.

[Tyler]

@ThomasAhle Ok, I looked up the STL deque implementation, and it is a dynamically sized circular array. You get that point. But my main point still holds: stacks can be implemented with O(1) worst-case push/pop functions via linked list. O(1) worst-case is strictly better than O(1) amortized. There's no room for debate. If you want fast push/pops and nothing else, which is what a stack does, then there's no reason to forgo worst-case constant times. For the record, I was misled by this page's evidence that a deque has O(1) push/pop's: codeproject.com/KB/stl/vector_vs_deque.aspx

[Thomas Ahle]

@Tyler: I'm impressed with the speed of the deque in your referred study. However when methods have equal or nearly equal big-oh values as here, the only way to compare them is testing individual implementations. At least in java I found that LinkedList uses 3.75 times longer on appending on average, and 3.23 in median, than ArrayList.

[Devon_C_Miller]

Originally posted as an answer by @Bajaj: There is a flaw in the solution suggested by Dave L. [stackoverflow.com/a/69436/1465918]. A deadlock scenario could occur or order of elements could fail during concurrent DeQueue and Enqueue operation. As each Dequeue involves popping from mainStack and pushing it into second Stack. and if new element added during this operation, the location of the new item might not retain last position

[Dave L.]

@Devon_C_Miller Indeed, the example in Java is not thread safe, just like most of the other collections in Java. As with any such class, if you want to use it in a multithreaded context, be sure to use synchronization or some other appropriate tool.

[supercat]

I'm not sure what you mean by O(1) worst-case being "strictly better" than a combination of O(1) average case and O(n) worst-case. Constant scaling factors matter. A data structure which, if it contains N items, may need to be repacked after N operations at a time of N microseconds, and otherwise takes one microsecond per operation, may be far more useful than one which takes a millisecond for each operation, even if the data size will expand to millions of items (thus implying that some individual operations would take multiple seconds).

[Tyler]

@supercat, you're right that some algorithms may have a slower time complexity yet may be faster for small-sized inputs. My statement was about worst-case vs amortized time complexity in general. If all you know is that one alg is O(f(n)) worst-case and the other is O(f(n)) amortized, then the worst-case analysis gives you more information. This is relevant to queues. Suppose you're writing a realtime video game, where a constant 1ms per queue-op is ok, but even an occasional slow queue-op will appear as lag to the user. Then you care about worst-case performance, and this is just one example.

[supercat]

@Tyler: My point wasn't about small-size inputs. My point was about big batches of inputs. A typical amortized-constant-time algorithms will be able to guarantee that the total cost to perform M consecutive operations on a data set of size N will be O(M)+O(N). If N is O(M) [meaning the number of operations to be performed is at least a constant fraction of the data set size], then O(M)+O(N) will be O(M). The fact that some individual operations may take time O(N) won't adversely affect the time to perform M of them. In practical terms...

[supercat]

...it's often possible for amortized-time algorithms to guarantee that provided one performs some number operations on a data set of a particular size (the number depending upon the size), the time saved on the operations which are processed quickly will outweigh the extra time taken by those which do not. If one doesn't care about the time required to process individual operations, but only groups which are larger than that size, the amortized-time operation may be strictly better.

[Newtang]

I'm confused by something. If I do this: a) queue 1,2,3 b) dequeue (returning 1). c) queue 4, 5 d) dequeue Then, I get back 4, not 2, which is what I would expect from a queue. Am I missing something?

[Dave L.]

@Newtang a) queue 1,2,3 => Inbox[3,2,1]/Outbox[]. b) dequeue. outbox is empty, so refill => Inbox[]/Outbox[1,2,3]. Pop from outbox, return 1 => Inbox[]/Outbox[2,3]. c) queue 4,5 => Inbox[5,4]/Outbox[2,3]. d) dequeue. outbox is not empty, so pop from outbox, return 2 => Inbox[5,4]/Outbox[3]. Does that make more sense?

[ying]

@Tyler: why is your proposal the worst-case constant time, not normal time?

[ying]

@supercat: can you elaborate more why 2-stack approach is better than Tyler's approach?

[supercat]

@ying: Forward-linked-list queues can be useful in some scenarios, but Tyler's answer seemed to derisively suggest that one should without exception always judge algorithms by their worst-case performance. In many cases, double-stack queues may be just as good as anything else from a performance standpoint, especially if what one cares about is the total time an application spends putting objects into a queue and taking them out.

[ying]

@supercat: I understand the point about worst time vs avg time. But my understanding is double-stack queue need to copy/move element between stacks to achieve FIFO while linked list doesn't need copying at all and is much simpler. So what's the gain for double-stack queue? Some ppl (stackoverflow.com/a/8357639/1294552) mentioned immutability and thread-safe, but linked list can also achieve it. Can you explain under what condition to choose double-stack queue rather than linkedlist queue? How to choose? Thanks.

[supercat]

@ying: Adding an item to a lock-free stack is simple: do {newItem.next = firstLink;} while CompareExchange(firstLink, newItem, newItem.next); The amount of contention in multi-processor scenarios is a function of the amount of code within the CompareExchange loop. All lock-free linked-list approaches I know of have more complicated producer loop. Further, if one looks at the total amount of work that will have to be done on each item in the two-stack approach, from the time it enters to the time it leaves, it's pretty small.

[ying]

@supercat: This question seems helpful: stackoverflow.com/questions/2050120/…

[ying]

@supercat: how to impl lock free atomic copying elements from one stack to the other?

[supercat]

@ying: Note that in common implementations of the two-stack approach, each stack is a linked list; the difference is that when the list on on the "add items" side each links points to the previous item rather than the next. When the reader's stack gets try and it has to grab the writer's stack, the reversal can be done in place with a simple loop. The behavior is equivalent to popping all items off one stack and pushing on the other, but the implementation can be much faster. In some cases, building the queue with forward-pointers may have an advantage...

[supercat]

@ying: ...in that each item will have to be accessed twice in rapid succession (when writing it, and when writing the next item) and then once much later (when reading), while in a double-stack queue the three accesses would be more disjoint in time; thus, the latter approach may have three cache misses in cases where the former would only have two. Note that the reversal need not be atomic in the many-writers one-reader case, since the reversal would be done by the (only) reader thread.

[spiralmoon]

I remember this problem appeared in the book Crack the Coding Interview

[Lionel Parreaux]

@antti.huima And would you explain how this could be a quadratic insert?! From what I understand, insert does n pop and n push operations, so it's a perfectly linear O(n) algorithm.

[Ankit Kumar]

@LP_ it takes quadratic time O(n^2) to insert n items in the queue using the above data structure. the sum (1 + 2 + 4 + 8 + .... + 2(n-1)) results in ~O(n^2). I hope you get the point.

[Lionel Parreaux]

@antti.huima You were talking about the complexity of the insert function (you said "O(n2) insert" -- you probably meant "O(n2) fill"). By convention, "the complexity insert" is the time one insertion takes, which is here linear in the number of elements already present. If we talked in the time needed to insert n items, we would say a hashtable has linear insert. Which is not the case.

[Binita Bharati]

What happens if outbox is not empty ?

[Binita Bharati]

Yes, you are right. I wonder, how you got so many down-votes. I have upvoted your answer

[Dave L.]

@BinitaBharati: Then a dequeue operation will simply pop the top item off outbox.

[theGreenCabbage]

None of the solutions I understood except for your method 2. I love the way you explain it with the enqueue and dequeue method with the steps.

[sat]

google.com/…

[melpomene]

You're using arrays here. I don't see where your stacks are.

[melpomene]

This code is inefficient (unnecessary copying) and broken: if (stack2 != null) is always true because stack2 is instantiated in the constructor.

[melpomene]

This code is functionally identical to the answer by Dave L. It adds nothing new, not even an explanation.

[John Leidegren]

@melpomene OK, if you take a closer look you'll notice that the only operations that I'm performing is adding/removing of the last element in the array. In other words, pushing and popping. For all intent and purposes these are stacks but implemented using arrays.

[John Leidegren]

@melpomene Actually, that's only half right, I am assuming doubled ended stacks. I am allowing the stack to be modified in a non standard way from bottom up under certain conditions.

[realPK]

It adds isEmpty() and size() methods along with basic exception handling. I will edit to add explanation.

[melpomene]

No one asked for those extra methods, and they're trivial (one line each): return inbox.isEmpty() && outbox.isEmpty() and return inbox.size() + outbox.size(), respectively. Dave L.'s code already throws an exception when you dequeue from an empty queue. The original question wasn't even about Java; it was about data structures / algorithms in general. The Java implementation was just an additional illustration.

[Kemal Tezer Dilsiz]

This is a great source for people looking to understand how to build queue from two stacks, the diagrams most definitely helped me more than reading Dave's answer.

[UKMonkey]

You're essentially using the stack, as a stack. This means that if a large number of items are in the stack, you can end up with a stack overflow - it's almost like the solution was designed for this site!

[realPK]

@melpomene: Its not about methods being trivial but of need. Queue interface in Java extends those methods from Collection interface because they are needed.

[melpomene]

@KemalTezerDilsiz What diagrams? Did you comment on the wrong answer?

[rd22]

@DaveL. The complexity of the above approach for enqueue operation is O(1) and for for the dequeue is O(1) is there a way to reduce this complexity? I was asked this at an interview.

[Dave L.]

@rd22 Actually, the worst case time complexity for dequeue is O(n), it's just the amortized time that is O(1). It's not possible to do better than this using only stacks.

[Severus Tux]

@DaveL. Could you please help me understand how amortized constant time is O(1) ? i.e, one D-queue where current size is n would be O(n), hence continues n De-queues would be (n)+(n-1)+(n-2)+...+1 = n(n+1)/2 i.e, O(n^2) , Therefore I think amortized constant time is O(n)

[Dave L.]

@SeverusTux The worst case for a single Dequeue is O(n), which is true. However, that only happens if there outbox is empty and there are O(n) items in the inbox. In that case, the total cost for each of the next set of operations is O(1) since they each only need to pop the top item off the outbox. So that gives O(n) + n * O(n) which equals O(n) + O(n) which is still just O(n). In other words, any time you have an expensive dequeue, it's guaranteed to be followed by many cheap dequeues, so it averages out fine.

[Severus Tux]

Oh.. got it. Thanks. You mean O(n) + n * O( 1 ) i guess.

[Dave L.]

Oops! Yes, that's what I meant.

[Alexander]

This is bugged. If you enqueue more elements after dequeueing, you'll put them in stack1. When you go to dequeue again, you'll move them items into stack2, putting them ahead of what was already there.

[Dave L.]

@user355834 Need more specifics. A circular linked list is another structure that can efficiently implement the First In First Out semantics of a queue, but can also support other operations such as removing from the back of the queue. You could do other things with the stacks as well, but it really gets to the details of what operations you want to do and how efficient they are. Generally outside the scope of this exercise.

[Dave L.]

@User355834 I'd argue with the assertion that a circular linked list can be implemented via queue. A circular linked list is a structure with a set of nodes, each pointing to the next, and the last pointing back to the first. It can be used to implement a queue, but it doesn't really make sense to try to use a queue to implement a circular linked list.

[greybeard]

I see one non-comment. I don't see a single stack. What question is this post supposed to answer?

[greybeard]

Without a description of the number of operations necessary, this answer is not useful.

[greybeard]

Where are the queue operations, say, enqueue(T value) and T dequeue()? Is it necessary to instantiate Nodes in pop()? Without a description of the number of operations necessary, this answer is not useful.

[greybeard]

@Alexander: you'll move them items into stack2, putting them ahead of what was already there if and only if this.stack2.size() === 0, putting those elements before - nothing.

[greybeard]

Below is the explanation of the problem promises, promises - 1., 2., and 3. look a stab at describing a solution. Why s1 when there is neither s0 nor s2? There is an else following a return. There is an opening { with no matching }.

[Alexander]

Haha I wrote that 3 years ago (almost to the date), and now I can't understand what I meant