Deque यानि Double-ended Queue

एक deque एक line जैसी है जिसे आप किसी भी end से join या leave कर सकते हैं, एक stack और एक queue का mix।

In this page:

What is a Deque?
Insert at Front
Insert at Rear
Deque as Stack
Deque Applications

Syntax

markup

from collections import deque
dq = deque()
dq.appendleft(item)   # insert at front
dq.append(item)       # insert at rear
dq.popleft()          # remove from front
dq.pop()              # remove from rear

What is a Deque?

एक deque (double-ended queue) stacks और queues दोनों को generalize करता है front और rear दोनों पर insertion और removal allow करके, सिर्फ एक fixed end पर नहीं। यह flexibility एक deque को sliding window maximum जैसे algorithms के लिए उपयोगी बनाती है, जहां elements को दोनों ends से efficiently जोड़ना और हटाना है।

उदाहरण: What is a Deque?

#include <iostream>
#include <deque>
using namespace std;
int main() {
	deque<int> dq;
	dq.push_back(2); dq.push_back(3);
	dq.push_front(1);
	for (int x : dq) cout << x << " ";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Deque<Integer> dq = new ArrayDeque<>();
		dq.addLast(2); dq.addLast(3);
		dq.addFirst(1);
		System.out.println(dq);
	}
}

from collections import deque
dq = deque()
dq.append(2)
dq.append(3)
dq.appendleft(1)
print(list(dq))

#include <stdio.h>
int main() {
	int dq[5] = {1, 2, 3};
	for (int i = 0; i < 3; i++) printf("%d ", dq[i]);
	return 0;
}

Insert at Front

Front पर insert करना एक नया element deque में अभी जो कुछ भी है उससे आगे जोड़ता है, एक operation जो एक plain queue बिल्कुल support नहीं करती क्योंकि यह सिर्फ rear पर जोड़ सकता है। एक अच्छी तरह implemented deque (आमतौर पर एक doubly linked list या circular buffer से backed) पर दोनों insertion operations constant O(1) time में चलते हैं।

उदाहरण: Insert at Front

#include <iostream>
#include <deque>
using namespace std;
int main() {
	deque<int> dq = {2, 3};
	dq.push_front(1);
	dq.push_front(0);
	for (int x : dq) cout << x << " ";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Deque<Integer> dq = new ArrayDeque<>(Arrays.asList(2, 3));
		dq.addFirst(1);
		dq.addFirst(0);
		System.out.println(dq);
	}
}

from collections import deque
dq = deque([2, 3])
dq.appendleft(1)
dq.appendleft(0)
print(list(dq))

#include <stdio.h>
int main() {
	int dq[4] = {0, 1, 2, 3};
	for (int i = 0; i < 4; i++) printf("%d ", dq[i]);
	return 0;
}

Insert at Rear

Rear पर insert करना बिल्कुल एक normal queue पर enqueue जैसा काम करता है, नए element को वहां पहले से मौजूद हर चीज़ के बाद append करते हुए। चूंकि दोनों ends O(1) insertion support करते हैं, एक deque को एक stack, एक queue, या दोनों के रूप में एक साथ उपयोग किया जा सकता है इस आधार पर कि आप कौन सा end उपयोग करते हैं।

उदाहरण: Insert at Rear

#include <iostream>
#include <deque>
using namespace std;
int main() {
	deque<int> dq = {1, 2};
	dq.push_back(3);
	dq.push_back(4);
	for (int x : dq) cout << x << " ";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Deque<Integer> dq = new ArrayDeque<>(Arrays.asList(1, 2));
		dq.addLast(3);
		dq.addLast(4);
		System.out.println(dq);
	}
}

from collections import deque
dq = deque([1, 2])
dq.append(3)
dq.append(4)
print(list(dq))

#include <stdio.h>
int main() {
	int dq[4] = {1, 2, 3, 4};
	for (int i = 0; i < 4; i++) printf("%d ", dq[i]);
	return 0;
}

Deque as Stack

चूंकि यह दोनों ends support करता है, एक deque बिल्कुल एक stack की तरह behave कर सकता है सिर्फ consistently दोनों insertions और removals के लिए एक end उपयोग करके, push और pop दोनों उसी side पर होते हुए।

उदाहरण: Deque as Stack

#include <iostream>
#include <deque>
using namespace std;
int main() {
	deque<int> dq;
	dq.push_back(1); dq.push_back(2); dq.push_back(3);
	cout << "Popped: " << dq.back();
	dq.pop_back();
	cout << ", New top: " << dq.back();
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Deque<Integer> dq = new ArrayDeque<>();
		dq.addLast(1); dq.addLast(2); dq.addLast(3);
		System.out.print("Popped: " + dq.peekLast());
		dq.removeLast();
		System.out.println(", New top: " + dq.peekLast());
	}
}

from collections import deque
dq = deque()
dq.append(1); dq.append(2); dq.append(3)
print("Popped:", dq[-1])
dq.pop()
print("New top:", dq[-1])

#include <stdio.h>
int main() {
	int dq[3] = {1, 2, 3};
	int top = 2;
	printf("Popped: %d\n", dq[top]);
	top--;
	printf("New top: %d", dq[top]);
	return 0;
}

Deque Applications

Deques sliding-window problems (candidates की एक monotonic window maintain करना), undo/redo systems जिन्हें दोनों ends से जोड़ना और हटाना है, और दोनों boundaries पर efficient access चाहने वाले किसी भी scenario के लिए standard tool हैं।

उदाहरण: Deque Applications

#include <iostream>
#include <deque>
using namespace std;
int main() {
	int arr[] = {1, 3, -1, -3, 5};
	deque<int> dq;
	for (int i = 0; i < 5; i++) {
		while (!dq.empty() && arr[dq.back()] < arr[i]) dq.pop_back();
		dq.push_back(i);
		if (i >= 2) cout << arr[dq.front()] << " ";
	}
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {1, 3, -1, -3, 5};
		Deque<Integer> dq = new ArrayDeque<>();
		for (int i = 0; i < 5; i++) {
			while (!dq.isEmpty() && arr[dq.peekLast()] < arr[i]) dq.pollLast();
			dq.addLast(i);
			if (i >= 2) System.out.print(arr[dq.peekFirst()] + " ");
		}
	}
}

from collections import deque
arr = [1, 3, -1, -3, 5]
dq = deque()
for i in range(5):
    while dq and arr[dq[-1]] < arr[i]:
        dq.pop()
    dq.append(i)
    if i >= 2:
        print(arr[dq[0]], end=" ")

#include <stdio.h>
int main() {
	int arr[] = {1, 3, -1, -3, 5};
	int dq[5], front = 0, back = -1;
	for (int i = 0; i < 5; i++) {
		while (back >= front && arr[dq[back]] < arr[i]) back--;
		dq[++back] = i;
		if (i >= 2) printf("%d ", arr[dq[front]]);
	}
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Circular Queue Next Lesson → Priority Queue