Loading...
Master the First-In-First-Out (FIFO) principle and explore different queue types including linear, circular, priority, and double-ended queues used in real-world applications.
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Think of it like a line of people waiting - the first person to join is the first to be served.
Basic queue implementation where elements are stored in a linear fashion.
Queue where the rear connects to the front, forming a circle.
Elements are served based on priority, not insertion order.
Allows insertion and deletion at both front and rear ends.
Add an element to the rear of the queue
queue.enqueue(element)
Time: O(1) | Space: O(1)Remove and return element from the front
element = queue.dequeue()
Time: O(1) | Space: O(1)View the front element without removing it
element = queue.front()
Time: O(1) | Space: O(1)Check if the queue has no elements
boolean = queue.isEmpty()
Time: O(1) | Space: O(1)class CircularQueue {
constructor(capacity = 100) {
this.items = new Array(capacity);
this.front = -1;
this.rear = -1;
this.capacity = capacity;
this.size = 0;
}
enqueue(element) {
if (this.isFull()) {
throw new Error("Queue Overflow");
}
if (this.isEmpty()) {
this.front = 0;
this.rear = 0;
} else {
this.rear = (this.rear + 1) % this.capacity;
}
this.items[this.rear] = element;
this.size++;
}
dequeue() {
if (this.isEmpty()) {
throw new Error("Queue Underflow");
}
const element = this.items[this.front];
this.items[this.front] = null;
if (this.size === 1) {
this.front = -1;
this.rear = -1;
} else {
this.front = (this.front + 1) % this.capacity;
}
this.size--;
return element;
}
front() {
return this.isEmpty() ? null : this.items[this.front];
}
isEmpty() {
return this.size === 0;
}
isFull() {
return this.size === this.capacity;
}
}class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedQueue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
enqueue(element) {
const newNode = new Node(element);
if (this.isEmpty()) {
this.front = newNode;
this.rear = newNode;
} else {
this.rear.next = newNode;
this.rear = newNode;
}
this.size++;
}
dequeue() {
if (this.isEmpty()) {
throw new Error("Queue Underflow");
}
const data = this.front.data;
this.front = this.front.next;
if (this.front === null) {
this.rear = null;
}
this.size--;
return data;
}
front() {
return this.isEmpty() ? null : this.front.data;
}
isEmpty() {
return this.front === null;
}
}class PriorityQueue {
constructor() {
this.heap = [];
}
enqueue(element, priority) {
const node = { element, priority };
this.heap.push(node);
this.heapifyUp(this.heap.length - 1);
}
dequeue() {
if (this.isEmpty()) {
throw new Error("Queue Underflow");
}
const min = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.heapifyDown(0);
}
return min.element;
}
heapifyUp(index) {
const parentIndex = Math.floor((index - 1) / 2);
if (parentIndex >= 0 &&
this.heap[parentIndex].priority > this.heap[index].priority) {
[this.heap[parentIndex], this.heap[index]] =
[this.heap[index], this.heap[parentIndex]];
this.heapifyUp(parentIndex);
}
}
heapifyDown(index) {
const leftChild = 2 * index + 1;
const rightChild = 2 * index + 2;
let smallest = index;
if (leftChild < this.heap.length &&
this.heap[leftChild].priority < this.heap[smallest].priority) {
smallest = leftChild;
}
if (rightChild < this.heap.length &&
this.heap[rightChild].priority < this.heap[smallest].priority) {
smallest = rightChild;
}
if (smallest !== index) {
[this.heap[index], this.heap[smallest]] =
[this.heap[smallest], this.heap[index]];
this.heapifyDown(smallest);
}
}
isEmpty() {
return this.heap.length === 0;
}
}Operating systems use queues to manage process scheduling and resource allocation.
BFS algorithm uses queues to explore nodes level by level in graphs and trees.
Printers use queues to manage multiple print jobs in the order they were received.
Handle data transfer between devices with different processing speeds.
Priority queues manage tasks based on urgency and importance in applications.
Web servers use queues to handle incoming HTTP requests in order.