Queue in Data Structure | DSA Tutorials

YASH PAL,

Queue in Data Structure – A queue is an abstract data structure in which insertion is performed on one end and deletion is performed on the other end.

Queue in Data Structure

queue in data structure
Figure 1: Queue

Example of Queue – In Figure 1, you see that the customers are standing in a line. And the customer who entered the line will go first means First in First out. And we can add the new customers to the end of the line, and they will go out from the beginning of the line. So the queue follows the FIFO ( First in First out ) process, and we can insert a new value from one end and delete the first inserted value from the other end.

Enqueue operation

To insert a new value in the queue is called the Enqueue operation in the queue

Dequeue operation

Deleting the first entered value in the queue is called the Dequeue operation in the queue.

Front end

The end from which we delete the value in the queue is called the Front end of the queue.

Rear-end

The end from which we insert a new value in the queue is called the rear end of the queue.

Front and rear part of queue
Figure 2: Front and rear parts of the queue

If we want to enter a new value, then we use the rear end, and if we want to delete the value, then we use the front end.

Queue data structure
Figure 3: Queue data structure

Implementation of the Queue

We can implement a queue using two ways or using two data types. The first is using the array, and the second is using a linked list. So first we learn about how to implement a queue using an array, and then we will learn about the implementation of a queue using a linked list.

Implementation of the queue using an array

Implementation of queue using array
Figure 4: Implementation of a queue using an array

To implement a queue using an array, first, we need to choose the position of the front and rear ends. We use the first index of the array as the front end and the last index as the rear end.

Implementation of queue using array
Figure 5: Implementation of a queue using an array

In the above example, first, we take an empty array, and then we enqueue the values 20, 30, 15, and 40. After that, we dequeue the values 20 and 30 from the front end, and then we again enqueue the value 56, and then dequeue the value 15.

Program to implement a queue using an array in Python

class EmptyQueueError(Exception):
    pass
class Queue:

    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)

    def enqueue(self,item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is Empty")
        return self.items.pop(0)

    def peek(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is Empty")
        return self.items[0]

    def display(self):
        print(self.items)

##############


if __name__ == '__main__':
    qu = Queue()

    while True:
        print("1. Enqueue")
        print("2. Dequeue")
        print("3. Peek")
        print("4. Size")
        print("5. Display")
        print("6. Quit")

        choice = int(input("Enter your choice : "))

        if choice == 1:
            x = int(input("Enter the element : "))
            qu.enqueue(x)
        elif choice == 2:
            x=qu.dequeue()
            print("Element deleted fro the queue is : ", x)
        elif choice == 3:
            print("Element at the front end is ", qu.peek())
        elif choice == 4:
            print("Size of queue ", qu.size())
        elif choice == 5:
            qu.display()
        elif choice == 6:
            break        else:
            print("Wrong choice ")
        print()

Implementation of the queue using a linked list

Implementation of the queue using a linked list
Figure 6: Implementation of the queue using a linked list

To implement a queue using a linked list, we first store the first node and the last node’s reference into the front and rear variables. Because using the front variable, we perform deletion in a queue and using the rear variable, we perform insertion in a queue. So the beginning of the list is called the front end of the queue, and the end of the list is called the rear end of the queue.

Stack Dequeue operation

To remove a node from the queue is known as Dequeue. We already know how to delete the first node of the linked list and delete the node in the only linked list. And if you don’t know, then please go through this tutorial – Deletion in the linked list

Stack Dequeue operation
Figure 7: Stack Dequeue operation

Enqueue operation

To add or insert a new node in the queue is known as the Enqueue operation. We already know how to insert a new node at the end of the linked list. And if you don’t know, then please go through this tutorial – Insertion in the linked list

Stack Enqueue operation
Figure 8: Stack Enqueue operation

Program to implement a queue using a linked list in Python

class EmptyQueueError(Exception):
    pass

class Node:

    def __init__(self, value):
        self.info = value
        self.link = None

class Queue:

    def __init__(self):
        self.rear = None
    def is_empty(self):
        return self.rear is None
    def size(self):
        if self.is_empty():
            return 0        n = 0        p = self.rear.link
        while True:
            n += 1            p = p.link
            if p == self.rear.link:
                break        return n

    def enqueue(self, data):
        temp = Node(data)

        if self.is_empty():
            self.rear = temp
            self.rear.link = self.rear
        else:
            temp.link = self.rear.link
            self.rear.link = temp
            self.rear = temp

    def dequeue(self):

        if self.is_empty():
            raise EmptyQueueError("Queue is Empty ")

        if self.rear.link == self.rear:
            temp = self.rear
            self.rear = None        else:
            temp = self.rear.link
            self.rear.link = self.rear.link.link
        return temp.info

    def peek(self):
        if self.is_empty():
            raise EmptyQueueError("Queue is Empty")
        return self.rear.link.info

    def display(self):
        if self.is_empty():
            print("List is empty")
            return
        p = self.rear.link
        while True:
            print(p.info, " ", end='')
            p = p.link
            if p == self.rear.link:
                break        print()


#####################

if __name__ == '__main__':
    qu = Queue()

    while True:
        print("1. Enqueue")
        print("2. Dequeue")
        print("3. Peek")
        print("4. Size")
        print("5. Display")
        print("6. Quit")

        choice = int(input("Enter your choice : "))

        if choice == 1:
            x = int(input("Enter the element : "))
            qu.enqueue(x)
        elif choice == 2:
            x = qu.dequeue()
            print("Element deleted from the queue is : ", x)
        elif choice == 3:
            print("Element at the front end is ", qu.peek())
        elif choice == 4:
            print("Size of queue ", qu.size())
        elif choice == 5:
            qu.display()
        elif choice == 6:
            break        else:
            print("Wrong choice")
        print()
Data Structures & Algorithms Tutorials for Beginners
Computer Science Tutorials Data Structures Tutorials

Leave a Reply

Your email address will not be published. Required fields are marked *