Implement A Queue With Two Stacks (Practice Interview Question)

You only have 3 free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

You're in!

Implement a queue ↴

Quick reference

Worst Case

space $O(n)$

enqueue $O(1)$

dequeue $O(1)$

peek $O(1)$

A queue stores items in a first-in, first-out (FIFO) order.

Picture a queue like the line outside a busy restaurant. First come, first served.

Strengths:

Fast operations. All queue operations take $O(1)$ time.

Uses

Breadth-first search uses a queue to keep track of the nodes to visit next.

Printers use queues to manage jobs—jobs get printed in the order they're submitted.

Web servers use queues to manage requests—page requests get fulfilled in the order they're received.

Processes wait in the CPU scheduler's queue for their turn to run.

Implementation

Queues are easy to implement with linked lists:

To enqueue, insert at the tail of the linked list.

To dequeue, remove at the head of the linked list.

You could implement a queue with an array or dynamic array, but it would get kinda messy. Try drawing it out. You'll notice that you'd need to build out a "scoot over" or "re-center" operation that automatically fires when your queue items hit the bottom edge of the array.

	Worst Case
space	$O(n)$
enqueue	$O(1)$
dequeue	$O(1)$
peek	$O(1)$

	Worst Case
space	$O(n)$
push	$O(1)$
pop	$O(1)$
peek	$O(1)$

	Stack Push	Stack Pop
Linked Lists	insert at head	remove at head
Dynamic Arrays	append	remove last element

with 2 stacks. ↴

Quick reference

Worst Case

space $O(n)$

push $O(1)$

pop $O(1)$

peek $O(1)$

A stack stores items in a last-in, first-out (LIFO) order.

Picture a pile of dirty plates in your sink. As you add more plates, you bury the old ones further down. When you take a plate off the top to wash it, you're taking the last plate you put in. "Last in, first out."

Strengths:

Fast operations. All stack operations take $O(1)$ time.

Uses:

The call stack is a stack that tracks function calls in a program. When a function returns, which function do we "pop" back to? The last one that "pushed" a function call.

Depth-first search uses a stack (sometimes the call stack) to keep track of which nodes to visit next.

String parsing—stacks turn out to be useful for several types of string parsing.

Implementation

You can implement a stack with either a linked list or a dynamic array—they both work pretty well:

Stack Push Stack Pop

Linked Lists insert at head remove at head

Dynamic Arrays append remove last element

Your queue should have an enqueue and a dequeue method and it should be "first in first out" (FIFO).

Optimize for the time cost of $m$ calls on your queue. These can be any mix of enqueue and dequeue calls.

Assume you already have a stack implementation and it gives $O(1)$ time push and pop.

Gotchas

We can get $O(m)$ runtime for $m$ calls. Crazy, right?

Breakdown

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Solution

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Complexity

Each enqueue is clearly $O(1)$ time, and so is each dequeue when out_stack has items. Dequeue on an empty out_stack is order of the number of items in in_stack at that moment, which can vary significantly.

Notice that the more expensive a dequeue on an empty out_stack is (that is, the more items we have to move from in_stack to out_stack), the more $O(1)$ -time dequeues off of a non-empty out_stack it wins us in the future. Once items are moved from in_stack to out_stack they just sit there, ready to be dequeued in O(1) time. An item never moves "backwards" in our data structure.

We might guess that this "averages out" so that in a set of $m$ enqueues and dequeues the total cost of all dequeues is actually just $O(m)$ . To check this rigorously, we can use the accounting method, ↴

The accounting method can be used for computing time complexity for things like "the cost of $m$ operations on this data structure."

In the accounting method, you simply look at the time cost incurred by each item passing through the system instead of the time cost of each operation.

counting the time cost per item instead of per enqueue or dequeue.

So let's look at the worst case for a single item, which is the case where it is enqueued and then later dequeued. In this case, the item enters in_stack (costing 1 push), then later moves to out_stack (costing 1 pop and 1 push), then later comes off out_stack to get returned (costing 1 pop).

Each of these 4 pushes and pops is $O(1)$ time. So our total cost per item is $O(1)$ . Our $m$ enqueue and dequeue operations put $m$ or fewer items into the system, giving a total runtime of $O(m)$ .

What We Learned

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Do you have an answer?

Show answer

I have an answer Tell me more

Ready for more?

Check out our full course

You only have 3 free questions left (including this one).

Quick reference

Strengths:

Uses

Implementation

Quick reference

Strengths:

Uses:

Implementation

Gotchas

Breakdown

Start your free trial!

Solution

Start your free trial!

Complexity

What We Learned

Start your free trial!

Ready for more?

Programming interview questions by company:

Programming interview questions by topic: