Queue / Stack
A deque (you say it like "deck") is a list you can add to and remove from at both ends in O(1) time. Here's everything you'll use in an interview:
That one class covers both queues and stacks. The rest of this page shows how each one works, and when a deque is better than a plain list.
Queue vs stack
You'll need queues and stacks for bigger topics like graph and tree traversal. The only difference between them is which end you take items from.
Queue: First In, First Out (FIFO). A queue gives you back the oldest item first. Think of a line at a ticket counter. The first person to get in line is the first person to leave it. You'll use queues a lot in breadth-first search.
Stack: Last In, First Out (LIFO). A stack gives you back the newest item first. Think of a stack of pancakes. You add new pancakes to the top, and you eat from the top too. Stacks show up in problems about recursion, reversing things, and matching pairs like Valid Parenthesis.
In Python, you use the same class for both: the deque. You don't have to memorize two different classes!
deque vs list: why not just use a list?
A list is fast at its right end and slow at its left end. When you call list.pop(0), Python has to shift every other item over by one, so it's O(n). A deque doesn't store its items that way, so popleft() is O(1) no matter how big it gets:
This matters most in breadth-first search. BFS pops from the front of the queue once for every node it visits. With list.pop(0), each of those pops is O(n), and your O(V + E) search quietly turns into something closer to O(V²). Interviewers notice this one.
For a stack, a plain list is totally fine. append() and pop() both work on the right end, so they're O(1) either way. A list is also faster when you need to index into the middle, since that's O(n) on a deque.
Note
Don't mix this up with queue.Queue. That class is built for passing work between threads, so it's slower and you don't need it in an interview. Use collections.deque.
Queue
Creating a queue
To make a queue, call the deque constructor:
You can also start the deque off with some values:
Adding an item to the queue
O(1)In a queue, new items always go to the back of the line. You do that with append():
Removing an item from the queue
O(1)To take an item off the queue, use popleft(). Remember, people join at the back of the line and leave from the front:
Peeking at the front of the queue
O(1)popleft() also returns the item it removed, so that's how you get the front of the queue. If you just want to look at the front without removing it, use ticket_line[0]. The back of the queue is ticket_line[-1].
Note
Indexing or popping an empty deque raises an IndexError. In a loop, check while ticket_line: before you pop.
Stack
Creating a stack
You make a stack the same way you make a queue, since it's the same class.
You can start a stack off with values, too:
Adding an item to the stack
O(1)New items go on the "top" of the stack. We'll treat the right end of the deque as the top, so you add items with append():
Removing an item from the stack
O(1)To take an item off a stack, use pop(). That's the only difference in code between a stack and a queue. The problems you use them for are very different, though.
Peeking at the top of the stack
O(1)Just like with the queue, pop() returns the item it removed. To look at the top without removing it, use pancake_stack[-1].
deque(maxlen=k): you probably won't need this in an interview, but it's handy to know. If you pass maxlen, the deque never grows past that size. Once it's full, each new item pushes the oldest one out the other end. That gives you a fixed-size sliding window for free: