====== صف و پشته ======


===== تعریف =====

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

{{ :آموزش:الگوریتم:selection_047.png |}}

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

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

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

===== عملیات‌ها =====

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

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

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

 کتاب‌خانه‌ی <stack> در ++C یک پیاده‌سازی استاندارد برای پشته است که می‌توان از آن هم بهره برد.
<code cpp 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;
}
</code>

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

<code cpp 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;
}
</code>

===== کاربردها =====


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

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