Queue

1. Overview

A Queue is a linear structure that follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

2. Description

2.1 Operations

2.1.1 Enqueue

Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.

2.1.2 Dequeue

Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.

2.1.3 Front

Get the front item from queue.

2.1.4 Rear

Get the last item from queue.

2.2 Time and Space Complexity

Algorithm	Average	Worst case
Space	O(n)	O(n)
Search	O(n)	O(n)
Insert	O(1)	O(1)
Delete	O(1)	O(1)

2.3 Implementation: Array

For implementing queue, we need to keep track of two indices, front, and rear. We enqueue an item at the rear and dequeue an item from the front. If we simply increment front and rear indices, then there may be problems, the front may reach the end of the array. The solution to this problem is to increase front and rear in a circular manner

# Python3 program for array implementation of queue 
  
# Class Queue to represent a queue 
class Queue: 
  
    # __init__ function 
    def __init__(self, capacity): 
        self.front = self.size = 0
        self.rear = capacity -1
        self.Q = [None]*capacity 
        self.capacity = capacity 
      
    # Queue is full when size becomes 
    # equal to the capacity  
    def isFull(self): 
        return self.size == self.capacity 
      
    # Queue is empty when size is 0 
    def isEmpty(self): 
        return self.size == 0
  
    # Function to add an item to the queue.  
    # It changes rear and size 
    def EnQueue(self, item): 
        if self.isFull(): 
            print("Full") 
            return
        self.rear = (self.rear + 1) % (self.capacity) 
        self.Q[self.rear] = item 
        self.size = self.size + 1
        print("%s enqueued to queue"  %str(item)) 
  
    # Function to remove an item from queue.  
    # It changes front and size 
    def DeQueue(self): 
        if self.isEmpty(): 
            print("Empty") 
            return
          
        print("%s dequeued from queue" %str(self.Q[self.front])) 
        self.front = (self.front + 1) % (self.capacity) 
        self.size = self.size -1
          
    # Function to get front of queue 
    def que_front(self): 
        if self.isEmpty(): 
            print("Queue is empty") 
  
        print("Front item is", self.Q[self.front]) 
          
    # Function to get rear of queue 
    def que_rear(self): 
        if self.isEmpty(): 
            print("Queue is empty") 
        print("Rear item is",  self.Q[self.rear]) 
  
  
# Driver Code 
if __name__ == '__main__': 
  
    queue = Queue(30) 
    queue.EnQueue(10) 
    queue.EnQueue(20) 
    queue.EnQueue(30) 
    queue.EnQueue(40) 
    queue.DeQueue() 
    queue.que_front() 
    queue.que_rear() 

3. Application Queue

• When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
• When data is transferred asynchronously (data not necessarily received at the same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.

4. Types of Queue

4.1 Priority Queue

struct item {
   int item;
   int priority;
}

• Every item has a priority associated with it.
• An element with high priority is dequeued before an element with low priority.
• If two elements have the same priority, they are served according to their order in the queue.

4.1.1 Implementation: Using Heaps

Heap is generally preferred for priority queue implementation because heaps provide better performance compared to arrays or linked lists. In a Binary Heap, getHighestPriority() can be implemented in O(1) time, insert() can be implemented in O(Logn) time and deleteHighestPriority() can also be implemented in O(Logn) time.
With Fibonacci heap, insert() and getHighestPriority() can be implemented in O(1) amortized time and deleteHighestPriority() can be implemented in O(Logn) amortized time.

4.1.2 Application of Priority Queue

• CPU Scheduling
• Graph algorithms like Dijkstra's shortest path algorithms, Prim's Minimum Spanning Tree, etc
• All queue applications where priority is involved.

4.2 Deque

Deque or double-ended queue is a generalized version of The queue data structure that allows insert and delete at both ends.

4.2.1 Implementation: Using a doubly linked list or circular array

A Deque can be implemented either using a doubly-linked list or circular array. In both implementations, we can implement all operations in O(1) time. We will soon be discussing C/C++ implementation of the Deque Data structure.

4.2.2 Application of Deque

Since Deque supports both stack and queue operations, it can be used as both. The Deque data structure supports clockwise and anticlockwise rotations in O(1) time which can be useful in certain applications.
Also, the problems where elements need to be removed and or added both ends can be efficiently solved using Deque. 

4.3 Circular Queue

• enQueue(value) This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at the Rear position.
• Steps:
  1. Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).
  2. If it is full then display Queue is full. If queue is not full then, check if (rear == SIZE – 1 && front != 0) if it is true then set rear=0 and insert element.
• deQueue() This function is used to delete an element from the circular queue. In a circular queue, the element is always deleted from the front position.
• Steps:
  1. Check whether a queue is Empty means check (front==-1).
  2. If it is empty then display Queue is empty. If the queue is not empty then step 3
  3. Check if (front==rear) if it is true then set front=rear= -1 else check if (front==size-1), if it is true then set front=0 and return the element.

4.3.1 Time Complexity

The time complexity of enQueue(), deQueue() operation is O(1) as there is no loop in any of the operations.

4.3.2 Applications

• Memory Management: The unused memory locations in the case of ordinary queues can be utilized in circular queues.
• Traffic system: In a computer-controlled traffic system, circular queues are used to switch on the traffic lights one by one repeatedly as per the time set.
• CPU Scheduling: Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.

5. Reference

https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

https://www.geeksforgeeks.org/queue-data-structure/

https://www.geeksforgeeks.org/priority-queue-set-1-introduction/

https://www.geeksforgeeks.org/deque-set-1-introduction-applications/

https://en.wikipedia.org/wiki/Double-ended_queue

https://www.geeksforgeeks.org/queue-set-1introduction-and-array-implementation/

https://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation/