Queue

• Queue is a linear data structure where items are kept according to the FIFO (First In First Out) principle, meaning that the first element to be eliminated is the one that was added first.Imagine it as a queue of people waiting to be served; the first person in line gets served first.
• Queue can be implemented using arrays as well as linked lists.
  • Array based queue : The components of the queue are stored in an array in this implementation. It is easy to use and provides quick access to items, but unless you use dynamic arrays, its size is fixed.
  • Linked list based queue : In this implementation, the elements are stored in a linked list. Its size is adjustable, but because of the pointers stored, there is an increased memory overhead.This will increase the flexibility of organizing and storing of the data in the linked list.

UML class diagram of a Queue-node

Structure of a Queue

UML classs diagram of a Queue – linked list based

• we should maintain the O(1) time complexity in queue operations hence we have to introduce the two ends as rear and front.
  • Rear : To enter elements to the queue.
  • Front : To exit elements from the queue.

1.1 Operations on queue

1. Enqueue
   • Add an element from the end of the queue.
     Array based
     
     Linked list based
     
2. Dequeue
   • Remove the first element from the queue without traversing.
     Array based
     
     Linked list based
     
3. Peek
   • Get the front element without removing it.
4. IsEmpty
   • Check if the queue is empty.
5. IsFull
   • Check if the queue is fully occupied.
6. Printing the queue
   • print every element after iterating through the queue.
     Array based
     
     Linked list based
     
7. searching the queue
   • Check for a element in the queue.
     

1.2 Types of Queues

• Simple Queue: Standard FIFO queue.
• Circular Queue : Operations are carried out in accordance with the FIFO (First In First Out) principle.The last location in a circular queue is connected to the first position to form a circle.
• Priority Queue: Every element has a priority, and priorities are used to figure out how an element is dequeued rather than positions.
• Double-ended Queue: Both ends (front and back) are used for insertion and deletion operations. It means that we have the ability to add from both the front and the back, as well as remove from both.

1.3 Applications of Queue

• Scheduling: Used in operating systems for managing tasks, processes, and jobs.
• Buffering : Used in data streaming, such as IO buffers.
• Order Processing: Used in systems that process requests or jobs in the order they arrive.