স্ট্যাক (Stack)
স্ট্যাক LIFO হিসেবে ইমপ্লিমেন্ট হয় যেখানে ইনসার্শন এবং ডিলিশন একই এন্ড থেকে হয়, টপ। শেষে যে এলিমেন্ট ইন করবে, সেটি প্রথমে ডিলিট হবে।
স্ট্যাক অপারেশনগুলো -
- push(int data) - টপে ইনসার্শন
- int pop() - টপ থেকে ডিলিশন
কিউ (Queue)
কিউ FIFO হিসেবে ইমপ্লিমেন্ট হয় যেখানে ইনসার্শন একটি кінারে (রিয়ার) এবং ডিলিশন অন্য кінার থেকে (ফ্রন্ট) হয়। প্রথমে যে এলিমেন্ট ইন করবে, সেটি প্রথমে ডিলিট হবে।
কিউ অপারেশনগুলো -
- EnQueue(int data) - রিয়ার এন্ডে ইনসার্শন
- int DeQueue() - ফ্রন্ট এন্ড থেকে ডিলিশন
এটি দুটি কিউ ব্যবহার করে স্ট্যাক ইমপ্লিমেন্ট করার C++ প্রোগ্রাম।
অ্যালগরিদম
শুরু
enqueue1 ফাংশন - আইটেম a qu1-এ ইনসার্ট করতে:
np1 = new qu1 সেট করো
np1->d1 = a
np1->n1 = NULL
if (f1 == NULL)
তাহলে সেট করো
r1 = np1
r1->n1 = NULL
f1 = r1
অন্যথায়
r1->n1 = np1
r1 = np1
r1->n1 = NULL
শেষ
শুরু
dequeue1 ফাংশন - qu1 থেকে আইটেম ডিলিট করতে।
যদি কিউ নাল হয়
প্রিন্ট করো "no elements present in queue"।
অন্যথায়
q1 = f1
f1 = f1->n1
a = q1->d1
delete(q1)
return a
শেষ
শুরু
enqueue2 ফাংশন - আইটেম a qu2-এ ইনসার্ট করতে।
np2 = new qu2;
np2->d2 = a;
np2->n2 = NULL;
যদি কিউ নাল হয়
সেট করো r2 = np2
r2->n2 = NULL
f2 = r2
অন্যথায়
সেট করো r2->n2 = np2
r2 = np2
r2->n2 = NULL
শেষ
শুরু
dequeue2 ফাংশন - qu2 থেকে আইটেম ডিলিট করতে:
যদি কিউ নাল হয়
প্রিন্ট করো "no elements present in queue"।
অন্যথায়
q2 = f2
f2 = f2->n2
a = q2->d2
delete(q2)
return a
শেষউদাহরণ কোড
#include <iostream>
using namespace std;
struct qu1 { // queue1 ডিক্লেরেশন
qu1 *n1;
int d1;
}*f1 = NULL, *r1 = NULL, *q1 = NULL, *p1 = NULL, *np1 = NULL;
struct qu2 { // queue2 ডিক্লেরেশন
qu2 *n2;
int d2;
}*f2 = NULL, *r2 = NULL, *q2 = NULL, *p2 = NULL, *np2 = NULL;
void enqueue1(int a) {
np1 = new qu1;
np1->d1 = a;
np1->n1 = NULL;
if (f1 == NULL) {
r1 = np1;
r1->n1 = NULL;
f1 = r1;
} else {
r1->n1 = np1;
r1 = np1;
r1->n1 = NULL;
}
}
int dequeue1() {
int a;
if (f1 == NULL) {
cout << "no elements present in queue\n";
} else {
q1 = f1;
f1 = f1->n1;
a = q1->d1;
delete(q1);
return a;
}
}
void enqueue2(int a) {
np2 = new qu2;
np2->d2 = a;
np2->n2 = NULL;
if (f2 == NULL) {
r2 = np2;
r2->n2 = NULL;
f2 = r2;
} else {
r2->n2 = np2;
r2 = np2;
r2->n2 = NULL;
}
}
int dequeue2() {
int a;
if (f2 == NULL) {
cout << "no elements present in queue\n";
} else {
q2 = f2;
f2 = f2->n2;
a = q2->d2;
delete(q2);
return a;
}
}
int main() {
int n, a, i = 0;
cout << "Enter the number of elements to be entered into stack\n";
cin >> n;
while (i < n) {
cout << "enter the element to be entered\n";
cin >> a;
enqueue1(a);
i++;
}
cout << "\n\nElements popped\n\n";
while (f1 != NULL || f2 != NULL) { // যদি দুটি কিউ নাল না হয়
if (f2 == NULL) { // যদি কিউ ২ নাল হয়
while (f1->n1 != NULL) {
enqueue2(dequeue1());
}
cout << dequeue1() << endl;
} else if (f1 == NULL) { // যদি কিউ ১ নাল হয়
while (f2->n2 != NULL) {
enqueue1(dequeue2());
}
cout << dequeue2() << endl;
}
}
}আউটপুট
Enter the number of elements to be entered into stack: 5 enter the element to be entered: 1 enter the element to be entered: 2 enter the element to be entered: 3 enter the element to be entered: 4 enter the element to be entered: 5 Elements popped 5 4 3 2 1
