Stacks and Queues: Selecting the Ideal Data Structure (Overview)
There are a variety of ways for storing and managing data in your program and the choice of the right data structure has an effect on the readability of your code, ease of writing, and performance. Python has a wide selection of built-in mechanisms that meet most of your data structure needs. This course introduces you to three types of data structures: stacks, queues, and priority queues.
There are multiple types and classes for all of these data structures and this course discusses them and provides information on how to choose the right one.
In this course you’ll learn about:
- How stacks are defined with Last-In/First-Out (LIFO) semantics
- How to use the collections.deque object
- How concurrency will affect your choice
- What are priority queues
- Which data structure methods are thread safe
- How to decide between all of implementations of these data structures
The course is the third part of an ongoing series, exploring how to find the right Data Structure for your projects. The first course is Dictionaries and Arrays: Selecting the Ideal Data Structure and the second course is Records and Sets: Selecting the Ideal Data Structure.
00:00 Welcome to Selecting the Ideal Data Structure: Stacks, Queues, and Priority Queues. My name is Chris and I will be your guide. This course is the third of three parts on how to select the ideal data structure when coding in Python. As you might guess from the title, this course concentrates on stacks, queues, and priority queues.
00:23 Additionally, it also talks about queuing if you’re in a multithreaded environment and how to make sure that it’s thread-safe. Just a quick note, all the code samples here were tested using Python 3.9.
00:36 For the most part, earlier versions will work fine. I’ll try to point out any differences as I go along.
00:44 There’s all sorts of different ways of organizing your data when you program. The selection of the correct data structure can have a big impact on your code. Each kind of data structure has a different purpose, strength, and weakness.
00:58 Python, being batteries-included, comes with a lot of the most common data structures that you could ever possibly need. This course focuses on three types of data structures: stacks, queues, and priority queues.
01:12 Other kinds of data structures were covered in the previous two parts. Links to those parts are available in the notes below.
01:21 Stacks and queues are similar data structures. Stacks are Last-In/First-Out, also known as LIFO. That means the last thing put in is the first thing taken out.
01:33 Queues are similar to stacks but they’re FIFO, First-In/First-Out, so the first thing put into the queue is the first thing removed from the queue. Priority queues are a special type of queue that, instead of being FIFO, store items in a priority order.
01:50
The built-in list type can be used for stacks, queues, and priority queues. In the case of priority queues, it takes a little extra effort, and for the stack and queue, you have to make sure you use the right calls, but a list will do in a pinch.
02:05
Because a list is flexible, you can mix LIFO and FIFO on it. This may not always be ideal. The queue library provides a bunch of implementations of stacks and queues.
02:15
These are more specific than a list and might meet your needs a little better. And finally, if you’re after a priority queue, the heapq library is probably your best bet.
Become a Member to join the conversation.