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!
Alternatively, a list can be used to represent a queue/stack. However, popping the oldest element of a list is an O(n) operation.
Creating a queue
To create a queue, we'll be using the
A deque can be created by calling its constructor:
You can also initialize the deque with a collection of starting values:
Adding an item to the queueO(1)
When using a deque as a queue, we always want to add to the back. We can do this via the
Removing an item from the queueO(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):
Getting values from the queueO(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. Similarly, you can access the end of the queue with
Creating a stack
Initializing a stack follows the same process as the queue, since we are using the same class.
Like a queue, you can also initialize the stack with values in the same way:
Adding an item to the stackO(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.
Removing an item from the stackO(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).
Getting values from the stackO(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.