Queue का Implementation

एक array-based queue chairs की एक line जैसी है दो markers के साथ, एक line के front पर और एक back पर, kids के join और leave होने पर आगे बढ़ते हुए।

In this page:

Array Queue
Linked List Queue
Queue Overflow
Queue Underflow
Queue Using Two Pointers

Syntax

markup

class Queue:
    def __init__(self):
        self.items = []
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        return self.items.pop(0)

Array Queue

एक array-based queue दो indexes track करता है, front और rear, valid elements की current शुरुआत और आखिर मार्क करते हुए, और enqueue/dequeue बस उन indexes को पूरे array shift करने के बजाय आगे move करते हैं।

उदाहरण: Array Queue

#include <iostream>
using namespace std;
int main() {
	int q[5], front = 0, rear = -1;
	q[++rear] = 1; q[++rear] = 2; q[++rear] = 3;
	cout << "Dequeued: " << q[front++] << endl;
	cout << "Front now: " << q[front] << ", Rear: " << q[rear];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] q = new int[5];
		int front = 0, rear = -1;
		q[++rear] = 1; q[++rear] = 2; q[++rear] = 3;
		System.out.println("Dequeued: " + q[front++]);
		System.out.println("Front now: " + q[front] + ", Rear: " + q[rear]);
	}
}

q = [None] * 5
front, rear = 0, -1
for v in (1, 2, 3):
    rear += 1
    q[rear] = v
print("Dequeued:", q[front])
front += 1
print("Front now:", q[front], ", Rear:", q[rear])

#include <stdio.h>
int main() {
	int q[5], front = 0, rear = -1;
	q[++rear] = 1; q[++rear] = 2; q[++rear] = 3;
	printf("Dequeued: %d\n", q[front++]);
	printf("Front now: %d, Rear: %d", q[front], q[rear]);
	return 0;
}

Linked List Queue

एक linked-list-based queue head और tail node references रखता है: enqueue tail पर एक नया node जोड़ता है, और dequeue head पर node हटाता है, दोनों O(1) time में चाहे queue में कितने भी elements हों।

उदाहरण: Linked List Queue

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
	Node* head = new Node{1, nullptr};
	Node* tail = head;
	tail->next = new Node{2, nullptr}; tail = tail->next;
	tail->next = new Node{3, nullptr}; tail = tail->next;
	cout << "Dequeued: " << head->data;
	head = head->next;
	cout << ", New head: " << head->data;
	return 0;
}

public class Main {
	static class Node { int data; Node next; Node(int d) { data = d; } }
	public static void main(String[] args) {
		Node head = new Node(1);
		Node tail = head;
		tail.next = new Node(2); tail = tail.next;
		tail.next = new Node(3); tail = tail.next;
		System.out.print("Dequeued: " + head.data);
		head = head.next;
		System.out.println(", New head: " + head.data);
	}
}

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = tail = Node(1)
for v in (2, 3):
    tail.next = Node(v)
    tail = tail.next
print("Dequeued:", head.data)
head = head.next
print("New head:", head.data)

#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
	struct Node *head = malloc(sizeof(struct Node));
	head->data = 1; head->next = NULL;
	struct Node *tail = head;
	tail->next = malloc(sizeof(struct Node)); tail = tail->next; tail->data = 2; tail->next = NULL;
	printf("Dequeued: %d\n", head->data);
	head = head->next;
	printf("New head: %d", head->data);
	return 0;
}

Queue Overflow

एक array-backed queue overflow होता है जब rear index array की capacity तक पहुंचता है और किसी दूसरे element के लिए कोई जगह नहीं बचती, भले ही पहले slots पिछले dequeues से free हुए हों (जब तक यह wrap न हो, एक circular queue की तरह)।

उदाहरण: Queue Overflow

#include <iostream>
using namespace std;
int main() {
	int q[3], rear = -1;
	int capacity = 3;
	for (int i = 0; i < 4; i++) {
		if (rear == capacity - 1) { cout << "Overflow! Cannot enqueue " << i + 1; break; }
		q[++rear] = i + 1;
	}
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] q = new int[3];
		int rear = -1, capacity = 3;
		for (int i = 0; i < 4; i++) {
			if (rear == capacity - 1) { System.out.println("Overflow! Cannot enqueue " + (i + 1)); break; }
			q[++rear] = i + 1;
		}
	}
}

q = [None] * 3
rear = -1
capacity = 3
for i in range(4):
    if rear == capacity - 1:
        print("Overflow! Cannot enqueue", i + 1)
        break
    rear += 1
    q[rear] = i + 1

#include <stdio.h>
int main() {
	int q[3], rear = -1, capacity = 3;
	for (int i = 0; i < 4; i++) {
		if (rear == capacity - 1) { printf("Overflow! Cannot enqueue %d", i + 1); break; }
		q[++rear] = i + 1;
	}
	return 0;
}

Queue Underflow

Underflow तब होता है जब एक खाली queue पर एक dequeue की कोशिश की जाती है, मतलब front और rear indicate करते हैं कि हटाने के लिए कुछ नहीं बचा, और एक implementation को garbage return करने के बजाय इसे explicitly जांचना चाहिए।

उदाहरण: Queue Underflow

#include <iostream>
using namespace std;
int main() {
	int front = 0, rear = -1;
	if (front > rear) cout << "Underflow! Queue is empty.";
	else cout << "Dequeue OK";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int front = 0, rear = -1;
		if (front > rear) System.out.println("Underflow! Queue is empty.");
		else System.out.println("Dequeue OK");
	}
}

front, rear = 0, -1
if front > rear:
    print("Underflow! Queue is empty.")
else:
    print("Dequeue OK")

#include <stdio.h>
int main() {
	int front = 0, rear = -1;
	if (front > rear) printf("Underflow! Queue is empty.");
	else printf("Dequeue OK");
	return 0;
}

Queue Using Two Pointers

Front और rear को दो अलग positions के रूप में track करना, दोनों के लिए एक single index reuse करने की कोशिश करने के बजाय, वह है जो enqueue और dequeue को हर एक को किसी मौजूदा elements shift किए बिना एक clean, constant-time operation रखता है।

उदाहरण: Queue Using Two Pointers

#include <iostream>
using namespace std;
int main() {
	int q[5], front = 0, rear = -1;
	q[++rear] = 1; q[++rear] = 2;
	int dequeued = q[front++];
	q[++rear] = 3;
	cout << "Dequeued: " << dequeued << ", front=" << front << ", rear=" << rear;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] q = new int[5];
		int front = 0, rear = -1;
		q[++rear] = 1; q[++rear] = 2;
		int dequeued = q[front++];
		q[++rear] = 3;
		System.out.println("Dequeued: " + dequeued + ", front=" + front + ", rear=" + rear);
	}
}

q = [None] * 5
front, rear = 0, -1
rear += 1; q[rear] = 1
rear += 1; q[rear] = 2
dequeued = q[front]; front += 1
rear += 1; q[rear] = 3
print("Dequeued:", dequeued, ", front=", front, ", rear=", rear)

#include <stdio.h>
int main() {
	int q[5], front = 0, rear = -1;
	q[++rear] = 1; q[++rear] = 2;
	int dequeued = q[front++];
	q[++rear] = 3;
	printf("Dequeued: %d, front=%d, rear=%d", dequeued, front, rear);
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Queue Introduction Next Lesson → Circular Queue