From the course: Python Data Structures and Algorithms

Understand the queue data structure - Python Tutorial

From the course: Python Data Structures and Algorithms

Start my 1-month free trial

Understand the queue data structure

“

- [Instructor] The next data structure we're going to look at is the queue. Now, a queue in computing is very similar to a queue in real life and that you have an arrival order which you wish to maintain. There are many applications of the queue data structure. So for example inside of the CPU, whenever you have data transferred asynchronously between two processes we need some way of maintaining the order the original order. Several graph traversal algorithms, including the ones we're looking at in this course, and many other applications, often when a resource to be shared among multiple consumers is when a queue becomes relevant. So a queue is a data structure in which all additions are made at one end called the rear or tail of the queue. And all deletions are made from the other end called the head or front of the queue. Which end actually serves as the head and which is the tail is an implementation detail. In this course, we will consider the left to be the head of our queues and the right to be the tail. Queue is first-in, first-out data structure. So in contrast to the first-in, last-out that we had previously with the stack, this is first-in, first-out, so FIFO first-in, first-out. So you can see on the slide and other representation so the front of the queue is the next person to be served, if you compare this to a shopping queue or a queue at an ice cream stand or something like that, so the front of the queue was the first person to arrive, and it's going to be the next person to be served, and the rear of the queue is where the last person joined. Sometimes the front and the rear are called the head and the tail okay, so just be aware that, that can vary but they have the same meanings it's front is head and tail is rear. And there's a couple of signature operations, so one is enqueue, which is where you put an item into the queue and the other is dequeue which is where you remove an item from the front of the queue. And finally we just have a slightly more logical representation bit more like what it might look like in our program. So on the left hand side is the front of the queue, from which we dequeue or remove items, and on the right hand side we have the back of the queue which is where we enqueue new items or add new items to our queue. If you make a point of memorizing the FIFO acronym first-in, first-out and associating it with the image shown here, it would help you to keep your bearings as we move forward.

Contents