Introduction to Queue – DSA

What is Queue in Data Structure?

• A Queue is an order list of elements where insertions and deletions are performed at two ends. Queue works on the principle FIFO (first in first out).
• The operations we can perform on Queue are En queue and de queue.
• En queue means inserting the elements into the queue. De queue means deleting the elements from the queue.
• The other operations of the queue are peak() and display(). Peak() is used to display the first element of the queue. Display() is used to display all the elements in the queue.
• Queue operations can be carried out using two techniques.
  • 1. Static memory allocation (arrays)
  • 2. Dynamic memory allocation (linked list)

• A Queue is a linear data structure useful in solving various real-life problems. One can stimulate real-life challenges with this data structure. 
• The theory of Queue is common and simple to all. We can come across queue applications in every occupation.

Types of Queues:

1. Circular Queue
2. Double-Ended Queue
3. Priority Queue

Applications of Queues:

1. A queue of people standing at the railway reservation counter for booking the tickets.
2. A queue of people standing in a bank to perform their transactions.

A queue is widely used as a waiting list for a single shared resource.

Ex: Printer

Queue is used to transfer the data correspondingly between the two processors. Queue is a buffer in MP3 players, iPod playlists, and CD players. Queue is also used in the operating system to handle the interrupts.

Queue representation by using arrays:

• Queues can be easily represented by using a 1-D array. 
• The insertion operation of the queue is done at the rear end, while the deletion operation of the queue is done at the front end. 
• Initially, the values of the front and rear are -1. 
• When we insert an element into the queue the rear value is incremented by one. 
• If we add the first element to the queue, we should initialize the front index to zero and increment the rear index by one.
• When rear=MAX-1, we say that the queue is full. 
• When the queue is full and if we try to perform insert operation it results in queue overflow. 
• When front=-1 or front>rear, we say the queue is empty. 
• If the queue is empty and we try to perform a delete operation it results in queue underflow.

The diagrammatic representation of the queue is given below.

F=-1            queue is empty                                                                                                                     R=-1

Insert 35

F=0                                                                                                                                                     R=0

Insert 23

F=0                                                                                                                                                     R=1

Insert 29

F=0                                                                                                                                                     R=2

Insert 45

F=0                                                                                                                                                     R=3

Insert 65

F=0                                                                                                                                                     R=4

Insert 28

Queue overflow[R=MAX-1]

Delete 35

F=1                                                                                                                                                     R=4

Delete 23

F=2                                                                                                                                                   R=4

Delete 29

If we do a delete operation F value increases, if F>R the queue results in underflow.

Differences between Stack and Queue:

Related FAQs:

1. What is the Difference Between a Queue and a Stack?

• While both are linear data structures, they differ in their ordering:
  • Queue: FIFO (First-In, First-Out)
  • Stack: LIFO (Last-In, First-Out) – Think of a stack of plates.

2. How Do I Choose Between an Array-Based and Linked List-Based Queue?

• Consider these factors:
  • Memory: Linked lists are more flexible, allocating memory as required. Arrays have a fixed size.
  • Efficiency: Array-based queues can experience performance issues when dequeuing elements, especially if not implemented carefully to avoid unnecessary element shifting. Linked lists handle this more efficiently.

3. What is a Circular Queue, and How Does it Differ from a Linear Queue?

• A circular queue connects the rear and front, allowing it to “wrap around.” This prevents wasted space and potential overflow conditions in linear queues.

4. What is the Time Complexity of Queue Operations?

• In a well-implemented queue (often using a linked list), enqueue and dequeue operations have a time complexity of O(1), meaning they take constant time regardless of the queue’s size.

5. Are There Different Types of Priority Queues?

• While the basic principle of prioritizing elements remains, there are variations like:
  • Bounded Priority Queue: Has a fixed maximum size.
  • Unbounded Priority Queue: Can grow dynamically.

6. Can Queues Be Used to Implement Other Data Structures?

• Yes! Queues are versatile and can be used as building blocks for other data structures like:
  • Priority Queues 
  • Breadth-first search implementations