Queue

[Lomanu4]

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.

Пожалуйста Авторизируйтесь или Зарегистрируйтесь для просмотра скрытого текста.