Queue | Data Structure

Introduction

‘Queue’ is another abstract and linear data structure. It’s almost like Stack. The difference is it follows the principle FIFO instead of LIFO. So let’s get into the blog. In this blog, I am going to give you an overview of the Queue data structure. And of course, I will show you the implementation in Python.

Concept

The queue works just like the real-life queue. The rule it follows is First In First Out and also known as FIFO.

In this way, we can store data in a computer where the first inserted data will be removed first. Let’s see a visual example.

Code Implementation

In the queue data structure, there are two main operations. These two operations have a naming convention. One is for adding data. It’s called enqueue. Another is for removing data. And it’s called dequeue. There is also another operation called peek. This operation returns the first inserted data of the queue, which is not removed yet.

We can implement Queue using Array or Linked List data structure. This time we will see how to implement it using Linked List.

class Node():
    
    def __init__(self, val):
        self.val = val
        self.next = None
    
class Queue():

    def __init__(self):
        self.head = None
        self.tail = None
    
	# Enqueue
    def enqueue(self, val):
        
        new_node = Node(val)

        if self.head is None:
            self.head = new_node
        else:
            self.tail.next = new_node
        
        self.tail = new_node
       
	# Dequeue
    def dequeue(self):
        if self.head == None:
            return 'Stack is empty'
			
        self.head = self.head.next
		
	# Search
    def search(self, val):
        if self.head is None:
            return False

        current = self.head

        while current:
            if current.val == val:
                return True
            
            current = current.next
        
        return False
        

    
	# Peek
    def peek(self):
        if self.head == None:
            return 'Stack is empty'
			
        return self.head.val

queue = Queue()

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)

print(queue.peek()) # 1
print(queue.search(3)) # True
print(queue.search(10)) # False
queue.dequeue()
queue.dequeue()
print(queue.peek()) # 3

The time complexity of these four operations are:

Enqueue: O(1)
Dequeue: O(1)
Search: O(n)
Peek: O(1)

Priority Queue

There is an exception in the queue, which is called the priority queue. It does not follow the general queue rule FIFO. Here elements are removed based on the priority. Usually, priorities are set while when the elements are inserted.

Last Words

I hope this high-level overview and implementation of the Queue data structure helps you. There is so many real-life use case of this data structure in computer science. If you know this better, you can implement it in your real-life project.

Tags: Data StructureFIFOPythonQueue