Data Structure and Algorithm Implementation In Python: Queue

This is part of 'Data structure and algorithm implementation in python' series of blog. Previous: Stack    Next: Linked List

Queue:

(source code) Direct... First in first out discipline. Let's see in real life example: The man who is standing in front of a queue is served first. That man is in front of the queue because he entered that queue at first. Formally defining: A queue is an ordered collection of items from which items are deleted from the front of the queue and the insertion of item takes place from rear of the queue. the first one inserted will be the first element to be removed.

Operations done in Queue:

enqueue(item): This operation inserts an item at the rare of the queue i.e. if we are using python's list to implement queue then rare means last element in the stack and every insertions after an item inserted will be appended at last of the queue.

dequeue(): This operation deletes item from the front end of the queue. If we are using python's list to implement queue then front means the zeroth index position of the list. So we remove item from the queue from queuelist[0].

These operations are basic or you can say primitive operations for queue. Other operations are also used like to check if the queue is empty, full, to display size or number of elements in the queue.

We will be using the following operations:

enqueue(item): This function will add an item at the rare of the queue. i.e. append to the queue list.

dequeue(): This function will remove an item from the front of the queue.

isEmpty(): This method will check if the queue is empty or not and returns true if queue is empty, false otherwise.

numberOfElement(): This method will return the size of the queue. The number of elements currently in the queue.

The above is basic outline that we will use to implement our queue in python and we will be sticking with the following algorithm:

To initialize a queue (Linear Queue):

1. Setup a list that holds items in the queue
2. set rear variable to -1 and front to 0
   

Since we are using python list to implement list, we don't have to care about that second step as we have append and pop as inbuilt function of list.

To enqueue or add item in the queue:

1. Set rear = rear + 1
2. Add item as queue[rear] = item
   

since we have append inbuilt method of list so we simply just append that item to the list.

To Dequeue or remove an item from the queue:

1. Check if the queue is empty. i.e if rear < front: print queue is empty
2. If not empty then item = queue[front + 1]

since we are using list, we just have to check if the length of the list is 0 using inbuilt method len() to check the empty queue and to dequeue we just pop front of the list i.e. pop zeroth index value of the list.

To check empty queue:

1. Check the size of the queue with len(queuelist)
2. If len is equal to 0 then queue is empty

To find number of elements in the queue:

1. Return length of queue list with len(queuelist)

Now, lets code it. Please notice those comments in the code

class EmptyQueueError(Exception):
    #used to display custom error when queue is empty 
    pass

class Queue:

    def __init__(self):
        # initilizing empty using list
        self.data = []

    def enqueue(self, item):
            # Insert the item at the rear of the Queue

        self.data.append(item)

    def dequeue(self):
        
        #Removes an item from the front of the Queue.
  
        if self.isEmpty():
            raise EmptyQueueError("Trying to dequeue from an Empty Queue.")

        return self.data.pop(0)

    def isEmpty(self):
        #     Test if the queue has no items.
        #     :return: True if Queue is Empty. False Otherwise
        return self.numberOfElement() == 0    


    def numberOfElement(self):
        # Returns the number of elements currently in the Queue.
        
        return len(self.data)

Now lets make a instance of the class queue and play with it's methods

q = Queue()
#initial enqueue
q.enqueue("item1")
q.enqueue("item2")
q.enqueue("item3")

print(q.numberOfElement())
print(q.data)

#inserting with user input
item = input("Enter value to insert ")
q.enqueue(item)

print(q.data)
# dequeue operation
q.dequeue()
print(q.data) # notice the output before and after dequeue. The first one inserted i.e. 'item1' should be remove from the queue first

You are moving forward. That's all for queue and now lets move on for linked list.

References:

1. Data Structure Using C by A. K. Sharma
2. Packt: Data Sturctures and Algorithms

Resources:

1. Source code