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:
You can also initialize the deque with a collection of starting values:
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:
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):
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].
Stack
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 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.
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).
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.