How to Implement a Queue in Python

You may hate the line at the DMV, but without it, things might turn into a rough-and-tumble free for all! In the same way that a line keeps raging motorists from getting out of hand, a Queue helps your computer keep its ducks in a row. The Queue functions very much like a line of people. It’s a First-In, First-Out (FIFO) data structure, so no cutting!

Starting Out

class Node(object):
def __init__(self, d):
self.data = d
self.prev_node = None
self.next_node = None

class Queue(object):
def __init__(self):
self.head = None
self.tail = None
self.size = 0

enqueue

In our hypothetical DMV line, everyone is holding their driver’s license in their pocket. This registration is your data, making you a Node in the Queue. Our Queue will be implemented as a Double-Ended Linked List, which means that every Node will point to the next data item in the queue. So, each person in our line will have to point at the next person in line. Perhaps rudely, they’ll need to jerk a thumb over their shoulder at the previous person in line, too.

When you’re joining the line, the first thing you need to do is point at the current tail. Then, move the hypothetical arrow and declare yourself as the new tail reference.

In code, this would look like:

def enqueue(self, d):
new_node = Node(d)
if self.size > 0:
self.tail.prev_node = new_node
new_node.next_node = self.tail
self.tail = new_node
else:
self.head = new_node
self.tail = new_node
self.size += 1

dequeue

Something special just happened. You’ve been dequeue‘d. Congratulations.

In order to dequeue something from the list, you first grab the Node from the front. Then, set self.head = self.head.prev_node. In other words, move the head pointer to the previous person in line. Now, return the data from Node you just removed from the Queue. It’s important to store this in a temporary variable. Otherwise, you’ll be returning the data of something still in the Queue. An important part of dequeue is that the item you return has been removed from the queue.

def dequeue(self):
if self.head == None:
return None
result = self.head
self.head = self.head.prev_node
self.size -= 1
return result.data

peek

How did they know you were there? They had to peek at the front of the line to recognize your face.

This operation is very simple. All you need to do is ask the first person in line to pull out their driver’s license for a moment. In other words, just return self.head.data.

def peek(self):
return self.head.data

Full Source and Tests

Do you enjoy learning about programming and computer engineering? If so, Line by Line Code is the place for you! Click here to visit.

Originally published at linebylinecode.com on June 23, 2017.