double ended queue c with examples
C ++ में Deque या डबल-एंड क्यू पर एक इन-डेप्थ ट्यूटोरियल। ट्यूटोरियल समझाता है कि Deque, बेसिक ऑपरेशंस, C ++ और Java कार्यान्वयन और अनुप्रयोग क्या हैं:
डबल समाप्त कतार या बस 'Deque' कतार का एक सामान्यीकृत संस्करण है।
क्यू और डीके के बीच अंतर यह है कि यह फीफो (फर्स्ट इन, फर्स्ट आउट) दृष्टिकोण का पालन नहीं करता है। Deque की दूसरी विशेषता यह है कि हम तत्वों को सामने या पीछे के छोर से सम्मिलित और हटा सकते हैं।
=> आसान सी ++ प्रशिक्षण श्रृंखला के माध्यम से पढ़ें
आप क्या सीखेंगे:
- डबल एंडेड कतार वर्गीकरण
- बुनियादी स्पर्श संचालन
- और चित्रण
- और कार्यान्वयन
- अनुप्रयोग
- निष्कर्ष
- अनुशंसित पाठ
डबल एंडेड कतार वर्गीकरण
Deque को निम्नानुसार वर्गीकृत किया जा सकता है:
प्रतिबंधित-स्पर्श इनपुट; इनपुट-प्रतिबंधित में, विलोपन दोनों सिरों से किया जा सकता है लेकिन सम्मिलन केवल कतार के पीछे के छोर पर किया जा सकता है।
आउटपुट-प्रतिबंधित Deque: आउटपुट-प्रतिबंधित कतार में, सम्मिलन दोनों सिरों से किया जा सकता है लेकिन विलोपन केवल एक छोर पर किया जाता है यानी कतार के सामने का छोर।
हम भी deque का उपयोग करके ढेर और कतारों को लागू कर सकते हैं।
बुनियादी स्पर्श संचालन
निम्नलिखित मूल संचालन हैं जो कि deque पर किए जा सकते हैं।
- सामने डालें: मृग के सामने एक वस्तु डालें या जोड़ें।
- सम्मिलित करें: छल के पीछे एक आइटम डालें या जोड़ें।
- हटाएं: पंक्ति के सामने से आइटम हटाएं या निकालें।
- अंतिम हटाएं: पंक्ति के पीछे से आइटम हटाएं या निकालें।
- GetFront: छल में सामने की वस्तु को पुनः प्राप्त करता है।
- अंतिम लो: कतार में अंतिम आइटम निकालता है।
- खाली है: जाँच करता है कि क्या रिक्त स्थान खाली है।
- पूर्ण है: चेक करता है कि क्या फुल भरा हुआ है।
और चित्रण
एक खाली डॉक को निम्नानुसार दर्शाया गया है:
व्यापार विश्लेषक साक्षात्कार और बैंकिंग डोमेन के लिए उत्तर देते हैं
अगला, हम सामने 1 पर तत्व 1 सम्मिलित करते हैं।
अब, हम पीछे के तत्व 3 को सम्मिलित करते हैं।
अगला, हम तत्व 5 को सामने से जोड़ते हैं और जब सामने वाले अंक को बढ़ाकर 4 करते हैं।
फिर, हम तत्वों को पीछे की तरफ 7 और सामने की तरफ 9 डालें। नीचे दी गई के रूप में दिखाया गया है।
अगला, हमें सामने से एक तत्व निकालने दें।
इस प्रकार, हम देखते हैं कि जब तत्वों को सामने रखा जाता है, तो सामने की स्थिति को हटा दिया जाता है जबकि किसी तत्व को हटाए जाने पर इसे बढ़ाया जाता है। पीछे के छोर के लिए, स्थिति सम्मिलन के लिए बढ़ाई जाती है और हटाने के लिए डीग्रेड की जाती है ।
और कार्यान्वयन
100 ++ स्पर्श कार्यान्वयन
हम सरणियों के साथ-साथ लिंक की गई सूची का उपयोग करके सी ++ में एक छल को लागू कर सकते हैं। इसके अलावा, मानक टेम्पलेट लाइब्रेरी (एसटीएल) में एक वर्ग है 'deque' जो इस डेटा संरचना के लिए सभी कार्यों को लागू करता है।
नीचे दिए गए सरणी का सरणी कार्यान्वयन दिया गया है। जैसा कि यह एक डबल-एंडेड कतार है, हमने कार्यान्वयन के लिए परिपत्र सरणियों का उपयोग किया है।
#include using namespace std; #define MAX_size 10 // Maximum size of array or Dequeue // Deque class class Deque { int array(MAX_size); int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Check if Deque is full bool isFull()front == rear+1); // Check if Deque is empty bool isEmpty(){ return (front == -1); } }; // Insert an element at front of the deque void Deque::insertfront(int key) { if (isFull()) { cout << 'Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front is first position of queue front = size - 1 ; else // decrement front 1 position front = front-1; array(front) = key ; // insert current element into Deque } // insert element at the rear end of deque void Deque ::insertrear(int key) { if (isFull()) { cout << ' Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (rear == size-1) // rear is at last position of queue rear = 0; else // increment rear by 1 position rear = rear+1; array(rear) = key ; // insert current element into Deque } // Delete element at front of Deque void Deque ::deletefront() { if (isEmpty()) { cout << 'Queue Underflow!!
' << endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // remove current front value from Deque;increment front by 1 front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout << ' Underflow!!
' << endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // retrieve front element of Deque int Deque::getFront() { if (isEmpty()) { cout << ' Underflow!!
' << endl; return -1 ; } return array(front); } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear < 0) { cout << ' Underflow!!
' << endl; return -1 ; } return array(rear); } //main program int main() { Deque dq(5); cout << 'Insert element 1 at rear end
'; dq.insertrear(1); cout << 'insert element 3 at rear end
'; dq.insertrear(3); cout << 'rear element of deque ' << ' ' << dq.getRear() << endl; dq.deleterear(); cout << 'After deleterear, rear = ' << dq.getRear() << endl; cout << 'inserting element 5 at front end
'; dq.insertfront(5); cout << 'front element of deque ' << ' ' << dq.getFront() << endl; dq.deletefront(); cout << 'After deletefront, front = ' << dq.getFront() << endl; return 0; } आउटपुट:
पीछे के छोर पर तत्व 1 डालें
पीछे के अंत में तत्व 3 डालें
deque 3 का पिछला तत्व
pdf फाइल को कैसे खोला जाता है
दोष रहित होने के बाद, पीछे = 1
सामने के अंत में 5 तत्व डालने
छल का सामने का तत्व ५
हटाने के बाद, सामने = 1
जावा कार्यान्वयन भर्ती
Java में deque इंटरफ़ेस, 'java.util.Deque' 'java.util.Queue' इंटरफ़ेस से लिया गया है। Deque को एक कतार (First In, First Out) या एक स्टैक (Last In, First Out) के रूप में उपयोग किया जा सकता है। ये कार्यान्वयन लिंक्ड सूची की तुलना में तेजी से काम करते हैं।
नीचे दिए गए जावा में Deque इंटरफ़ेस के लिए पदानुक्रम है।
हमें जावा में Deque इंटरफ़ेस के बारे में कुछ बिंदुओं को याद रखना होगा:
- कार्यान्वयन थ्रेड-सुरक्षित नहीं है क्योंकि कोई बाहरी सिंक्रनाइज़ेशन नहीं है।
- Deque कई थ्रेड्स द्वारा concurrency का समर्थन नहीं करता है।
- सरणियों का उपयोग करके Deque का कार्यान्वित होना NULL तत्वों के उपयोग की अनुमति नहीं देता है।
- प्रतिबंधों को आवश्यकताओं के अनुसार बढ़ने की अनुमति है, प्रतिबंध-मुक्त क्षमता और resizable सरणी समर्थन दो सबसे महत्वपूर्ण विशेषताएं हैं।
Deque इंटरफ़ेस द्वारा समर्थित विभिन्न विधियाँ निम्नलिखित हैं:
बाकी वेब सेवा का परीक्षण करने के लिए उपकरण
| ऐसा न करें। | तरीका | विवरण |
|---|---|---|
| । | पुनरावृति () | छल के लिए एक पुनरावृत्ति देता है। |
| 1 | जोड़ें (तत्व) | एक तत्व को पूंछ में जोड़ता है। |
| दो | addFirst (तत्व) | एक तत्व को सिर / सामने जोड़ता है। |
| ३ | addLast (तत्व) | एक तत्व को पूंछ / पीछे जोड़ता है। |
| ४ | प्रस्ताव (तत्व) | एक तत्व को पूंछ में जोड़ता है; यदि प्रविष्टि सफल थी, तो इंगित करने के लिए बूलियन मान लौटाता है। |
| ५ | ऑफ़रफ़र्स्ट (तत्व) | एक तत्व को सिर में जोड़ता है; यदि प्रविष्टि सफल थी, तो इंगित करने के लिए बूलियन मान लौटाता है। |
| ६ | ऑफ़रलैस्ट (तत्व) | एक तत्व को पूंछ में जोड़ता है; यदि प्रविष्टि सफल थी, तो इंगित करने के लिए बूलियन मान लौटाता है। |
| । | अवरोही () | एक पुनरावर्तक लौटाता है जिसके पास इस आदेश के लिए रिवर्स ऑर्डर है। |
| ९ | धक्का (तत्व) | एक तत्व को deque के सिर में जोड़ता है। |
| १० | पॉप (तत्व) | एक तत्व को छल के सिर से निकालकर वापस कर देता है। |
| ग्यारह | निकालें () | तत्व को मृग के सिर पर से हटाता है। |
| १२ | निष्कासन () | तत्व को मृग की पूंछ पर हटा देता है। |
| १३ | पोल () | हटाता है और पहले तत्व को हटाता है (deque के प्रमुख द्वारा दर्शाया गया है); यदि रिक्त रिक्त है तो NULL लौटाता है। |
| १४ | प्रदूषित () | इस छल के पहले तत्व को निकालता है और हटाता है; यदि यह रिक्त स्थान खाली है, तो अशक्त देता है। |
| पंद्रह | पोलस्टैस्ट () | इस विलेख के अंतिम तत्व को निकालता है और हटाता है; यदि यह रिक्त स्थान खाली है, तो अशक्त देता है। |
| १६ | झांकना () | इस deque द्वारा दर्शाई गई कतार के शीर्ष (पहले तत्व) को पुनः प्राप्त करता है; यदि यह रिक्त स्थान खाली है, तो अशक्त देता है। नोट: यह ऑपरेशन तत्व को नहीं हटाता है। |
| १। | झांकना () | इस छल के पहले तत्व को पुनः प्राप्त करता है; यदि यह रिक्त स्थान खाली है, तो अशक्त देता है। नोट: यह ऑपरेशन तत्व को नहीं हटाता है। |
| १। | झांकना () | यदि इस रिक्त स्थान को खाली है, तो इस deque के अंतिम तत्व को पुनर्प्राप्त करता है, या अशक्त करता है। नोट: यह ऑपरेशन तत्व को नहीं हटाता है। |
निम्नलिखित जावा कार्यान्वयन ऊपर चर्चा किए गए विभिन्न कार्यों को प्रदर्शित करता है।
import java.util.*; class Main { public static void main(String() args) { Deque deque = new LinkedList (); // We can add elements to the queue in various ways deque.add(1); // add to tail deque.addFirst(3); deque.addLast(5); deque.push(7); //add to head deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println('The deque : ' + deque + '
'); // Iterate through the queue elements. System.out.println('Standard Iterator'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println('
Reverse Iterator'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println('
Peek ' + deque.peek()); System.out.println('After peek: ' + deque); // Pop returns the head, and removes it from // the deque System.out.println('
Pop ' + deque.pop()); System.out.println('After pop: ' + deque); // We can check if a specific element exists // in the deque System.out.println('
Contains element 3?: ' + deque.contains(3)); // We can remove the first / last element. deque.removeFirst(); deque.removeLast(); System.out.println('Deque after removing ' + 'first and last elements: ' + deque); } } आउटपुट:
और (11, 7, 3, 1, 5, 9, 13)
मानक Iterator
११ 11 ३ १ ५ ९ १३
रिवर्स इटरेटर
१३ ९ ५ १ ३ ३। ११
झांकना ११
झांकने के बाद: (11, 7, 3, 1, 5, 9, 13)
पॉप 11
पॉप के बाद: (7, 3, 1, 5, 9, 13)
तत्व 3 शामिल हैं ?: सच
पहले और आखिरी तत्वों को हटाने के बाद हटें: (३, १, ५, ९)
उपर्युक्त कार्यक्रम में, हमने जावा के Deque इंटरफ़ेस का उपयोग किया है और हमने पूर्णांक तत्वों के एक deque को परिभाषित किया है। फिर हमने इस deque पर विभिन्न ऑपरेशन किए और इन ऑपरेशनों के परिणाम प्रदर्शित किए गए।
अनुप्रयोग
निम्न में से कुछ अनुप्रयोगों में Deque का उपयोग किया जा सकता है।
# 1) निर्धारण एल्गोरिथम: एक शेड्यूलिंग एल्गोरिथ्म, 'ए-स्टिल शेड्यूलिंग एल्गोरिथ्म' मल्टीप्रोसेसर सिस्टम में विभिन्न प्रोसेसर के लिए कार्य शेड्यूलिंग को लागू करता है। इस कार्यान्वयन में डीके का उपयोग किया गया है और प्रोसेसर को निष्पादन के लिए डीके से पहला तत्व प्राप्त होता है।
# 2) गतिविधियों की पूर्ववत सूची: सॉफ्टवेयर अनुप्रयोगों में, हमारे पास कई क्रियाएं हैं। एक 'पूर्ववत' है। जब हमने कई बार पूर्ववत कार्रवाई की है, तो ये सभी क्रियाएं एक सूची में संग्रहीत हैं। इस सूची को एक छल के रूप में बनाए रखा गया है ताकि हम किसी भी छोर से प्रविष्टियों को आसानी से जोड़ / हटा सकें।
# 3) कुछ समय बाद प्रविष्टियाँ निकालें: एप्स अपनी सूची में प्रविष्टियों को ताज़ा करते हैं जैसे कि स्टॉक प्रविष्टियों को सूचीबद्ध करने वाले ऐप आदि। ये ऐप कुछ समय बाद प्रविष्टियों को हटा देते हैं और नई प्रविष्टियाँ भी डालते हैं। यह एक छल का उपयोग करके किया जाता है।
निष्कर्ष
Deque एक डबल-एंडेड कतार है, जो हमें कतार के दोनों सिरों यानी सामने और पीछे के तत्वों को जोड़ने / हटाने की अनुमति देता है। ऐरे या लिंक्ड लिस्ट का उपयोग करके डीके लागू किया जा सकता है। हालाँकि, हमारे पास एक मानक टेम्प्लेट लाइब्रेरी (एसटीएल) वर्ग भी है जो डीके के विभिन्न कार्यों को कार्यान्वित करता है।
जावा में, हमारे पास एक Deque इंटरफ़ेस है जो Deque को कार्यान्वित करने के लिए कतार इंटरफ़ेस से विरासत में मिला है। डेके के बुनियादी मानक संचालन के अलावा, यह इंटरफ़ेस विभिन्न अन्य ऑपरेशनों का समर्थन करता है जिन्हें डीके पर किया जा सकता है।
Deque का उपयोग आम तौर पर उन अनुप्रयोगों के लिए किया जाता है जिन्हें दोनों सिरों से तत्वों को जोड़ने / हटाने की आवश्यकता होती है। यह बहु-प्रोसेसर प्रणालियों में प्रोसेसर के निर्धारण में भी ज्यादातर उपयोग किया जाता है।
=> पूर्ण सी ++ प्रशिक्षण श्रृंखला देखें
अनुशंसित पाठ
- एसटीएल में प्राथमिकता कतार
- तुलना परीक्षण क्या है (उदाहरण के साथ जानें)
- उदाहरणों के साथ पायथन डेटटाइम ट्यूटोरियल
- शैल C ++ में उदाहरणों के साथ
- उदाहरणों के साथ यूनिक्स में कमान काटें
- यूनिक्स कैट कमांड सिंटैक्स, उदाहरण के साथ विकल्प
- उदाहरणों के साथ MongoDB में कर्सर का उपयोग
- उदाहरणों के साथ यूनिक्स में Ls कमांड