8) Abstract Data Structures Lesson

Python Queue and Python Stack

6 min to complete · By Martin Breuss

Contents

  1. Introduction
  2. What are Stacks and Queues
    1. Stacks
    2. Queues
  3. Summary: Python Queue and Python Stack
    1. Required Methods for a Stack
    2. Required Methods for a Queue

You might have come across the terms "stack" and "queue" as two common Abstract Data Structures in programming. For any job interview, it won't be a bad thing to know what these are and when you might want to use them. You might even want to know how to build them!

What are Stacks and Queues

Stacks and queues are quite similar to each other. And it turns out that you can use a linked list as the base for implementing either of these two. Let's start by considering their time complexities for common operations:

What Complexity Why
Insert and Delete $`O(1)`$ Stacks and queues define how you can add and remove items. Because you always add and remove from an end of the data structure, these operations work in constant time
Access and Search $`O(n)`$ To search for or access an item, you may need to scan the entire list

These Big-O complexities make both stacks and queues a useful choice for implementing insertion and deletion functionalities. How do the two differ from each other?

Stacks

A stack is a collection where the last item added is the first one you can retrieve from the stack. This is often abbreviated as LIFO, which stands for last in, first out. You can visualize it like a stack of plates:

A stack of colorful plates on a table seen from the side

A stack data structure should implement at least four methods:

  1. Push adds an element to the collection
  2. Pop removes the most recently added element from the collection
  3. Empty checks whether there are any elements in the stack
  4. Peek returns the topmost element without removing it from the stack

You can implement additional methods, for example, a method that returns the total size of the stack or a method that returns True if the stack is full.

Queues

A queue is a collection where the first item added is the first item that gets removed from the queue. This is often abbreviated as FIFO, which stands for first in, first out. You can think of it just like a queue at the cashier's desk in a supermarket, one of the rare ones where no one skips the line:

Graphic of a queue data structure - like a line at the movie theater - first in, first out

A queue data structure should implement at least the following methods:

  1. Enqueue adds an element to the back of the collection.
  2. Dequeue removes and returns the element at the front of the queue.
  3. Empty returns True if the queue is empty, else False.
  4. Peek returns the element at the front of the collection without removing it.

You can implement additional methods, for example, a method that returns the total size of the queue or a method that returns True if the queue is full.

Colorful illustration of a light bulb

Addition Resources

In the next lesson, you'll build a custom queue in Python to continue to train your understanding of Abstract Data Structures.

Summary: Python Queue and Python Stack

  • Stacks and Queues are very similar to each other
  • Stacks are a collection where the last item added is the first one you can retrieve from the stack
  • LIFO stands for last in, first out
  • Queues are a collection where the first item added is the first item that gets removed from the queue
  • FIFO stands for first in, first out

Required Methods for a Stack

  1. Push $`0(1)`$
  2. Pop $`0(1)`$
  3. Empty $`0(1)`$
  4. Peek $`0(1)`$

Required Methods for a Queue

  1. Enqueue $`0(1)`$
  2. Dequeue $`0(1)`$
  3. Empty $`0(1)`$
  4. Peek $`0(1)`$
Previous Next → How to Build a Python Queue