Data Structures and Algorithms 101 part two: Queues

Sakis Kasampallis | Jan 4, 2013 min read

Definition

Think of a queue as a line of people waiting to buy a ticket for an event (music concert, film, etc.).

Photo Credit: Bryan Bedder/Getty Images for Tribeca Film Festival

In the queue shown at the picture, a person who just arrives to buy a ticket goes to the left side (unless cheating) and a person who just bought a ticket leaves the queue from the right side (to avoid conflicts).

In queue terminology, adding a new item means enqueuing it to one side of the queue (either side is fine), while removing an item means dequeuing it from the opposite side of the queue.

Fundamental queue operations
The first item that enters a queue is the first item that exits the queue (first come-first served). For that reason, we call queues First In First Out (FIFO) data structures.

Usage and performance

Queues have many practical applications (search for "applications"). A simple example is printing documents. Documents are sent to the printer using a first come-first served policy (let's skip priorities for simplicity). If the printer is busy and we are trying to print a document, it will enqueue it and begin printing it only after it has finished with printing (dequeuing) all the existing documents.

Enqueuing and dequeuing items in a queue takes constant time - O(1). On the other hand, queues (like stacks) are not optimized for searching or adding/removing items from arbitrary positions. These operations take linear time - O(n).

Implementation

Like my stack implementation, I will use python and the built-in list data structure to implement a queue. Notice the similarities between stacks and queues. The only difference is the way the elements are accessed.

If you are not familiar with __iter__ and __next__ they are special functions for implementing iterators in python. In short, we can now say for i in mq where mq is an instance of myqueue. Quite convenient! I am going to use it in the sample problem.

Sample problem

Implement a song playlist for a jukebox/media player, etc. New songs are added to the back (left side) of the playlist. The next song to be played is picked from the front (right side) of the playlist.

Obviously that's not a "real" playlist since it doesn't track time so that can be automatically triggered after the end of a song. That's left as an exercise for you dear hacker. Enjoy!

References