C++ मधील Deque किंवा डबल-एंडेड रांगेवरील सखोल ट्यूटोरियल. ट्यूटोरियल स्पष्ट करते की Deque काय आहे, मूलभूत ऑपरेशन्स, C++ & Java अंमलबजावणी आणि ऍप्लिकेशन्स:
दुहेरी समाप्त झालेली रांग किंवा फक्त "डेक" ही रांगेची सामान्यीकृत आवृत्ती आहे.
रांग आणि डेकमधील फरक हा आहे की ते FIFO चे अनुसरण करत नाही. (फर्स्ट इन, फर्स्ट आउट) दृष्टिकोन. Deque चे दुसरे वैशिष्ठ्य हे आहे की आपण समोर किंवा मागील बाजूस घटक घालू आणि काढू शकतो.
डबल एंडेड रांग वर्गीकरण
डेक हे करू शकते. खालीलप्रमाणे वर्गीकृत केले जावे:
इनपुट-प्रतिबंधित डेक: इनपुट-प्रतिबंधित, दोन्ही टोकांपासून हटविले जाऊ शकते परंतु समाविष्ट करणे केवळ मागील बाजूस केले जाऊ शकते. रांग.
आउटपुट-प्रतिबंधित डेक: आउटपुट-प्रतिबंधित रांगेत, दोन्ही टोकांपासून अंतर्भूत केले जाऊ शकते परंतु हटविणे केवळ एका टोकाला म्हणजेच रांगेच्या पुढच्या टोकाला केले जाते.
आम्ही डेक वापरून स्टॅक आणि रांगा देखील अंमलात आणू शकतो.
बेसिक डेक ऑपरेशन्स
खालील मूलभूत ऑपरेशन्स आहेत जे डेकवर करता येतात.
- समोर घाला: डेकच्या समोर एक आयटम घाला किंवा जोडा.
- इन्सर्ट लास्ट: येथे आयटम घाला किंवा जोडा डेकचा मागील भाग.
- पुढील भाग हटवा: रांगेच्या पुढील भागातून आयटम हटवा किंवा काढा.
- शेवटचा हटवा: हटवा किंवा काढा च्या मागील बाजूस असलेली वस्तूरांग.
- गेटफ्रंट: डेकमधील पुढील आयटम पुनर्प्राप्त करते.
- गेट लास्ट: रांगेतील शेवटचा आयटम पुनर्प्राप्त करते.
- रिक्त आहे: डेक रिकामे आहे का ते तपासते.
- पूर्ण आहे: डेक भरले आहे का ते तपासते.
डेक इलस्ट्रेशन
रिक्त डेक खालीलप्रमाणे दर्शविला जातो:
13>
पुढे, आम्ही घटक 1 समोर घालतो.
आता, आम्ही मागील बाजूस घटक 3 घालतो.
पुढे, आम्ही घटक 5 समोर जोडतो आणि जेव्हा पुढील बिंदू वाढवतो 4.
नंतर, आम्ही घटक 7 मागील बाजूस आणि 9 समोर घालतो. खाली दर्शविल्याप्रमाणे deque दिसेल.
पुढे, समोरून एक घटक काढून टाकूया.
अशा प्रकारे, आपण पाहतो की जेव्हा घटक समोर घातले जातात तेव्हा समोरची स्थिती कमी होते आणि घटक काढून टाकल्यावर ते वाढवले जाते. मागील टोकासाठी, स्थान समाविष्ट करण्यासाठी वाढविले जाते आणि काढण्यासाठी कमी केले जाते .
डेक अंमलबजावणी
C++ डेक अंमलबजावणी
आम्ही एक डेक लागू करू शकतो C++ मध्ये अॅरे तसेच लिंक केलेली सूची वापरून. याशिवाय, स्टँडर्ड टेम्प्लेट लायब्ररी (STL) मध्ये "deque" वर्ग आहे जो या डेटा स्ट्रक्चरसाठी सर्व कार्ये लागू करतो.
डेकची अॅरे अंमलबजावणी खाली दिली आहे. ही एक दुहेरी-एंडेड रांग असल्यामुळे आम्ही यासाठी परिपत्रक अॅरे वापरले आहेतअंमलबजावणी.
#includeusing 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() return ((front == 0 && rear == size-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!!\n" 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!!\n " 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!!\n" 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!!\n" 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!!\n" endl; return -1 ; } return array[front]; } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear 0) { cout " Underflow!!\n" endl; return -1 ; } return array[rear]; } //main program int main() { Deque dq(5); cout "Insert element 1 at rear end \n"; dq.insertrear(1); cout "insert element 3 at rear end \n"; 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 \n"; 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
deleterear नंतर, rear =
एलिमेंट 5 समोरच्या टोकाला घालत आहे
deque 5 चा फ्रंट एलिमेंट
डिलीटफ्रंट नंतर, समोर = 3
Java Deque अंमलबजावणी
Java मधील deque इंटरफेस, “java.util.Deque” हे “java.util.Queue” इंटरफेस वरून घेतले आहे. Deque रांग (फर्स्ट इन, फर्स्ट आउट) किंवा स्टॅक (लास्ट इन, फर्स्ट आउट) म्हणून वापरले जाऊ शकते. ही अंमलबजावणी लिंक केलेल्या सूचीपेक्षा जलद कार्य करते.
जावा मधील डेक इंटरफेसची पदानुक्रम खाली दिलेली आहे.
आम्हाला Java मधील Deque इंटरफेसबद्दल काही मुद्दे लक्षात ठेवण्याची गरज आहे:
- बाह्य सिंक्रोनाइझेशन नसल्यामुळे अंमलबजावणी थ्रेड-सेफ नाही.
- डेक असे नाही एकाधिक थ्रेड्सद्वारे समरूपतेचे समर्थन करा.
- अॅरे वापरून अंमलात आणलेले Deque NULL घटक वापरण्यास परवानगी देत नाही.
- अॅरेंना निर्बंधमुक्त क्षमता आणि आकार बदलता येण्याजोग्या अॅरे समर्थनासह, आवश्यकतेनुसार वाढण्याची परवानगी आहे. ही दोन सर्वात महत्त्वाची वैशिष्ट्ये आहेत.
डेक इंटरफेसद्वारे समर्थित विविध पद्धती खालीलप्रमाणे आहेत:
क्रमांक | पद्धत | वर्णन |
---|---|---|
1 | जोडा(घटक) | शेपटीला एक घटक जोडते. |
2 | addFirst(element) | मध्ये एक घटक जोडतेहेड/फ्रंट. |
3 | addLast(element) | शेपटी/मागील घटक जोडते. | 4 | ऑफर(घटक) | शेपटीला एक घटक जोडते; समाविष्ट करणे यशस्वी झाले की नाही हे सूचित करण्यासाठी बुलियन मूल्य मिळवते. |
5 | offerFirst(element) | हेडमध्ये एक घटक जोडते; समाविष्ट करणे यशस्वी झाले की नाही हे सूचित करण्यासाठी बुलियन मूल्य परत करते. |
6 | offerLast(element) | शेपटीला एक घटक जोडते; इन्सर्टेशन यशस्वी झाले की नाही हे सूचित करण्यासाठी बुलियन व्हॅल्यू मिळवते. |
7 | इटरेटर() | डेकसाठी इटरेटर मिळवते. |
8 | decendingIterator() | या डेकसाठी रिव्हर्स ऑर्डर असलेला पुनरावृत्तीकर्ता परत करतो. |
9 | पुश(एलिमेंट) | डेकच्या डोक्यावर एक घटक जोडतो. |
10 | पॉप(एलिमेंट) | डेकच्या डोक्यातून एक घटक काढून टाकतो आणि तो परत करतो. |
11 | रिमूव्ह फर्स्ट() | वर घटक काढून टाकतो डेकचे हेड. |
12 | removeLast() | डेकच्या शेपटीवरील घटक काढून टाकते. |
13 | पोल() | डेकचा पहिला घटक पुनर्प्राप्त करतो आणि काढून टाकतो (डेकच्या प्रमुखाद्वारे दर्शविला जातो); डेक रिक्त असल्यास NULL मिळवते. |
14 | पोलफर्स्ट() | या डेकचा पहिला घटक पुनर्प्राप्त करते आणि काढून टाकते; हा deque असल्यास शून्य परत करतोरिक्त. |
15 | पोललास्ट() | या डीकचा शेवटचा घटक पुनर्प्राप्त करतो आणि काढून टाकतो; हा डेक रिकामा असल्यास शून्य परत करतो. |
16 | पीक() | प्रस्तुत केलेल्या रांगेचे हेड (डेकचा पहिला घटक) पुनर्प्राप्त करते या डेकद्वारे; हा डेक रिकामा असल्यास शून्य परत करतो. टीप: हे ऑपरेशन घटक काढून टाकत नाही. |
17 | peekFirst() | या डेकचा पहिला घटक पुनर्प्राप्त करते; हा deque रिकामा असल्यास शून्य परत करतो. टीप: हे ऑपरेशन घटक काढून टाकत नाही. |
18 | peekLast() | या डीकचा शेवटचा घटक पुनर्प्राप्त करते किंवा हा डीक रिकामा असल्यास शून्य मिळवते. टीप: हे ऑपरेशन घटक काढून टाकत नाही. |
खालील Java अंमलबजावणी वर चर्चा केलेल्या विविध ऑपरेशन्सचे प्रात्यक्षिक करते.
import java.util.*; class Main { public static void main(String[] args) { Dequedeque = 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 + "\n"); // 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("\nReverse Iterator"); while (reverse.hasNext()) System.out.print(" " + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println("\n\nPeek " + deque.peek()); System.out.println("After peek: " + deque); // Pop returns the head, and removes it from // the deque System.out.println("\nPop " + deque.pop()); System.out.println("After pop: " + deque); // We can check if a specific element exists // in the deque System.out.println("\nContains 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]
मानक इटेरेटर
11 7 3 1 5 9 13
रिव्हर्स इटेरेटर
13 9 5 1 3 7 1
पीक 11
पीक नंतर: [11, 7, 3, 1, 5, 9, 13]
पॉप 11
पॉप नंतर: [7, 3, 1, 5, 9, 13]
घटक 3 समाविष्ट आहे?: सत्य
पहिले आणि शेवटचे घटक काढल्यानंतर डेक: [3, 1, 5, 9]
3
वरील प्रोग्राममध्ये, आम्ही Java चा Deque इंटरफेस वापरला आहे आणि आम्ही पूर्णांक घटकांचा deque परिभाषित केला आहे. मग आम्ही या डेकवर विविध ऑपरेशन्स केल्या आणि या ऑपरेशन्सचे परिणाम आउटपुट केलेप्रदर्शित.
अॅप्लिकेशन्स
डेक खालीलपैकी काही अॅप्लिकेशन्समध्ये वापरले जाऊ शकतात.
#1) शेड्युलिंग अल्गोरिदम: शेड्युलिंग अल्गोरिदम, “ए-स्टील शेड्युलिंग अल्गोरिदम” मल्टीप्रोसेसर सिस्टममधील विविध प्रोसेसरसाठी टास्क शेड्यूलिंग लागू करते. ही अंमलबजावणी deque वापरते आणि प्रोसेसरला अंमलबजावणीसाठी deque मधून पहिला घटक मिळतो.
#2) क्रियाकलापांची यादी पूर्ववत करा: सॉफ्टवेअर अॅप्लिकेशन्समध्ये, आमच्याकडे अनेक क्रिया आहेत. एक म्हणजे "पूर्ववत करा". जेव्हा आम्ही अनेक वेळा पूर्ववत क्रिया केली, तेव्हा या सर्व क्रिया सूचीमध्ये संग्रहित केल्या जातात. ही यादी डेक म्हणून ठेवली जाते जेणेकरून आम्ही कोणत्याही टोकापासून एंट्री सहजपणे जोडू/काढू शकू.
#3) काही वेळाने नोंदी काढून टाका: अॅप्स रिफ्रेश त्यांच्या यादीतील नोंदी जसे की अॅप्स स्टॉक एंट्रींची सूची इ. हे अॅप्स काही काळानंतर नोंदी काढून टाकतात आणि नवीन नोंदी देखील टाकतात. हे deque वापरून केले जाते.
निष्कर्ष
Deque ही एक दुहेरी-एंडेड रांग आहे जी आम्हाला रांगेच्या समोर आणि मागील दोन्ही टोकांपासून घटक जोडू/काढू देते. अॅरे किंवा लिंक केलेल्या याद्या वापरून डेक लागू केले जाऊ शकते. तथापि, आमच्याकडे स्टँडर्ड टेम्प्लेट लायब्ररी (STL) क्लास देखील आहे जो Deque च्या विविध ऑपरेशन्सची अंमलबजावणी करतो.
जावामध्ये, आमच्याकडे एक Deque इंटरफेस आहे जो Deque लागू करण्यासाठी क्यू इंटरफेस मधून वारसा मिळाला आहे. Deque च्या मूलभूत मानक ऑपरेशन्स व्यतिरिक्त, हा इंटरफेस विविध सपोर्ट करतोइतर ऑपरेशन्स जे Deque वर केले जाऊ शकतात.
Deque चा वापर सामान्यतः अशा ऍप्लिकेशन्ससाठी केला जातो ज्यांना दोन्ही टोकांपासून घटक जोडणे/काढणे आवश्यक असते. मल्टी-प्रोसेसर सिस्टीममध्ये प्रोसेसरच्या शेड्यूलिंगमध्ये देखील याचा वापर केला जातो.
पूर्ण C++ प्रशिक्षण मालिका पहा