صف و پشته

پشته (stack) یک داده‌ساختار خطی است که عملیات درج و حذف از یک سوی آن که بالای پشته (top) گفته می‌شود، انجام می‌گردد.

مثال: وسایلی که داخل یک کوله‌پشتی قرار می‌دهیم، یک پشته می‌سازند. اگر وسیله‌ای به کوله بیفزاییم، بالای تمام وسایل قرار می‌گیرد و اگر بخواهیم کوله را تخلیه کنیم، باید هر بار وسیله‌ی رویی را در بیاوریم.

صف داده‌ساختاری شبیه به پشته است؛ با این تفاوت که درج از انتها و حذف از ابتدای آن انجام می‌شود.

مثال: در طول روز، شاهد صف‌های متعددی هستیم. برای مثال صف صندوق فروشگاه را در نظر بگیرید. خریدارهای جدید به انتهای صف افزوده می‌شوند و خریداری که در ابتدای صف قرار دارد، بعد از انجام کارش از آن خارج می‌شود.

1. درج (push): افزودن یک عنصر به بالای پشته
2. حذف (pop): حذف بالاترین عنصر پشته و برگرداندن آن
3. عملیات های اختیاری مثل مشخص کردن اندازه‌ی پشته، $k$-امین عنصر و …

1. درج (push): افزودن یک عنصر جدید به انتهای صف
2. حذف (pop): حذف اولین عنصر صف و برگرداندن آن
3. عملیات‌های اختیاری مثل مشخص کردن اندازه صف، $k$-امین عنصر و …

پشته را می‌توان با یک آرایه یا با اشاره‌گرها پیاده‌سازی کرد.

کتاب‌خانه‌ی <stack> در ++C یک پیاده‌سازی استاندارد برای پشته است که می‌توان از آن هم بهره برد.

stack.cpp

#include <stack>
using namespace std;
int main()
{
    stack<int> st; //presentation of stack
    st.push(5); // push 5 into stack in O(1)
    st.pop(); // pop from stack in O(1)
    st.top(); // top of stack given in O(1)
    st.size(); // size of stack given in O(1)
    st.empty(); // if stack is empty, true otherwise, false given in O(1)
    // in c++11
    stack<int> ts;
    st.swap(ts); // swap two stacks in O(1)
    return 0;
}

مشابه پشته، صف را نیز می‌توان با آرایه یا اشاره‌گرها پیاده‌سازی کرد. اما یک پیاده‌سازی استاندارد در کتابخانه‌ی <queue> برای آن وجود دارد.

queue.cpp

#include <queue>
using namespace std;
int main()
{
    queue<int> q; // presentation of queue
    q.push(5); // add 5 at the end of queue in O(1)
    q.pop(); // pop from front of queue in O(1)
    q.front(); // front of queue given in O(1)
    q.back(); // back of queue given in O(1)
    q.size(); // size of queue given in O(1)
    q.empty(); // if queue is empty, true otherwise false given in O(1)
    // in c++11
    queue<int> p;
    q.swap(p); //swap two queues in O(1)    
    return 0;
}

• در طراحی بیش‌تر کامپیوترها، پشته یک جزء اساسی است.
• برای تبدیل توابع بازگشتی به غیر بازگشتی کاربرد دارد.
• در طراحی بعضی ساختمان داده‌های پیچیده‌تر استفاده می‌شود.
• برای تجزیه‌ی عبارت‌ها کارایی دارد.
• در الگوریتم‌های هندسه محاسباتی نظیر یافتن پوش کوژ یا اشتراک نیم‌صفحه‌ها استفاده دارد.
• برای تبدیل مبنای اعداد می‌توان از پشته بهره جست.
• و کاربردهای بسیار دیگر

• در الگوریتم‌های گراف از جمله جستجوی سطح اول، شار بیشینه و … استفاده می‌شود.
• در روش‌های حریصانه، استفاده از صف بسیار متداول است.
• و کاربردهای بسیار دیگر