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!
Bear with me. Our basic Queue data structure and accompanying Node will look like this:
def __init__(self, d):
self.data = d
self.prev_node = None
self.next_node = None
self.head = None
self.tail = None
self.size = 0
Take a number, buddy. When you get in line, you’re involved in the
enqueue operation. You begin your journey to the front desk at the back, or
tail, of the Queue. The
tail attribute is just a pointer; it’s like a big flag or arrow saying, “This person (or object) is last in line!” Talk about embarrassing…
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
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
self.head = new_node
self.tail = new_node
self.size += 1
You’ve been waiting for an hour, and finally shuffled to the front of the line. The man at the desk yells, “Next!” and you rush to the desk.
Something special just happened. You’ve been
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.
if self.head == None:
result = self.head
self.head = self.head.prev_node
self.size -= 1
Let’s say that you just made it to the front of the line. All the clerks are busy, but you know someone who works there. Your long time pal looks up from a pile of work and yells, “What’s going on?”
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
Full Source and Tests
Feel free to check out the source of the entire Queue on Github. If it interests you, the code I used to test it is here. Thanks for reading!
Do you enjoy learning about programming and computer engineering? If so, PageKey Solutions is the place for you! Click here to visit.
Originally published at blog.pagekeysolutions.com on June 23, 2017.