হঠাৎ, আপনি পেছনের দিকে স্তূপ করা কিছু প্লাস্টিকের চেয়ার দেখতে পেলেন, যেগুলো একটির উপর আরেকটি সাজানো রয়েছে। এখন, আপনি কোন চেয়ারটি নিবেন? নিশ্চয়ই সবার উপরের চেয়ারটি। কারণ, স্তূপটি এমনভাবে সাজানো রয়েছে যে আপনি মাঝখান থেকে একটি চেয়ার সরাসরি নিতে পারবেন না। যদি মাঝের একটি চেয়ার নিতে চান, তাহলে আপনাকে উপরের চেয়ারগুলো একে একে সরিয়ে নিতে হবে, অথবা অপেক্ষা করতে হবে যতক্ষণ না অন্যরা উপরের চেয়ারগুলো নিয়ে যাবে। যদি আপনি সবার নিচের চেয়ারটি নিতে চান, যেটি প্রথমে রাখা হয়েছিল, তবে আপনাকে সবার শেষে সেটি নিতে হবে।
স্ট্যাককে আমরা এই চেয়ারের স্তূপের সাথে তুলনা করতে পারি। যখন চেয়ারগুলো নেয়া হয়, তখন সেগুলো উপরের দিক থেকে একে একে সরানো হয়। অর্থাৎ, সবচেয়ে পরে এবং উপরে রাখা চেয়ারটি প্রথমে নেওয়া হয়, এবং সবচেয়ে নিচের চেয়ারটি সবার শেষে নেওয়া হয়।
স্ট্যাক হলো এমন একটি লিনিয়ার ডেটা স্ট্রাকচার যেখানে সর্বশেষে যোগ করা উপাদানটিই প্রথমে সরানো হয়। এখানে 'লিনিয়ার' বলতে বোঝানো হয়েছে যে, আপনি ইচ্ছা করলেই মাঝখানের কোনো উপাদানে সরাসরি প্রবেশ করতে পারবেন না; বরং, একে একে উপাদানে প্রবেশ করতে হবে। আর 'ডেটা স্ট্রাকচার' বলতে বোঝানো হয়েছে ডেটাগুলো মেমোরিতে কীভাবে সাজানো আছে।
স্ট্যাকের প্রধান বৈশিষ্ট্য:
স্ট্যাক Last In First Out (LIFO) নিয়ম অনুসরণ করে। অর্থাৎ, যে উপাদানটি সর্বশেষে যোগ করা হয়েছে, সেটি প্রথমে সরানো হয় স্ট্যাক থেকে এবং যে উপাদানটি প্রথমে যোগ করা হয়েছে, সেটি সর্বশেষে সরানো হয় স্ট্যাক থেকে
স্ট্যাকের প্রধান অপারেশনগুলো:
পুশ (Push): নতুন উপাদান স্ট্যাকে যোগ করা।
পপ (Pop): সর্বশেষ যোগ করা উপাদানটি স্ট্যাক থেকে সরানো।
টপ (Top): স্ট্যাকের শীর্ষে থাকা উপাদানটি দেখা।
স্ট্যাক কে দুটি উপায়ে বাস্তবায়ন করা যেতে পারেঅ্যারের সাহায্যে: স্ট্যাককে একটি অ্যারের মাধ্যমে গঠন করা যায়।ডাবলি লিংকড লিস্টের মাধ্যমে: স্ট্যাককে একটি ডাবলি লিংকড লিস্ট ব্যবহার করে গঠন করা যায়।
অ্যারের সাহায্যে স্ট্যাক বাস্তবায়নঃ#include <bits/stdc++.h>
using namespace std;
class myStack
{
public:
vector<int> v;
void push(int val)
{
v.push_back(val);
}
void pop()
{
v.pop_back();
}
int top()
{
return v.back();
}
int size()
{
return v.size();
}
bool empty()
{
if (v.size() == 0)
return true;
else
return false;
}
};
ডাবলি লিংকড লিস্টের মাধ্যমে স্ট্যাক বাস্তবায়নঃ#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int val;
Node *next;
Node *prev;
Node(int val)
{
this->val = val;
this->next = NULL;
this->prev = NULL;
}
};
class myStack
{
public:
Node *head = NULL;
Node *tail = NULL;
int sz = 0;
void push(int val)
{
sz++;
Node *newNode = new Node(val);
if (head == NULL)
{
head = newNode;
tail = newNode;
return;
}
newNode->prev = tail;
tail->next = newNode;
tail = tail->next;
}
void pop()
{
sz--;
Node *deleteNode = tail;
tail = tail->prev;
if (tail == NULL)
{
head = NULL;
}
else
{
tail->next = NULL;
}
delete deleteNode;
}
int top()
{
return tail->val;
}
int size()
{
return sz;
}
bool empty()
{
if (sz == 0)
return true;
else
return false;
}
};
//main Function
int main()
{
myStack st;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
st.push(x);
}
while (st.empty() == false)
{
cout << st.top() << endl;
st.pop();
}
return 0;
}
- ব্রাউজারের ব্যাকওয়ার্ড ও ফরওয়ার্ড ফাংশব্রাউজারের ব্যাকওয়ার্ড এবং ফরওয়ার্ড বাটনগুলি আসলে দুটি স্ট্যাকের উপর কাজ করেব্যাকওয়ার্ড স্ট্যাক (Backward Stack):যখন আপনি কোনো নতুন পেজ ভিজিট করেন, সেই পেজটি স্ট্যাকের টপে সংরক্ষিত হয়।
- এরপর যখন আপনি একটি নতুন পেজ ভিজিট করেন, পুরোনো পেজটি ব্যাকওয়ার্ড স্ট্যাকে ঢুকে যায়যখন আপনি ব্যাক বাটন চাপেন, বর্তমান পেজটি ফরওয়ার্ড স্ট্যাকে চলে যায় এবং ব্যাকওয়ার্ড স্ট্যাক থেকে আগের পেজটি বের হয়ে সেটি প্রদর্শিত ফরওয়ার্ড স্ট্যাক (Forward Stack):যদি আপনি ব্যাক বাটন চেপে আগে একটি পেজে যান এবং তারপর ফরওয়ার্ড বাটন চাপেন, তাহলে সেই পেজটি ফরওয়ার্ড স্ট্যাক থেকে বের হয়ে সেটি আবার প্রদর্শিত হয়।
যদি আপনি নতুন কোনো পেজ ভিজিট করেন, তখন ফরওয়ার্ড স্ট্যাকটি ক্লিয়ার হয়ে যায়, অর্থাৎ সবগুলো এলিমেন্ট মুছে ফেলা হএকটি উদাহরণ:
আপনি যদি প্রথমে ফেসবুক, তারপর গিটহাবে এবং শেষে লিটকোড ভিজিট করেন, তাহলে ফেসবুক , এবং গিটহাবে ব্যাকওয়ার্ড স্ট্যাকে ঢুকে যায় এবং লিটকোড বর্তমান পেজ হিসেবে প্রদর্শিত হয়যদি আপনি ব্যাক বাটন চাপেন, তাহলে লিটকোড ফরওয়ার্ড স্ট্যাকে চলে যায় এবং গিটহাবে ব্যাকওয়ার্ড স্ট্যাক থেকে বের হয়ে সেটি প্রদর্শিত এরপর যদি আপনি ফরওয়ার্ড বাটন চাপেন, তাহলে আবার লিটকোড প্রদর্শিত হবে, এবং এটি ফরওয়ার্ড স্ট্যাক থেকে সরিয়ে বর্তমান পেজ হিসেবে প্রদর্শিত হবব্রাউজারে ইতিহাস ম্যানেজমেন্ট (History Management)
ব্রাউজার প্রতিটি পেজের URL কে স্ট্যাকের উপাদান হিসেবে সংরক্ষণ করে। যখনই ব্যবহারকারী কোনো পেজ থেকে অন্য পেজে যায়, সেটি স্বয়ংক্রিয়ভাবে এই স্ট্যাকে ঢুকে যায়। ব্যাক বা ফরওয়ার্ড বাটনের মাধ্যমে ব্যবহারকারী বিভিন্ন পেজে সহজেই নেভিগেট করতে পারেন, এবং এই প্রক্রিয়াটি খুব দ্রুত ও কার্যকরী হয় স্ট্যাক ব্যবহারের কাএই স্ট্যাকের ধারণার জন্যই ব্যবহারকারী খুব সহজে বিভিন্ন পেজে ফরওয়ার্ড বা ব্যাকওয়ার্ড করতে পারে, এবং এটি ব্রাউজারের একটি অতি গুরুত্বপূর্ণ ফাংশনব্রাউজিং হিস্ট্রি এর জন্য কোড
#include<bits/stdc++.h>
using namespace std;
class BrowserHistory {
public:
stack<string> backStack, forwardStack;
string current;
public:
BrowserHistory(string homepage) {
current = homepage;
}
void visit(string url) {
backStack.push(current);
current = url;
while (!forwardStack.empty()) {
forwardStack.pop();
}
}
string back(int steps) {
while (steps > 0 && !backStack.empty()) {
forwardStack.push(current);
current = backStack.top();
backStack.pop();
steps--;
}
return current;
}
string forward(int steps) {
while (steps > 0 && !forwardStack.empty()) {
backStack.push(current);
current = forwardStack.top();
forwardStack.pop();
steps--;
}
return current;
}
};
int main() {
BrowserHistory* browserHistory = new BrowserHistory("google.com");
browserHistory->visit("facebook.com");
browserHistory->visit("github.com");
browserHistory->visit("leetcode.com");
cout << browserHistory->back(1) << endll; // github
cout << browserHistory->back(1) << endl; // facebook
cout << browserHistory->forward(1) << endl; //
browserHistory->visit("linkedin.com");
cout << browserHistory->forward(2) << nl; // linkedin.com (can't move forward)
cout << browserHistory->back(2) << nl; // youtube.com
cout << browserHistory->back(7) << nl; // google.com (only goes as far back as possible)
delete browserHistory;
return 0;
}
আপনি কখন স্ট্যাক ব্যবহার করতে পারবেন না:
১. স্ট্যাকের মূল সীমাবদ্ধতা হল, শুধুমাত্র স্ট্যাকের টপ আইটেমে অ্যাক্সেস করা যায়। অন্য কোন আইটেমে সরাসরি অ্যাক্সেস করা যায় না।
২. যদি স্ট্যাক একটি নির্দিষ্ট আকারের (যেমন, অ্যারে ভিত্তিক স্ট্যাক) হয়, তাহলে যদি স্ট্যাক পূর্ণ হয়, নতুন আইটেম যোগ করা সম্ভব নয় (Stack Overflow)।
৩. অনেক সমস্যায় যেখানে এলিমেন্ট গুলোর মধ্যে স্বতন্ত্রভাবে বা এলোমেলোভাবে অ্যাক্সেস করতে হয়, সেখানে স্ট্যাক কার্যকর নয়।
