پشته‌ها در C++ (Stacks in C++)
پشته‌ها در C++ (Stacks in C++)
پشته (Stack) یک ساختار داده‌ای است که از اصل LIFO (Last In, First Out) پیروی می‌کند، یعنی آخرین عنصری که اضافه شده است، اولین عنصری است که حذف می‌شود. پشته‌ها را می‌توان به روش‌های مختلفی پیاده‌سازی کرد، از جمله آرایه‌ها (Arrays)، لیست‌های پیوندی (Linked Lists) یا استفاده از کلاس stack در STL.
۱. پیاده‌سازی پشته با std::stack (کتابخانه استاندارد C++)
در C++، یک کلاس داخلی به نام stack در هدر <stack> وجود دارد که کار با پشته را ساده می‌کند.
مثال: استفاده از std::stack
#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
// افزودن عناصر به پشته
s.push(10);
s.push(20);
s.push(30);
// نمایش عنصر بالای پشته
std::cout << “عنصر بالای پشته: “ << s.top() << std::endl; // 30
// حذف عنصر بالا
s.pop();
std::cout << “عنصر بالای پشته بعد از حذف: “ << s.top() << std::endl; // 20
// اندازه پشته
std::cout << “اندازه پشته: “ << s.size() << std::endl; // 2
// بررسی خالی بودن پشته
if (s.empty())
std::cout << “پشته خالی است” << std::endl;
else
std::cout << “پشته خالی نیست” << std::endl;
return 0;
}
۲. پیاده‌سازی پشته با استفاده از آرایه
در این روش، از یک آرایه با اندازه ثابت و یک متغیر برای پیگیری عنصر بالای پشته استفاده می‌شود.
مثال: پیاده‌سازی پشته با آرایه
#include <iostream>
#define MAX 100
class Stack {
int top;
int arr[MAX];
public:
Stack() { top = -1; }
bool push(int x) {
if (top >= MAX – 1) {
std::cout << “سرریز پشته (Stack Overflow)\n”;
return false;
}
arr[++top] = x;
return true;
}
int pop() {
if (top < 0) {
std::cout << “پشته خالی است (Stack Underflow)\n”;
return -1;
}
return arr[top–];
}
int peek() {
if (top < 0) {
std::cout << “پشته خالی است\n”;
return -1;
}
return arr[top];
}
bool isEmpty() { return (top < 0); }
};
int main() {
Stack s;
s.push(10);
s.push(20);
s.push(30);
std::cout << “عنصر بالای پشته: “ << s.peek() << std::endl;
std::cout << “حذف عنصر: “ << s.pop() << std::endl;
std::cout << “عنصر بالای پشته پس از حذف: “ << s.peek() << std::endl;
return 0;
}
۳. پیاده‌سازی پشته با استفاده از لیست پیوندی (Linked List)
در این روش، هر عنصر پشته یک گره (Node) است که شامل مقدار داده و اشاره‌گری به گره بعدی است.
مثال: پیاده‌سازی پشته با لیست پیوندی
#include <iostream>
class Node {
public:
int data;
Node* next;
};
class Stack {
Node* top;
public:
Stack() { top = nullptr; }
void push(int x) {
Node* newNode = new Node();
newNode->data = x;
newNode->next = top;
top = newNode;
}
int pop() {
if (top == nullptr) {
std::cout << “پشته خالی است (Stack Underflow)\n”;
return -1;
}
int value = top->data;
Node* temp = top;
top = top->next;
delete temp;
return value;
}
int peek() {
if (top == nullptr) {
std::cout << “پشته خالی است\n”;
return -1;
}
return top->data;
}
bool isEmpty() { return top == nullptr; }
};
int main() {
Stack s;
s.push(10);
s.push(20);
s.push(30);
std::cout << “عنصر بالای پشته: “ << s.peek() << std::endl;
std::cout << “حذف عنصر: “ << s.pop() << std::endl;
std::cout << << s.peek() << std::endl;
return 0;
}
۴. کاربردهای پشته
پشته‌ها در بسیاری از مسائل و الگوریتم‌ها استفاده می‌شوند:
- مدیریت فراخوانی توابع (Function Call Stack) در بازگشتی (Recursion)
- ارزیابی و تبدیل عبارات ریاضی مانند پسوندی (Postfix)، پیشوندی (Prefix)، میانوندی (Infix)
- پیاده‌سازی عملیات “بازگشت به عقب” (Backtracking) مانند حل ماز یا جستجوی عمقی (DFS)
- بررسی پرانتزهای متوازن (Balanced Parentheses)
- ساختارهای Undo/Redo در ویرایشگرهای متن
نتیجه‌گیری
- اگر می‌خواهید سریع‌ترین و ساده‌ترین روش را استفاده کنید،
std::stackبهترین گزینه است. - اگر به حافظه محدود هستید و اندازه پشته ثابت است، آرایه (Array) مناسب‌تر است.
- اگر اندازه پشته متغیر است و نیاز به پشته پویا دارید، از لیست پیوندی (Linked List) استفاده کنید.
دیدگاهتان را بنویسید