Stacks and Queues

Stacks and Queues can be used as auxiliary data structures to solve a large set of problems.

Usually, you can use them while iterating over a sequence to store intermediate values that you can use later to compute some results.

Although very similar, there are a few differences between the two:

1. Stacks follow the LIFO principle, which means Last In First Out. The last element added (push) to the stack will be the first one to be removed (pop). A classic example that I remember from high school (a long time ago 🥲) is the stack of plates: if you add one at the top, you have to remove it first, before reaching the ones at the bottom.
2. Queues follow the FIFO principle, which means First In First Out. The first element added (enqueue) to the queue will be the the first one to be removed (dequeue). Think of a queue at the post office: the first person who arrives will be served first.

The deque object

Before discussing about the Python usage of these two data structures, let me introduce the deque object from the collections container. Deques (pronounced deck) is a generalization of Stacks and Queues and it represents a Double-ended Queue [1].

This object can be used to for both Stacks and Queues.

References

• [1]: https://docs.python.org/3/library/collections.html#deque-objects