The world’s leading publication for data science, AI, and ML professionals.

Data Structures and Algorithms With Python – Learn Stacks, Queues, and Deques in 10 Minutes

Master Data Structures and Algorithms in Python. Source code included.

Photo by Rohan G on Unsplash
Photo by Rohan G on Unsplash

Today’s article is all about the introduction to data structures and algorithms with Python. We’ll start simple, and in the process, you’ll learn about three fundamental data structures – stacks, queues, and deques.

Also, you’ll learn how to implement them from scratch. Let’s start!

The article is structured as follows:

  • Stacks
  • Queues
  • Deques
  • Final Words

Stacks

Let’s start with the simplest one. You can think of stacks as ordered arrays in which both addition and removal of items happen at the same end. Stacks are based on the LIFO principle (last-in-first-out). It means that the most recent item is the one to be removed first.

Let’s take a look at an example diagram:

Image 1 - Stack diagram (source: computersciencewiki.org)
Image 1 – Stack diagram (source: computersciencewiki.org)

As you can see, the LIFO principle is at the essence of a stack data structure. Items at the start of the stack (known as base) are in the stack the longest.

Stack example: Back button in a web browser. As you navigate through the pages and want to go back, the most recent website is closed, or poped-out of a stack.

Implementation-wise, the Stack class will need three methods (plus the constructor):

  • push(value) -> None – adds the value to the stack
  • pop() -> Any – removes the most recent value from the stack
  • is_empty() -> bool – checks to see if there are items in the stack

Here’s a code to implement stack from scratch in Python:

Let’s make a couple of tests:

As you can see, the stack data structure works as advertised. Let’s explore the next one.


Queues

Unlike stacks, adding items to queues takes place at the beginning of the array (index position 0), and the removal happens on the opposite end. This principle is better known as FIFO (first-in-first-out) principle. Therefore, the most recently added item must wait for the other items to be processed.

Let’s take a look at an example diagram:

Image 2 - Queue diagram (source: computersciencewiki.org)
Image 2 – Queue diagram (source: computersciencewiki.org)

One look at the above diagram should ring some bells, as it looks familiar to everyday situations.

Queue example: Basically any line you stand at – from grocery stores, cafeterias, to doctors’ office – the first person in the line is first to get out of the queue.

Implementation-wise, the Queue class will need four methods (plus the constructor):

  • enqueue(value) -> None – adds a new item to the rear of the queue
  • dequeue() -> Any – removes the first item in the queue
  • is_empty() -> bool— checks to see if there are items in the queue
  • peek() -> Any – returns the first item in the queue but doesn’t remove it

Here’s a code to implement queue from scratch in Python:

Let’s make a couple of tests:

And that’s all there is to it. You’re free to implement additional methods or perform further checks, but the ones from the script should be enough.


Deques

A deque data structure is quite similar to the previous two but doesn’t require either LIFO or FIFO orderings. Unlike stacks and queues, deques have two ends, and you can add and remove items to either end.

Let’s take a look at an example diagram:

Image 3 - Deque diagram (source: programiz.org)
Image 3 – Deque diagram (source: programiz.org)

To summarize, the deque is a hybrid data structure that implements all functionalities from stacks and queues.

Implementation-wise, the Deque class will need five methods (plus the constructor):

  • add_front(value: Any) -> None – adds a new item to the front of a deque
  • add_rear(value: Any) -> None – adds a new item to the end of a deque
  • remove_front() -> Any – returns the first item from the deque and removes it
  • remove_rear() -> Any – returns the last item from the deque and removes it
  • is_empty() -> bool – checks to see if there are items in the queue

Here’s a code to implement queue from scratch in Python:

Let’s make a couple of tests:

And that’s all about deques! Let’s wrap things up next.


Final Words

Today you’ve learned three basic data structures – stacks, queues, and decks – and implemented them from scratch in Python. These can come in handy for solving different Programming tasks, depending on the logic you’re trying to implement.

Also, implementing these from scratch or performing some operations based on them can sometimes be a coding interview question, so it can’t hurt to learn them properly.

Stay tuned to the rest of the Data Structures and Algorithms with Python series, where we’ll explore different topics such as linked lists, recursion, trees, searching, sorting, and many others.

Thanks for reading.


Loved the article? Become a Medium member to continue learning without limits. I’ll receive a portion of your membership fee if you use the following link, with no extra cost to you.

Join Medium with my referral link – Dario Radečić


Learn More


Stay Connected


Related Articles