Data Structures – Queues


title: Queues

Queues

Queue is a First In First Out (FIFO) Data Structure. Many algorithms use Queues at their core for improving performance.

Queue is one of the fundamental Abstract Data Types (ADT). It is similar to queues we have in movies or supermarkets. The first person to arrive will be served first right? Similarly, the first element to be inserted will be removed first. There are several types of queues such as,

  1. Simple Queue (or Queue)
  2. Circular Queue
  3. Priority Queue
  4. Dequeue (Double Ended Queue)

If you can understand the simple queue (which from here on will be referred as ‘Queue’) then all the others are just as easy, with little modifications.

Most common operations available on queue are,

  1. Add / Offer – Inserts an element into the end of the queue.
  2. Remove / Poll – Remove an element from the beginning of the queue.
  3. Peek – Returns element at the beginning of the queue but will not remove it.
  4. Size / Count – Returns the number of elements currently present in the queue.
  5. IsEmpty – Check whether the queue is empty or not.

Implementation of a queue is possible using either arrays or linked lists. The following is a simple array implementation of the queue data structure with its most common operations.

Example in C

#include <stdio.h> #define MAX 5 int front = -1, back = -1; int queue[MAX]; int isEmpty() { if(front == -1) { return 1; } return 0; } void add(int elem) { if (back == MAX-1) { printf("Queue overflow!\n"); } else { if(front == -1) { front++; } queue[++back] = elem; } } void delete() { if (front == -1) { printf("Queue underflow!\n"); } else if (front == back) { front = back = -1; } else { queue[front++]; } } int peek() { if (!isEmpty()) { printf("%d\n", queue[front]); } } void display() { if (!isEmpty()) { for(int i = front; i <= back; i++) { printf("%d\t", queue[i]); } printf("\n"); } } int main() { add(10); display(); // 10 add(5); display(); // 10 5 peek(); // 10 delete(); display(); // 5 return 0; }

Example in JavaScript

“`JavaScript
var Queue = function() {
var queue = [];
var front = 0;
var back = 0;
return {
isEmpty: function() {
return front >= back || queue.length === 0;
},
add: function(elem) {
/* You can also do queue.push(elem) in JavaScript.
This is how they do it in other languages */
queue[back++] = elem;
},
remove: function() {
if (!this.isEmpty()) {
return queue[front++]; // or queue.shift()
}
else {
throw new Error(“Queue is Empty.”);
}
},
peek: function() {
if (!this.isEmpty()) {
return queue[front];
}
}
}
};

var queue = new Queue();
console.log(queue.isEmpty()); // true
queue.add(1);
queue.add(2);
console.log(queue.remove()); // 1
console.log(queue.peek()); // 2
console.log(queue.remove()); // 2
console.log(queue.remove()); // exception
“`

Applications

  • Simulation
  • Scheduling (Job Scheduling, Disk Scheduling)
  • Shared Resource Management
  • Keyboard Buffer
  • Breadth First Search
  • To handle congestion in network

More Information:

This article needs improvement. You can help improve this article. You can also write similar articles and help the community.