Skip to main content

Data Structure and Algorithm Implementation In Python: Queue

By
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:

Comments

Post a Comment

Popular posts from this blog

Simple Face Recognition Project using OpenCV python Deep Learning

By
Okay, not from completely scratch though, in this Article you are going to learn to build a simple face detection and recognition console based application using Opencv python and Deeplearning Before Starting: If you don't have enough time to read the whole article or you are too lazy to read articles  Scroll all the way down and there is source code at last heading Resources. If you really love to learn step by step, there are lots of comments inside the code. I highly recommand you to read and go through it And at last, Don't panic :D Lets start: Installing Libraries: dlib (by davis king) Face_recognition (by adam geitgey ) (wraps around dlib’s facial recognition functionality making it to work easily with dlib) we also need to install imutils. Actually imutils is used to make basic image processing functions such as translation, rotation, resizing, skeletonization, and displaying Matplotlib images easier with OpenCV but we will be using it to maintain di...
Post a Comment
Read more

Image Compression and Color Quantization using K-Means Clustering

By
In this post, you'll able to compress an image of higher size relatively to a smaller size. Here size I mean the image's memory consumption, not the aspect ratio (though it is also somewhat related to the size). Before we begin, let's be familiar with what Image Compression, Color Quantization and K-Means Clustering is. Basically  K-Means Clustering  is used to find the central value (centroid) for k  clusters of data. Then each data point is assigned to the cluster whose center is nearest to k . Then, a new centroid is calculated for each of the k  clusters based upon the data points that are assigned in that cluster. In our case, the data points will be Image pixels. Assuming that you know what pixels are, these pixels actually comprises of 3 channels, Red, Green and Blue . Each of these channels' have intensity ranging from 0 to 255, i.e., altogether 256. So as a whole, total number of colors in each pixel is, 256 x 256 x 256.  Each pixel(color) has 2^...
Post a Comment
Read more

Data Structure and Algorithm Implementation In Python: Stack

By
Not comparing with other's But there are nice and great tutorial on data structure and algorithm implementation in python. But in this series of blog we will be more focused on academic requirement and algorithm based implementation. So Alert!! there will be some cheesy theory on related topics. In these series of blogs we will try to cover some examples of data structures with it's algorithm, theory and implementation in python. We will dive into the following topics Stack Queue Linked List (singly, doubly, circular) Hash Table Heap Data Structure Binary Tree After one or may be two topics covered we will switch our session and continue with another post. Why one should learn data structure and algorithm? The very first answer is it improves your problem solving skill. Learning Data structure and algorithm shows you how the coding follows algorithm. whenever you develop a program you have to handle various data and data structure storage format to those data and organizing all...
Post a Comment
Read more