স্ট্যাক (Stack)
স্ট্যাক LIFO হিসেবে ইমপ্লিমেন্ট হয় যেখানে ইনসার্শন এবং ডিলিশন একই এন্ড থেকে হয়, টপ। শেষে যে এলিমেন্ট ইন করবে, সেটি প্রথমে ডিলিট হবে।
স্ট্যাক অপারেশনগুলো -
- push(int data) - টপে ইনসার্শন
- int pop() - টপ থেকে ডিলিশন
কিউ (Queue)
কিউ FIFO হিসেবে ইমপ্লিমেন্ট হয় যেখানে ইনসার্শন একটি кінারে (রিয়ার) এবং ডিলিশন অন্য кінার থেকে (ফ্রন্ট) হয়। প্রথমে যে এলিমেন্ট ইন করবে, সেটি প্রথমে ডিলিট হবে।
কিউ অপারেশনগুলো -
- EnQueue(int data) - রিয়ার এন্ডে ইনসার্শন
- int DeQueue() - ফ্রন্ট এন্ড থেকে ডিলিশন
এটি দুটি স্ট্যাক ব্যবহার করে কিউ ইমপ্লিমেন্ট করার C++ প্রোগ্রাম।
ফাংশন বিবরণ
- enQueue() ফাংশন - কিউতে আইটেম ইনকিউ করতে:
- m কে s1-এ পুশ করো।
- deQueue() ফাংশন - কিউ থেকে আইটেম ডিকিউ করতে।
- যদি দুটি স্ট্যাকই খালি থাকে তবে প্রিন্ট করো "queue is empty"।
- যদি s2 খালি থাকে তবে s1 থেকে s2-এ এলিমেন্ট মুভ করো।
- s2 থেকে এলিমেন্ট পপ করো এবং রিটার্ন করো।
- push() ফাংশন - স্ট্যাকে আইটেম পুশ করতে।
- pop() ফাংশন - স্ট্যাক থেকে আইটেম পপ করতে।
উদাহরণ কোড
#include <stdlib.h>
#include <iostream>
using namespace std;
struct nod { // নোড ডিক্লেরেশন
int d;
struct nod *n;
};
void push(struct nod** top_ref, int n_d); // ফাংশন প্রোটোটাইপ
int pop(struct nod** top_ref);
struct queue {
struct nod *s1;
struct nod *s2;
};
void enQueue(struct queue *q, int m) {
push(&q->s1, m);
}
int deQueue(struct queue *q) {
int m;
if (q->s1 == NULL && q->s2 == NULL) {
cout << "Queue is empty";
exit(0);
}
if (q->s2 == NULL) {
while (q->s1 != NULL) {
m = pop(&q->s1);
push(&q->s2, m);
}
}
m = pop(&q->s2);
return m;
}
void push(struct nod** top_ref, int n_d) {
struct nod* new_node = (struct nod*) malloc(sizeof(struct nod));
if (new_node == NULL) {
cout << "Stack underflow \n";
exit(0);
}
// স্টাকে আইটেম রাখো
new_node->d = n_d;
new_node->n = (*top_ref);
(*top_ref) = new_node;
}
int pop(struct nod** top_ref) {
int res;
struct nod *top;
if (*top_ref == NULL) { // যদি স্ট্যাক নাল হয়
cout << "Stack overflow \n";
exit(0);
} else { // স্ট্যাক থেকে এলিমেন্ট পপ
top = *top_ref;
res = top->d;
*top_ref = top->n;
free(top);
return res;
}
}
int main() {
struct queue *q = (struct queue*) malloc(sizeof(struct queue));
q->s1 = NULL;
q->s2 = NULL;
cout << "Enqueuing..7";
cout << endl;
enQueue(q, 7);
cout << "Enqueuing..6";
cout << endl;
enQueue(q, 6);
cout << "Enqueuing..2";
cout << endl;
enQueue(q, 2);
cout << "Enqueuing..3";
cout << endl;
enQueue(q, 3);
cout << "Dequeuing...";
cout << deQueue(q) << " ";
cout << endl;
cout << "Dequeuing...";
cout << deQueue(q) << " ";
cout << endl;
cout << "Dequeuing...";
cout << deQueue(q) << " ";
cout << endl;
}আউটপুট
Enqueuing..7 Enqueuing..6 Enqueuing..2 Enqueuing..3 Dequeuing... 7 Dequeuing... 6 Dequeuing... 2
