- Double Ended Queue Classification
- বেসিক ডিক অপারেশনগুলি
- Deque ইলাস্ট্রেশন
- ডেক ইমপ্লিমেন্টেশন
- অ্যাপ্লিকেশনগুলি
- উপসংহার
C++ এ Deque বা ডাবল-এন্ডেড কিউ এর উপর একটি গভীর টিউটোরিয়াল। টিউটোরিয়াল ব্যাখ্যা করে Deque কি, বেসিক অপারেশন, C++ & জাভা ইমপ্লিমেন্টেশন এবং অ্যাপ্লিকেশান:
ডাবল এন্ডেড কিউ বা সহজভাবে বলা হয় "ডিক" হল সারির একটি সাধারণ সংস্করণ৷
সারি এবং ডিকের মধ্যে পার্থক্য হল এটি FIFO অনুসরণ করে না (ফার্স্ট ইন, ফার্স্ট আউট) পদ্ধতি। Deque-এর দ্বিতীয় বৈশিষ্ট্য হল যে আমরা সামনের বা পিছনের প্রান্ত থেকে উপাদানগুলি সন্নিবেশ করাতে এবং সরাতে পারি৷
Double Ended Queue Classification
Deque করতে পারে নিম্নরূপ শ্রেণীবদ্ধ করা হবে:
ইনপুট-সীমাবদ্ধ Deque: ইনপুট-সীমাবদ্ধ, উভয় প্রান্ত থেকে মুছে ফেলা যেতে পারে কিন্তু সন্নিবেশ শুধুমাত্র পিছনের প্রান্তে করা যেতে পারে সারি।
আউটপুট-সীমাবদ্ধ ডিক: আউটপুট-সীমাবদ্ধ সারিতে, উভয় প্রান্ত থেকে সন্নিবেশ করা যেতে পারে তবে মুছে ফেলা শুধুমাত্র এক প্রান্তে অর্থাৎ সারির সামনের প্রান্তে করা হয়।
আমরা deque ব্যবহার করে স্ট্যাক এবং সারিগুলিও প্রয়োগ করতে পারি৷
বেসিক ডিক অপারেশনগুলি
নিম্নলিখিত মৌলিক ক্রিয়াকলাপগুলি যা deque এ সম্পাদিত হতে পারে৷
- সামনে সন্নিবেশ করান: ডেকের সামনে একটি আইটেম ঢোকান বা যোগ করুন।
- ঢোকান শেষ: এ একটি আইটেম ঢোকান বা যোগ করুন ডিক এর পিছনে।
- মুছুন ফ্রন্ট: সারির সামনে থেকে আইটেমটি মুছুন বা সরান।
- শেষটি মুছুন: মুছুন বা সরান এর পিছন থেকে আইটেমসারি।
- গেটফ্রন্ট: ডিকিউতে সামনের আইটেমটি পুনরুদ্ধার করে।
- গেট লাস্ট: সারিতে থাকা শেষ আইটেমটি উদ্ধার করে।
- isEmpty: deque খালি আছে কিনা তা পরীক্ষা করে।
- Full: deque পূর্ণ কিনা তা পরীক্ষা করে।
Deque ইলাস্ট্রেশন
একটি খালি ডেক নিম্নরূপ উপস্থাপন করা হয়:
13>
পরবর্তীতে, আমরা এলিমেন্ট 1 সামনে সন্নিবেশ করি।
এখন, আমরা পিছনের অংশে 3 উপাদান সন্নিবেশ করি।
পরবর্তীতে, আমরা এলিমেন্ট 5 যুক্ত করি সামনে এবং যখন সামনের পয়েন্টগুলিকে বৃদ্ধি করি 4.
তারপর, আমরা পিছনের অংশে 7 এবং সামনে 9টি উপাদান সন্নিবেশ করি। ডিক নিচের মত দেখাবে।
এরপর, সামনে থেকে একটি উপাদান সরিয়ে ফেলি।
এইভাবে, আমরা দেখতে পাই যে যখন উপাদানগুলি সম্মুখে ঢোকানো হয়, তখন সামনের অবস্থানটি হ্রাস পায় যখন একটি উপাদান সরানো হয় তখন এটি বৃদ্ধি পায়। পিছনের প্রান্তের জন্য, সন্নিবেশের জন্য অবস্থান বৃদ্ধি করা হয় এবং অপসারণের জন্য হ্রাস করা হয় ।
ডেক ইমপ্লিমেন্টেশন
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.util.Deque" "java.util.Queue" ইন্টারফেস থেকে উদ্ভূত হয়েছে। Deque একটি সারি (First In, First Out) বা একটি স্ট্যাক (Last In, First Out) হিসাবে ব্যবহার করা যেতে পারে। এই বাস্তবায়নগুলি লিঙ্ক করা তালিকার চেয়ে দ্রুত কাজ করে৷
নিচে দেওয়া হল জাভাতে Deque ইন্টারফেসের অনুক্রমটি৷
আমাদের জাভাতে Deque ইন্টারফেস সম্পর্কে কয়েকটি পয়েন্ট মনে রাখতে হবে:
- বাস্তবায়নটি থ্রেড-নিরাপদ নয় কারণ কোনও বাহ্যিক সিঙ্ক্রোনাইজেশন নেই।
- ডেক করে না একাধিক থ্রেডের দ্বারা সমঝোতা সমর্থন করে।
- অ্যারে ব্যবহার করে প্রয়োগ করা Deque NULL উপাদান ব্যবহারের অনুমতি দেয় না।
- অ্যারেগুলিকে সীমাবদ্ধতা-মুক্ত ক্ষমতা এবং আকার পরিবর্তনযোগ্য অ্যারে সমর্থন সহ প্রয়োজনীয়তা অনুযায়ী বৃদ্ধি পেতে দেওয়া হয়। সবচেয়ে গুরুত্বপূর্ণ দুটি বৈশিষ্ট্য।
নিম্নলিখিত বিভিন্ন পদ্ধতি রয়েছে যা Deque ইন্টারফেস দ্বারা সমর্থিত:
| নং | পদ্ধতি | বিবরণ |
|---|---|---|
| 1 | add(element) | টেইলে একটি উপাদান যোগ করে। |
| 2 | addFirst(element) | এ একটি উপাদান যোগ করেহেড/সামনে। |
| 3 | addLast(element) | লেজ/পিছনে একটি উপাদান যোগ করে। | 4 | অফার(উপাদান) | টেলে একটি উপাদান যোগ করে; সন্নিবেশ সফল হয়েছে কিনা তা নির্দেশ করতে একটি বুলিয়ান মান প্রদান করে। |
| 5 | offerFirst(element) | হেডে একটি উপাদান যোগ করে; সন্নিবেশ সফল হয়েছে কিনা তা নির্দেশ করার জন্য একটি বুলিয়ান মান প্রদান করে। |
| 6 | offerLast(element) | টেলে একটি উপাদান যোগ করে; সন্নিবেশ সফল হয়েছে কিনা তা নির্দেশ করার জন্য একটি বুলিয়ান মান প্রদান করে। |
| 7 | ইটারেটর() | ডেকের জন্য একটি পুনরাবৃত্তিকারী প্রদান করে। |
| 8 | decendingIterator() | একটি ইটারেটর রিটার্ন করে যার এই ডেকটির বিপরীত ক্রম রয়েছে। |
| 9 | পুশ(এলিমেন্ট) | ডেকের মাথায় একটি এলিমেন্ট যোগ করে। |
| 10 | পপ(এলিমেন্ট) | ডিক এর মাথা থেকে একটি উপাদান সরিয়ে দেয় এবং এটি ফেরত দেয়। |
| 11 | রিমুভ ফার্স্ট() | এ উপাদানটিকে সরিয়ে দেয় deque এর মাথা। |
| 12 | removeLast() | deque এর লেজের এলিমেন্ট সরিয়ে দেয়। |
| 13 | পোল() | ডেকের প্রথম উপাদানটি পুনরুদ্ধার করে এবং সরিয়ে দেয় (ডেকের প্রধান দ্বারা প্রতিনিধিত্ব করা হয়); ডিক খালি থাকলে NULL প্রদান করে। |
| 14 | pollFirst() | এই ডিকটির প্রথম উপাদান উদ্ধার করে এবং সরিয়ে দেয়; এই deque হলে নাল ফেরত দেয়খালি৷ |
| 15 | pollLast() | এই ডিকটির শেষ উপাদানটি পুনরুদ্ধার করে এবং সরিয়ে দেয়; এই ডেক খালি থাকলে নাল রিটার্ন করে। |
| 16 | পিক() | উপস্থাপিত সারির হেড (ডেকের প্রথম উপাদান) উদ্ধার করে এই deque দ্বারা; এই ডিক খালি থাকলে নাল রিটার্ন করে৷ দ্রষ্টব্য: এই অপারেশনটি উপাদানটিকে সরিয়ে দেয় না৷ |
| 17 | পিক ফার্স্ট() | এই ডিকটির প্রথম উপাদানটি পুনরুদ্ধার করে; এই ডিক খালি থাকলে নাল রিটার্ন করে৷ দ্রষ্টব্য: এই অপারেশনটি উপাদানটিকে সরিয়ে দেয় না৷ |
| 18 | পিক লাস্ট() | এই ডিকটির শেষ উপাদানটি পুনরুদ্ধার করে, অথবা এই ডিকটি খালি থাকলে শূন্য প্রদান করে। দ্রষ্টব্য: এই অপারেশনটি উপাদানটিকে সরিয়ে দেয় না। |
নিম্নলিখিত জাভা বাস্তবায়ন উপরে আলোচনা করা বিভিন্ন ক্রিয়াকলাপ প্রদর্শন করে।
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]
উপরের প্রোগ্রামে, আমরা জাভার Deque ইন্টারফেস ব্যবহার করেছি এবং আমরা পূর্ণসংখ্যা উপাদানগুলির একটি deque সংজ্ঞায়িত করেছি। তারপরে আমরা এই ডিকটিতে বিভিন্ন অপারেশন করেছি এবং এই অপারেশনগুলির ফলাফলগুলি আউটপুটপ্রদর্শিত হয়৷
অ্যাপ্লিকেশনগুলি
নিম্নলিখিত কয়েকটি অ্যাপ্লিকেশনে Deque ব্যবহার করা যেতে পারে৷
#1) শিডিউলিং অ্যালগরিদম: একটি শিডিউলিং অ্যালগরিদম, "এ-স্টিল শিডিউলিং অ্যালগরিদম" মাল্টিপ্রসেসর সিস্টেমে বিভিন্ন প্রসেসরের জন্য টাস্ক শিডিউলিং প্রয়োগ করে। এই ইমপ্লিমেন্টেশনটি deque ব্যবহার করে এবং প্রসেসর এক্সিকিউশনের জন্য deque থেকে প্রথম উপাদান পায়।
#2) ক্রিয়াকলাপগুলির তালিকা পূর্বাবস্থায় ফেরান: সফ্টওয়্যার অ্যাপ্লিকেশনগুলিতে, আমাদের অনেকগুলি অ্যাকশন রয়েছে। একটি হল "আনডু"। যখন আমরা অনেকবার পূর্বাবস্থায় ক্রিয়া সম্পাদন করি, তখন এই সমস্ত ক্রিয়াগুলি একটি তালিকায় সংরক্ষণ করা হয়। এই তালিকাটি একটি ডেক হিসাবে রক্ষণাবেক্ষণ করা হয়েছে যাতে আমরা সহজেই যেকোনো প্রান্ত থেকে এন্ট্রিগুলি যোগ/মুছে ফেলতে পারি।
#3) কিছু সময় পরে এন্ট্রিগুলি সরান: অ্যাপস রিফ্রেশ তাদের তালিকার এন্ট্রি যেমন অ্যাপ স্টক এন্ট্রি তালিকাভুক্ত করে, ইত্যাদি। এটি একটি deque ব্যবহার করে করা হয়।
উপসংহার
Deque হল একটি ডবল-এন্ডেড সারি যা আমাদেরকে সারির সামনে এবং পিছনের উভয় প্রান্ত থেকে উপাদান যোগ/সরানোর অনুমতি দেয়। Deque অ্যারে বা লিঙ্ক তালিকা ব্যবহার করে বাস্তবায়ন করা যেতে পারে. যাইহোক, আমাদের একটি স্ট্যান্ডার্ড টেমপ্লেট লাইব্রেরি (STL) ক্লাস রয়েছে যা Deque-এর বিভিন্ন ক্রিয়াকলাপ বাস্তবায়ন করে৷
জাভাতে, আমাদের কাছে একটি Deque ইন্টারফেস রয়েছে যা Deque বাস্তবায়নের জন্য কিউ ইন্টারফেস থেকে উত্তরাধিকারসূত্রে পাওয়া যায়৷ Deque এর মৌলিক স্ট্যান্ডার্ড অপারেশন ছাড়াও, এই ইন্টারফেস বিভিন্ন সমর্থন করেঅন্যান্য ক্রিয়াকলাপ যা Deque-এ করা যেতে পারে।
Deque সাধারণত এমন অ্যাপ্লিকেশনগুলির জন্য ব্যবহৃত হয় যেগুলির উভয় প্রান্ত থেকে উপাদান যোগ করা/মুছে ফেলা প্রয়োজন। এটি বেশিরভাগ মাল্টি-প্রসেসর সিস্টেমে প্রসেসরের সময়সূচীতেও ব্যবহৃত হয়৷
সম্পূর্ণ C++ প্রশিক্ষণ সিরিজটি দেখুন