Data Structure — Queue (Python)

Data Structures

Python Implementation(Queue)

# A complete working Python program of a Queue in 31 lines of code.

Stage 1 (Node class)

Implementing a Queue is reasonably straightforward. We just need a class called Node, that stores a next and data value.

class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None

Stage 2 (Create Head and Tail Nodes)

For our Queue implementation we need to create two reference objects called head and tail. This will allow us to remove an object from the head(represents the front of the queue) and add an object at the tail(represents the back of the queue).

Head and Tail reference of a Queue

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

Stage 3(isEmpty & Peek Methods)

The isEmpty()method is very simple, just return if the head value is null;return self.head == None. If the head value is null, then the queue is empty, otherwise it is not.

def isEmpty(self):
        return self.head == None

The peek()method will show us the 1st value in our Queue, this is achieved through return head.data. This will throw an exception when head is null. If you want you can go explicitly check for that exception.

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

Stage 4(Add & Remove Node)

To add a node(enqueue) to the tail of the Queue, first you must create the node. Then if the tail is not null, let tail’s next pointer point point to the new node, and then update the tail. Then we want to make sure that, even in the case when the Queue is completely empty(in which case head == null) then this value should be the head value.

Updating Tail reference to point to new Node

def enqueue(self, data):
        new_data = Node(data)
        if self.head is None:
           self.head = new_data
           self.tail = self.head
        else:
           self.tail.next = new_data
           self.tail = new_data

To remove a node(dequeue) from head of the Queue. First thing is to get the head datadata = self.head.data. Then we simply want to change the head value to be the next value. So set self.head = self.head.next and this basically removes it from the Queue. Then we say, if the head value is null, make sure to set the tail value to null too. Then return that data.

Updating Head reference to point to the next Node in Queue

def dequeue(self):
        data = self.head.data
        self.head = self.head.next
        if self.head is None:
           self.tail is None
        return data

Full Implementation

This is what your code should look like :)

Queue data-structure implementation

Test Cases

It is good practice to test your good, to see if it works (:

Queue test cases

Congratulations on completing the Python implementation of a Queue. So that is the basics of implementing a Queue. The methods follows pretty logically from the actual design and the algorithm behind it. :) !