Queue

A queue is a commonly used data structure in programming. It works just like a line of people waiting to buy a ticket — the first person to join the line is the first one to get served.

This follows the First In, First Out (FIFO) rule — the item added first is the one that comes out first.

In the above image, since 1 was kept in the queue before 2, it is the first to be removed from the queue as well. It follows the FIFO rule.

In programming terms, putting items in the queue is called enqueue, and removing items from the queue is called dequeue.

We can implement the queue in any programming language like C, C++, Java, Python or C#, but the specification is pretty much the same.

Basic Operations of Queue

A queue is an object (an abstract data structure - ADT) that allows the following operations:

- Enqueue: Add an element to the end of the queue
- Dequeue: Remove an element from the front of the queue
- IsEmpty: Check if the queue is empty
- IsFull: Check if the queue is full
- Peek: Get the value of the front of the queue without removing it

Working of Queue

Queue operations work as follows:

• Two pointers FRONT and REAR

• FRONT track the first element of the queue

• REAR track the last element of the queue

• initially, set value of FRONT and REAR to -1

Enqueue Operation

• check if the queue is full

• for the first element, set the value of FRONT to 0.

• increase the REAR index by 1

• add the new element in the position pointed to by REAR

Dequeue Operation

• check if the queue is empty

• return the value pointed by FRONT

• increase the FRONT index by 1

• for the last element, reset the values of FRONT and REAR to -1

Queue Code implementation:

class Queue {
  constructor(maxSize) {
    this.items = new Array(maxSize);
    this.maxSize = maxSize;
    this.front = -1;
    this.rear = -1;
  }

  isEmpty() {
    return this.front === -1;
  }

  isFull() {
    return this.rear === this.maxSize - 1;
  }

  enqueue(element) {
    if (this.isFull()) {
      throw new Error('Queue is full');
    }
    if (this.front === -1) this.front = 0;
    this.rear += 1;
    this.items[this.rear] = element;
  }

  dequeue() {
    if (this.isEmpty()) {
      return 'Queue is empty';
    }

    const removed = this.items[this.front];

    if (this.front === this.rear) {
      this.front = this.rear = -1;
    } else {
      this.front += 1;
    }

    return removed;
  }

  peek() {
    return this.isEmpty() ? 'Queue is empty' : this.items[this.front];
  }

  print() {
    if (this.isEmpty()) return [];
    return this.items.slice(this.front, this.rear + 1);
  }

  size() {
    return this.isEmpty() ? 0 : this.rear - this.front + 1;
  }

  clear() {
    this.front = this.rear = -1;
  }
}

const queue = new Queue(4);

queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(7);
queue.enqueue(9);

queue.dequeue();

console.log(queue.peek());
console.log(queue.size());
console.log(queue.print());
queue.clear();
console.log(queue.print());

Limitations of Queue

As you can see in the image below, after a bit of enqueuing and dequeuing, the size of the queue has been reduced.

And we can only add indexes 0 and 1 only when the queue is reset (when all the elements have been dequeued).

After REAR reaches the last index, if we can store extra elements in the empty spaces (0 and 1), we can make use of the empty spaces. This is implemented by a modified queue called the circular queue.

Complexity Analysis

The time complexity of enqueue in a queue implemented using an array is O(1) when inserting at the end (e.g., using push() in JavaScript).
The time complexity of dequeue is O(n) when removing from the front (e.g., using shift()), because all subsequent elements must be shifted one position to the left.

Applications of Queue (Extended List)

1. CPU Scheduling

• Processes are scheduled using queues in different scheduling algorithms like FCFS (First Come First Serve), Round Robin, etc.

2. Disk Scheduling

• Disk I/O requests are managed in queues to improve seek time and efficiency.

3. Asynchronous Data Transfer (Synchronization)

• Queues help buffer data between producer and consumer processes.

• Examples: I/O Buffers, Pipes, File I/O, Streams.

4. Interrupt Handling in Real-Time Systems

• Hardware interrupts are stored in queues to be handled based on priority or arrival time.

5. Call Center Systems

• Incoming calls are queued and answered in the order they are received.

6. Print Queue in Operating Systems

• Multiple documents sent to a printer are held in a queue and printed in sequence.

7. Task Scheduling in Operating Systems

• Tasks waiting to be executed are placed in a queue by the task scheduler.

8. Breadth-First Search (BFS) in Graphs

• BFS uses a queue to explore nodes level by level.

9. Message Queues in Distributed Systems

• Systems like RabbitMQ, Apache Kafka, and AWS SQS use queues to manage asynchronous communication between services.

10. Job Scheduling in Batch Systems

• Jobs submitted by users are queued and executed one by one or in a time-sharing manner.

11. Network Packet Management

• Routers and switches use queues to store packets before processing and forwarding.

12. Order Processing in E-Commerce

• Orders are placed in a queue and processed in the order they are received.

13. Buffering in Streaming Services (e.g., YouTube, Netflix)

• Video data is buffered in a queue before being rendered on the screen.

14. Customer Service Queues

• Tickets or support requests are handled in FIFO order.

15. Simulation Systems (e.g., Airports, Banks)

• Queues are used to simulate waiting lines for services.

16. Traffic Management Systems

• Vehicles at traffic signals or toll booths are queued before being allowed to pass.

Types of Queue

There are four different types of queues:

- Simple Queue
- Circular Queue
- Priority Queue
- Double Ended Queue

Simple Queue

In a simple queue, insertion takes place at the rear and removal occurs at the front. It strictly follows the FIFO (First in First out) rule.

Circular Queue

In a circular queue, the last element points to the first element making a circular link.

The main advantage of a circular queue over a simple queue is better memory utilization. If the last position is full and the first position is empty, we can insert an element in the first position. This action is not possible in a simple queue.

Priority Queue

A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue.

Insertion occurs based on the arrival of the values and removal occurs based on priority.

Deque (Double Ended Queue)

In a double ended queue, insertion and removal of elements can be performed from either from the front or rear. Thus, it does not follow the FIFO (First In First Out) rule.