‘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.
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.
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.
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:
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.
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.