InterviewCrunch

Beta

Queue / Stack

Queues and stacks are important to understand for more advanced topics like graph/tree traversal or dynamic programming.

  • Queue - First In First Out (FIFO) returns the oldest entry added to the data structure. Think of a line at a ticket counter as a real life equivalent. The first person who enters the queue is also the first person to leave it. Queues are commonly used in BFS problems.
  • Stack - First In Last Out (FILO) returns the newest entry added the data structure. A good analogy is a stack of pancakes. New pancakes are added to the top, and you also eat from the top. Stacks are commonly used in recursive or reversing problems.

In Python, queue and stack are represented by the same class, the deque. No need to memorize two different classes!

Note

Alternatively, a list can be used to represent a queue/stack. However, popping the oldest element of a list is an O(n) operation.

Queue

Creating a queue

To create a queue, we'll be using the deque.

A deque can be created by calling its constructor:

# Most virtual interviews will already have this imported.
# If not, remember that most higher level data structures
# are in the collections library!
from collections import deque

ticket_line = deque()
print(ticket_line)

You can also initialize the deque with a collection of starting values:

from collections import deque

ticket_line = deque(["#1", "#2", "#3"])
print(ticket_line)

Adding an item to the queue

O(1)

When using a deque as a queue, we always want to add to the back. We can do this via the append() function:

from collections import deque

ticket_line = deque(["#1", "#2", "#3"])
ticket_line.append("#4")
print(ticket_line)

Removing an item from the queue

O(1)

To remove an item from a queue, use popleft() (remember, we want to add from the back of the line and remove from the front):

from collections import deque

ticket_line = deque(["#1", "#2", "#3"])
ticket_line.popleft()
print(ticket_line)

Getting values from the queue

O(1)

When you do a popleft(), it returns the value as well. This is how you get the item at the front of the queue. If you want to check what is in the front of the queue without popping, you can access the first element using ticket_line[0]. Similarly, you can access the end of the queue with ticket_line[-1].

from collections import deque

ticket_line = deque(["#1", "#2", "#3"])
first_element = ticket_line.popleft()
print(ticket_line)
print(first_element)
print(ticket_line[0])
print(ticket_line[-1])

Stack

Creating a stack

Initializing a stack follows the same process as the queue, since we are using the same class.

from collections import deque

pancake_stack = deque()
print(pancake_stack)

Like a queue, you can also initialize the stack with values in the same way:

from collections import deque

pancake_stack = deque(["bottom", "middle", "top"])
print(pancake_stack)

Adding an item to the stack

O(1)

We want to add items to the "top" of the stack. To do this we will assume that the top of the stack is the end of the deque.

from collections import deque
pancake_stack = deque(["bottom", "middle", "top"])
pancake_stack.append("top_top")
print(pancake_stack)

Removing an item from the stack

O(1)

To remove an item from a stack, use pop(). This is the only difference between a stack and a queue (the problems that they are used in are very different though).

from collections import deque

pancake_stack = deque(["bottom", "middle", "top"])
pancake_stack.pop()
print(pancake_stack)

Getting values from the stack

O(1)

Like the queue, we use pop() to get the value at the top. To check what is in the top of the stack without popping, just access the last element in the deque.

from collections import deque

pancake_stack = deque(["bottom", "middle", "top"])
top_element = pancake_stack.pop()
print(pancake_stack)
print(top_element)
print(pancake_stack[-1])
PrevPython For Interviews: Advanced Data Structures
NextTree