پشته، نوعی از ساختمان داده‌ است که از اصل LIFO پشتیبانی می‌کند. این عبارت به معنی این است که آخرین داده‌ای که وارد پشته می‌شود اولین داده‌ای خواهد بود که از پشته خارج می‌شود. پشته از ساختار ذخیره داده خطی استفاده می‌کند. می‌کند. با توجه به نمایش انطباق‌پذیری و کاربردهای گوناگون پشته به تاثیر مثبت این نوع از ساختمان داده در حل مسائل پی می‌بریم. بررسی اهمیت پشته‌ در ساختمان داده، راز حیاتی بودن این رشته تخصصی را در علوم کامپیوتر فاش می‌کند. در این مطلب جامع از مجله فرادرس به مبحث پشته در ساختمان داده پرداخته‌ایم. نه تنها به صورت عمیقی به بررسی چیستی پشته‌ها پرداختیم بلکه حتی درباره انواع ویژگی‌های کلیدی پشته‌ها و کاربرد‌ها و مزایا و معایبشان نیز کندوکاو کرده‌ایم.

در ادامه مطلب، مثال‌های عملی و کدنویسی‌هایی که در این مطلب نمایش داده‌ شده‌اند پیاده‌سازی پشته‌ها را همراه با چند عملیات رایج بر روی تعدادی از معروف‌ترین زبان‌های برنامه‌نویسی نمایش می‌دهند. سپس انواع کاربردهای پایه و پیشرفته پشته‌ها را با استفاده از عملیات push و pop بر روی داده ها را بررسی کرده‌ایم. در نهایت هم با موارد کاربرد عملی پشته در ساختمان داده آشنا می‌شویم و می‌بینیم که با کمک پشته‌ها روش مدیریت و کار با داده‌ها چگونه به طرز موثری ارتقا می‌یابد. این تاثیر مثبت در کار با داده‌ها باعث کاربرد چشم‌گیر پشته در سراسر بخش‌های علوم کامپیوتری شده است.

پشته در ساختمان داده چیست؟

پشته، ساختمان داده‌ای خطی است که از اصل LIFO پشتیبانی می‌کند. اصل LIFO سرنامی از عبارت Last-In-First-Out -آخرین ورودی اولین خروجی- است. این عبارت به معنی این است که آخرین داده‌ای که وارد پشته می‌شود اولین داده‌ای خواهد بود که از پشته خارج می‌شود. زیرا پشته‌ها یک سر باز برای ورود و خروج داده‌ها بیشتر ندارند. در حالی که صف‌ها در ساختمان داده دارای دو سر جلو و عقب هستند. پشته فقط یک نشانگر دارد به نام «Top Pointer»، این نشانگر همیشه به بالاترین عنصر درون پشته اشاره می‌کند. هر وقت که عنصری به پشته اضافه شود در بالاترین خانه پشته قرار می‌گیرد و تنها عنصری که می‌تواند از پشته حذف شود همین بالاترین عنصر است. به عبارت دیگر، پشته را می‌توان به عنوان ظرفی از داده‌ها در نظر گرفت که ورود و خروج فقط از یک سمت آن اتفاق می‌افتد. تنها سر پشته به عنوان بالاترین خانه پشته در نظر گرفته می‌شود.

چند نکته کلیدی مربوط به پشته ها

پشته دارای ویژگی‌های خاصی است که باعث شده به یکی از ساختمان‌داده‌های کاربردی برای موارد خاص تبدیل شود. در ادامه ویژگی‌های پشته را فهرست کرده‌ایم.

• از آن جهت به این ساختمان داده پشته گفته می‌شود که واقعا همانند پشته عمل می‌کند. چیزی مانند کتاب‌هایی که به روی یکدیگر گذاشته شده‌اند.
• پشته شکل انتزاعی از نوع داده با ظرفیتی از پیش تعیین شده است. به این معنا که پشته‌ها برای ذخیره‌سازی عنصر‌ها دارای محدودیت هستند.
• پشته‌ها نوعی از ساختمان داده هستند که از نظم خاصی برای ورود و خروج داده‌ها پشتیبانی می‌کنند. به این نظم خاص LIFO یا FILO می‌گویند.

کار کردن با پشته در ساختمان داده

پشته‌ها با الگوی LIFO کار می‌کنند. همین‌طور که در شکل زیر می‌بینیم، ۵ بلاک حافظه‌ای در پشته فرضی وجود دارند. بنابراین اندازه این پشته ۵ است.

قرار است که عناصر را درون پشته‌ای ذخیره کنیم و فرض می‌کنیم که پشته خالی است. برای این مثال پشته‌ای با اندازه ۵ را در نظر گرفته‌ایم. همین‌طور که در زیر نمایش داده شده عناصر را یک به یک درون پشته وارد می‌کنیم تا وقتی که پشته مورد نظر پر شود.

بنابراین چونکه اندازه پشته مورد استفاده در این مثال برابر ۵ تعیین شده است، بعد از وارد کردن این تعداد عنصر، پشته فرضی پر می‌شود. در موارد بالایی می‌توانیم مشاهده کنیم که هر وقت عنصری را به پشته وارد می‌کنیم، عناصر از بالا وارد می‌شوند و تا پایین ترین فضای خالی درون پشته می‌روند.

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

الگوی LIFO به معنی این است که آیتمی که اول از همه به پشته وارد شود آخر از همه نیز از پشته خارج می‌شود. در مورد مشاهده شده بالا، مقدار ۵ اولین عنصری بود که به پشته وارد شد. پس فقط وقتی می‌توان این عنصر را از پشته حذف کرد که بقیه عناصر وارد  شده بعد از عدد ۵ از قبل از پشته خارج شده باشند.

چگونه بر روی مبحث ساختمان داده و الگوریتم ها تسلط پیدا کنیم؟

ساختمان داده و الگوریتم‌ها، بخش بسیار مهم و تخصصی از علوم کامپیوتر را تشکیل می‌دهند. هر برنامه‌نویسی برای اینکه در نهایت بتواند خود را به عنوان برنامه‌نویس حرفه‌ای بشناسد باید توانایی طراحی الگوریتم و مدیریت ساختمان‌های داده را داشته باشد. در فرادرس برای درک، آشنایی و حرفه‌ای شدن در این زمینه فیلم‌های آموزشی بسیار خوبی طراحی شده است. فرادرس حساسیت بالایی بر روی کیفیت مباحث آموزشی و خود فیلم‌های تولید شده بر روی یادگیری و رضایت مخاطبان دارد. به این دلیل، توانسته به عنوان بزرگترین تولید کننده محتوای آموزشی فارسی شناخته شود.

در این بخش چند مورد از فیلم‌هی آموزشی مربوط به ساختمان داده و طراحی الگوریتم را معرفی کرده‌ایم. در صورت تمایل با کلیک بر روی تصویر بالا می‌توانید به صفحه اصلی این مجموعه آموزشی رفته و سایر فیلم‌ها را نیز مرور و بررسی کنید.

عملیات استاندارد پشته

در ادامه چند مورد از رایج‌ترین عملیاتی را معرفی کرده‌ایم که بر روی پشته‌ها پیاده‌سازی می‌شوند.

• push()

   : عملیات مربوط به وارد کردن عنصرها به پشته به نام push()

  شناخته می‌شوند. اگر پشته پر شده باشد، شرایط لازم برای احتمال وقوع «سرریز» (Overflow) فراهم شده‌ است.

• pop()

   : وقتی که عنصری را از پشته حذف می‌کنیم در واقع از حال اجرای عملیات pop()

  هستیم. اگر قبل از اجرای این عملیات پشته خالی شده بود، به معنی این است که دیگر عنصری درون پشته وجود ندارد. به این حالت «زیرریز» (Underflow) پشته گفته می‌شود.

• isEmpty()

   : این عملیات وضعیت خالی بودن یا نبودن پشته را مشخص می‌کند.

• isFull()

   :این عملیات وضعیت پر بودن یا نبودن پشته را مشخص می‌کند.

• peek()

   : عملیات peek()

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

• count()

   : عملیات count()

  مجموع کل تعداد عناصر قابل دسترسی در پشته را محاسبه و اعلام می‌کند.

• change()

   : عملیات change()

  عنصر موجود در محل مشخص شده در پشته را تغییر می‌دهد.

• display()

   : عملیات display()

  همه عناصر قابل دسترس درون پشته را در خروجی نمایش می‌دهد.

در ادامه چند مورد -PUSH و POP و isEmpty و Peek- را که به عنوان پرکاربردترین عملیات پشته‌ها شناخته می‌شوند، به صورت مفصل‌تری توضیح داده‌ایم.

عملیات PUSH

عملیات PUSH برای وارد کردن عنصرها به پشته استفاده می‌شود. این یکی از اولین توابعی است که می‌توان در هر پشته‌ای بکاربرد. هر بار اجرای عملیات PUSH شامل مراحل خاصی است که در پایین فهرست کرده‌ایم.

1. قبل از وارد کردن هر عنصر به پشته باید بررسی کنیم که آیا پشته پُر شده یا نه.
2. در حالی که پشته از قبل پُر شده است، اگر سعی کنیم عنصری را به آن وارد کنیم، حالت Overflow رخ خواهد داد.
3. وقتی که پشته‌ای را مقداردهی اولیه می‌کنیم‌، باید مقدار بالاترین خانه پشته را برابر با -1

     قرار دهیم. این کار باعث می‌شود که به سادگی با مقایسه بالاترین خانه پشته با عدد -1

   به خالی بودن یا نبودن پشته پی ببریم.

4. زمانی که عنصر جدیدی به پشته PUSH یا به آن وارد شد، در ابتدا مقدار top به صورت top=top+1 افزایش پیدا می‌کند و سپس عنصر در جایگاه جدید مقدار top قرار می‌گیرد.
5. تا وقتی که به «بیشترین اندازه» (Max Size) پشته برسیم، می‌توان عناصر را در پشته وارد کرد.

در تصویر زیر نمایشی از مراحل بالا برای پرشدن پشته را می‌توان مشاهده کرد.

عملیات POP

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

1. قبل از حذف کردن هر عنصر از پشته باید خالی بودن یا نبودن پشته را بررسی کنیم.
2. اگر برای حذف کردن عنصری از پشته خالی تلاش کنیم حالت Underflow رخ می‌دهد.
3. اگر پشته خالی نباشد، در ابتدا به عنصری که در خانه top پشته قرار گرفته دسترسی پیدا می‌کنیم و
4. سپس بلافاصله بعد از انجام عملیات POP، از مقدار top یک واحد کم می‌شود top=top-1.

در تصویر نمایش داده شده پایین، می‌توان مراحل توصیف شده بالا را مشاهده کرد.

عملیات Top یا Peek

این دو عبارت به یک معنا هستند. تابع peek()

 برای برگرداندن مقدار درون خانه Top بدون حذف این مقدار از پشته استفاده می‌شود.

الگوریتم این عملیات به این صورت است که:

1. قبل از برگرداندن بالاترین عنصر درون پشته، خالی بودن پشته را بررسی می‌کنیم.
2. اگر پشته خالی باشد و عبارت top == -1

    مقدار True

   را برگرداند، فقط کافی است که به سادگی عبارت Stack is empty

    را در خروجی نمایش دهیم.

3. در غیر این صورت، عنصری را که در index = top

    ذخیره شده به کاربر برمی‌گردانیم.

عملیات isEmpty

عملیات isEmpty برای بررسی خالی بودن یا نبودن پشته در ساختمان داده استفاده می‌شود. در صورت خالی بودن مقدار True

 و در غیر این صورت مقدار False

 را برمی‌گرداند.

الگوریتم این عملیات به این صورت است که:

1. در ابتدا مقدار خانه top را پشته بررسی می‌کنیم.
2. اگر عبارت مقایسه‌ای top == -1

    بر قرار بود، بنابراین پشته خالی است و مقدار True

   را به خروجی برمی‌گردانیم.

3. در غیر این صورت، پشته خالی نیست و مقدار False

   را باید به خروجی برگردانیم.

در بخش بعدی پشته را همراه با عملیات تعریف شده در این بخش پیاده‌سازی کرده‌ایم.

مثال های پیاده سازی پشته در ساختمان داده

در این بخش شکل ساده پیاده‌سازی پشته همراه با عملیات تعریف شده در بخش قبل را در ۶ زبان متفاوت نمایش داده‌ایم.

در کد زیر پیاده‌سازی پشته را همراه با چهار عملیات توصیف شده در بخش قبل با زبان برنامه‌نویسی ++C می‌بینید.

1/* C++ program to implement basic stack
2   operations */
3#include <bits/stdc++.h>
4
5using namespace std;
6
7#define MAX 1000
8
9class Stack {
10    int top;
11
12public:
13    int a[MAX]; // Maximum size of Stack
14
15    Stack() { top = -1; }
16    bool push(int x);
17    int pop();
18    int peek();
19    bool isEmpty();
20};
21
22bool Stack::push(int x)
23{
24    if (top >= (MAX - 1)) {
25        cout << "Stack Overflow";
26        return false;
27    }
28    else {
29        a[++top] = x;
30        cout << x << " pushed into stackn";
31        return true;
32    }
33}
34
35int Stack::pop()
36{
37    if (top < 0) {
38        cout << "Stack Underflow";
39        return 0;
40    }
41    else {
42        int x = a[top--];
43        return x;
44    }
45}
46int Stack::peek()
47{
48    if (top < 0) {
49        cout << "Stack is Empty";
50        return 0;
51    }
52    else {
53        int x = a[top];
54        return x;
55    }
56}
57
58bool Stack::isEmpty()
59{
60    return (top < 0);
61}
62
63// Driver program to test above functions
64int main()
65{
66    class Stack s;
67    s.push(10);
68    s.push(20);
69    s.push(30);
70    cout << s.pop() << " Popped from stackn";
71  
72    //print top element of stack after popping
73    cout << "Top element is : " << s.peek() << endl;
74  
75    //print all elements in stack :
76    cout <<"Elements present in stack : ";
77    while(!s.isEmpty())
78    {
79        // print top element in stack
80        cout << s.peek() <<" ";
81        // remove top element in stack
82        s.pop();
83    }
84
85    return 0;
86}

در کد زیر پیاده‌سازی پشته را همراه با چهار عملیات توصیف شده در بخش قبل با زبان برنامه نویسی C می‌بینید.

1// C program for array implementation of stack
2#include <limits.h>
3#include <stdio.h>
4#include <stdlib.h>
5
6// A structure to represent a stack
7struct Stack {
8    int top;
9    unsigned capacity;
10    int* array;
11};
12
13// function to create a stack of given capacity. It initializes size of
14// stack as 0
15struct Stack* createStack(unsigned capacity)
16{
17    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
18    stack->capacity = capacity;
19    stack->top = -1;
20    stack->array = (int*)malloc(stack->capacity * sizeof(int));
21    return stack;
22}
23
24// Stack is full when top is equal to the last index
25int isFull(struct Stack* stack)
26{
27    return stack->top == stack->capacity - 1;
28}
29
30// Stack is empty when top is equal to -1
31int isEmpty(struct Stack* stack)
32{
33    return stack->top == -1;
34}
35
36// Function to add an item to stack.  It increases top by 1
37void push(struct Stack* stack, int item)
38{
39    if (isFull(stack))
40        return;
41    stack->array[++stack->top] = item;
42    printf("%d pushed to stackn", item);
43}
44
45// Function to remove an item from stack.  It decreases top by 1
46int pop(struct Stack* stack)
47{
48    if (isEmpty(stack))
49        return INT_MIN;
50    return stack->array[stack->top--];
51}
52
53// Function to return the top from stack without removing it
54int peek(struct Stack* stack)
55{
56    if (isEmpty(stack))
57        return INT_MIN;
58    return stack->array[stack->top];
59}
60
61// Driver program to test above functions
62int main()
63{
64    struct Stack* stack = createStack(100);
65
66    push(stack, 10);
67    push(stack, 20);
68    push(stack, 30);
69
70    printf("%d popped from stackn", pop(stack));
71
72    return 0;
73}

زبان برنامه‌نویسی «جاوا» (Java) یکی از زبان‌های پرطرفدار در بین برنامه‌نویسان جهان است. این زبان به دلیل سادگی معمولا در دانشگاه‌ها و موسسات آموزشی به عنوان اولین زبان به دانشجویان آموزش داده می‌شود. در صورتی که نسبت به این زبان برنامه‌نویسی کم اطلاع و کنجکاو هستید، برای بدست آوردن اطلاعات بیشتر می‌توانید مطلب «آینده زبان برنامه نویسی جاوا چیست و آیا ارزش یادگیری دارد؟» را در مجله فرادرس را مطالعه کنید.

در کد زیر پیاده‌سازی پشته را همراه با چهار عملیات توصیف شده در بخش قبل با زبان برنامه‌ نویسی Java می‌بینید.

1/* Java program to implement basic stack
2operations */
3class Stack {
4    static final int MAX = 1000;
5    int top;
6    int a[] = new int[MAX]; // Maximum size of Stack
7
8    boolean isEmpty()
9    {
10        return (top < 0);
11    }
12    Stack()
13    {
14        top = -1;
15    }
16
17    boolean push(int x)
18    {
19        if (top >= (MAX - 1)) {
20            System.out.println("Stack Overflow");
21            return false;
22        }
23        else {
24            a[++top] = x;
25            System.out.println(x + " pushed into stack");
26            return true;
27        }
28    }
29
30    int pop()
31    {
32        if (top < 0) {
33            System.out.println("Stack Underflow");
34            return 0;
35        }
36        else {
37            int x = a[top--];
38            return x;
39        }
40    }
41
42    int peek()
43    {
44        if (top < 0) {
45            System.out.println("Stack Underflow");
46            return 0;
47        }
48        else {
49            int x = a[top];
50            return x;
51        }
52    }
53   
54    void print(){
55    for(int i = top;i>-1;i--){
56      System.out.print(" "+ a[i]);
57    }
58  }
59}
60
61// Driver code
62class Main {
63    public static void main(String args[])
64    {
65        Stack s = new Stack();
66        s.push(10);
67        s.push(20);
68        s.push(30);
69        System.out.println(s.pop() + " Popped from stack");
70        System.out.println("Top element is :" + s.peek());
71        System.out.print("Elements present in stack :");
72        s.print();
73    }
74}

در کد زیر پیاده‌سازی پشته را همراه با چهار عملیات توصیف شده در بخش قبل با زبان برنامه نویسی Python می‌بینید.

1# Python program for implementation of stack
2
3# import maxsize from sys module 
4# Used to return -infinite when stack is empty
5from sys import maxsize
6
7# Function to create a stack. It initializes size of stack as 0
8def createStack():
9    stack = []
10    return stack
11
12# Stack is empty when stack size is 0
13def isEmpty(stack):
14    return len(stack) == 0
15
16# Function to add an item to stack. It increases size by 1
17def push(stack, item):
18    stack.append(item)
19    print(item + " pushed to stack ")
20    
21# Function to remove an item from stack. It decreases size by 1
22def pop(stack):
23    if (isEmpty(stack)):
24        return str(-maxsize -1) # return minus infinite
25    
26    return stack.pop()
27
28# Function to return the top from stack without removing it
29def peek(stack):
30    if (isEmpty(stack)):
31        return str(-maxsize -1) # return minus infinite
32    return stack[len(stack) - 1]
33
34# Driver program to test above functions    
35stack = createStack()
36push(stack, str(10))
37push(stack, str(20))
38push(stack, str(30))
39print(pop(stack) + " popped from stack")

در کد زیر پیاده‌سازی پشته را همراه با چهار عملیات توصیف شده در بخش قبل با زبان برنامه نویسی #C می‌بینید.

1// C# program to implement basic stack
2// operations
3using System;
4
5namespace ImplementStack {
6class Stack {
7    private int[] ele;
8    private int top;
9    private int max;
10    public Stack(int size)
11    {
12        ele = new int[size]; // Maximum size of Stack
13        top = -1;
14        max = size;
15    }
16
17    public void push(int item)
18    {
19        if (top == max - 1) {
20            Console.WriteLine("Stack Overflow");
21            return;
22        }
23        else {
24            ele[++top] = item;
25        }
26    }
27
28    public int pop()
29    {
30        if (top == -1) {
31            Console.WriteLine("Stack is Empty");
32            return -1;
33        }
34        else {
35            Console.WriteLine("{0} popped from stack ", ele[top]);
36            return ele[top--];
37        }
38    }
39
40    public int peek()
41    {
42        if (top == -1) {
43            Console.WriteLine("Stack is Empty");
44            return -1;
45        }
46        else {
47            Console.WriteLine("{0} popped from stack ", ele[top]);
48            return ele[top];
49        }
50    }
51
52    public void printStack()
53    {
54        if (top == -1) {
55            Console.WriteLine("Stack is Empty");
56            return;
57        }
58        else {
59            for (int i = 0; i <= top; i++) {
60                Console.WriteLine("{0} pushed into stack", ele[i]);
61            }
62        }
63    }
64}
65
66// Driver program to test above functions
67class Program {
68    static void Main()
69    {
70        Stack p = new Stack(5);
71
72        p.push(10);
73        p.push(20);
74        p.push(30);
75        p.printStack();
76        p.pop();
77    }
78}
79}

در کد زیر پیاده‌سازی پشته را همراه با چهار عملیات توصیف شده در بخش قبل با زبان برنامه‌نویسی Javascript می‌بینید.

1<script>
2/* javascript program to implement basic stack
3operations 
4*/
5 var t = -1;
6      var MAX = 1000;
7    var a = Array(MAX).fill(0); // Maximum size of Stack
8
9    function isEmpty() {
10        return (t < 0);
11    }
12
13    function push(x) {
14        if (t >= (MAX - 1)) {
15            document.write("Stack Overflow");
16            return false;
17        } else {
18        t+=1;
19            a[t] = x;
20            
21            document.write(x + " pushed into stack<br/>");
22            return true;
23        }
24    }
25
26    function pop() {
27        if (t < 0) {
28            document.write("Stack Underflow");
29            return 0;
30        } else {
31            var x = a[t];
32            t-=1;
33            return x;
34        }
35    }
36
37    function peek() {
38        if (t < 0) {
39            document.write("Stack Underflow");
40            return 0;
41        } else {
42            var x = a[t];
43            return x;
44        }
45    }
46
47    function print() {
48        for (i = t; i > -1; i--) {
49            document.write(" " + a[i]);
50        }
51    }
52
53        push(10);
54        push(20);
55        push(30);
56        document.write(pop() + " Popped from stack");
57        document.write("<br/>Top element is :" + peek());
58        document.write("<br/>Elements present in stack : ");
59        print();
60
61</script>

خروجی حاصل از اجرای همه کدهای بالا به صورت زیر است.

10 pushed into stack
20 pushed into stack
30 pushed into stack
30 Popped from stack
Top element is : 20
Elements present in stack : 20 10 

چطور با فرادرس برنامه نویس شویم؟

برنامه‌نویسی یکی از جذاب‌ترین رشته‌های علمی و کاری حداقل در دو دهه اخیر بوده است. بسیار از افراد هم به‌خاطر علاقه و سرگرمی و هم به‌خاطر مسائل شغلی به یادگیری برنامه‌نویسی مشغول شده‌اند. خود رشته برنامه‌نویسی شامل زبان‌های بسیار متنوعی است که هر کدام مزیت‌ها و توانایی‌های خود را دارند. وب‌سایت آموزشی فرادرس برای یادگیری برنامه‌نویسی متناسب با همه سنین و همه سطوح علمی مخاطبان، فیلم‌های متنوعی تولید کرده است. هر زبان برنامه‌نویسی نیز برای خود گرایش‌ها و تکنولوژی‌های خاصی دارد. در فراردس تلاش کردیم تقریبا همه این گرایش‌ها و تکنولوژی‌های متنوع را با بهترین کیفیت ممکن پوشش دهیم.

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

کاربردهای پشته در ساختمان داده

پشته‌ها دارای کاربردهای متنوعی در تمام بخش‌های مربوط به علوم کامپیوتری می‌شوند. در این بخش چند مورد از این کاربردها را به همراه مزایا و معایب استفاده از پشته‌ها فهرست کرده‌ایم.

• «برقراری تعادل در نمادها» (Balancing Of Symbols): پشته‌ها برای ایجاد تعادل در نماد‌ها نیز به‌کار برده می‌شوند. برای مثال فرض کنید که برنامه زیر را نوشته‌ایم.

1int main()  
2{  
3   cout<<"Hello";  
4   cout<<"javaTpoint";  
5}  

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

• «معکوس کردن رشته‌ها» (String Reversal): پشته‌ها برای معکوس کردن رشته‌ها نیز به‌کار برده می‌شوند. برای مثال می‌خواهیم که رشته «Faradars» را معکوس کنیم. با استفاده از پشته به سادگی می‌توانیم به هدف خود برسیم.
  • در ابتدا همه کاراکترهای رشته را تا زمان رسیدن به کاراکتر NULL درون پشته‌ای وارد می‌کنیم.
  • بعد از Push کردن همه کاراکترها شروع به خارج کردن کاراکترها به صورت یک به یک تا زمان رسیدن به کف پشته می‌کنیم.
  • نتیجه برابر با «sradaraF» می‌شود.
• UNDO/REDO: از پشته‌ها برای اجرای عملیات UNDO/REDO نیز می‌توان استفاده کرد.
  • برای مثال فرض کنیم که ادیتوری داریم. در این ادیتور در ابتدا حرف «a» سپس حرف «b» و در نهایت حرف «c» را وارد می‌کنیم.
  • بنابراین متن نوشته شده در ادیتور باید «abc» باشد.
  • الان ۳ حالت مختلف «abc» و «ab» و «a» وجود دارند که هر سه در پشته‌ای ذخیره شده‌اند. برای چنین شرایطی باید دو پشته مختلف وجود داشته باشد. یکی برای نمایش حالت‌های UNDO و پشته بعدی برای نمایش حالت‌های REDO به‌کار می‌رود.
  • اگر بخواهیم که عملیات UNDO را برای رسیدن به حالت «ab» انجام دهیم باید یک بار عملیات pop را بر روی پشته اجرا کنیم.

• «اجرای بازگشتی توابع» (Recursion): اجرای بازگشتی توابع به حالتی گفته می‌شود که تابعی خودش را فراخوانی کند. برای نگهداری حالت قبلی متغیرهای درون تابع، کامپایلر زبان برنامه‌نویسی& پشته سیستمی را برای نگهداری مقادیر قبلی رکوردهای تابع ایجاد می‌کند.
• DFS | Depth First Search: الگوریتم «جست‌وجوی عمق اول» (Depth First Search) برای جست‌وجو در گراف ها پیاده‌سازی شده است. این الگوریتم با استفاده از پشته در گراف‌ها به جست‌وجوی شاخه به شاخه می‌پردازد.
• «پیمایش معکوس» (Backtracking): فرض کنیم که باید مسیری را برای حل کردن مسئله‌ای مربوط به هزارتو ایجاد کنیم. شاید بعد از قدم گذاشتن در مسیر خاصی، متوجه شویم که مسیر مورد نظر تکراری یا اشتباه است. برای آمدن به محل شروع پیمایش مسیر و ساخت مسیر جدید باید از ساختار داده پشته‌ استفاده کنیم.
• «تبدیل عبارات» (Expression Conversion): پشته‌ها برای تبدیل عبارات نیز می‌توانند استفاده شوند. این مورد یکی از مهمترین کاربردهای پشته‌ها محسوب می‌شود. فهرستی برای مثال از تبدیل عبارات در ادامه نمایش داده شده است.

Infix to prefix
Infix to postfix
Prefix to infix
Prefix to postfix
Postfix to infix

• «مدیریت حافظه» (Memory Management): پشته‌ها حافظه سیستم را از طریق تخصیص حافظه به بلاک‌های حافظه‌ای مجاور هم مدیریت می‌کنند. به همین دلیل است که اغلب به پشته‌ها، پشته حافظه‌ای نیز می‌گویند. وقتی برنامه‌ای اجرا می‌شود، کامپایلر اندازه حافظه‌ مورد نیاز را می‌داند. همین‌طور که توابع فراخوانی می‌شوند، متغیرهای آن‌ها نیز به حافظه پشته تخصیص داده می‌شوند. وقتی تابعی کار خود را به پایان می‌رساند، متغیرهای اختصاص داده شده به پشته آزاد می‌شوند. این فرایند تخصیص و آزاد کردن حافظه باعث می‌شود که پشته‌ برای مدیریت فراخوانی‌های توابع و متغیرهای محلی گزینه بسیار کارآمدی باشد.

مزایای پشته در ساختمان داده

مزایای استفاده از پشته‌ در ساختمان داده شامل چند بخش کلی می‌شود که البته در این قسمت به صورت مختصر و مفید این مزیت‌ها را فهرست کرده‌ایم.

• سادگی: پشته‌ها ساختمان داده ساده و قابل درکی هستند. این خاصیت، استفاده از پشته‌ها را در طیف وسیعی از برنامه‌ها به گزینه مناسبی تبدیل کرده است.
• کارآیی: عملیات مربوط به ورود و خروج داده‌ها در پشته را می‌توان در زمان ثابت O(1) انجام داد. که این بازدهی زمانی دسترسی مناسبی را به داده‌ها فراهم می‌کند.
• آخرین ورودی، اولین خروجی یا LIFO: پشته‌ها از اصل LIFO پشتی‌بانی می‌کنند. این کار باعث می‌شود که همیشه آخرین عنصر وارد شده به پشته اولین عنصر قابل خارج شدن از پشته نیز باشد. این رفتار در سناریو‌های زیادی مانند فراخوانی توابع و ارزش‌یابی عبارت‌ها مفید واقع می‌شود.
• استفاده از حافظه محدود شده: تنها کار پشته‌ها این است که عناصر ارسال شده به خود را ذخیره‌سازی کنند. این کار پشته‌ها را در مقایسه با سایر ساختارهای ذخیره داده از لحاظ مصرف حافظه بسیار کارآمدتر می‌کند.

معایب پشته در ساختمان داده

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

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

جمع بندی

پشته نوعی ساختار ذخیره داده است که از اصل LIFO پشتیبانی می‌کند. از آنجا که پشته‌ها فقط دارای یک سر هستند، ورود و خروج داده‌ها نیز فقط از همان جهت انجام می‌گیرد. بنابراین اولین داده‌ ورودی فقط زمانی قادر به خروج است که داده‌های وارد شده بعد از آن قبلا از پشته خارج شده باشند. در این مطلب از مجله فرادرس درباره پشته و اینکه پشته چیست صحبت کردیم. انواع عملیات رایج بر روی پشته‌ها را نام بردیم و ۴ مورد از رایج‌ترین‌ها را با ذکر مثال‌های کدنویسی شده توضیح دادیم. در نهایت هم کاربردهای مختلف پشته را همراه با مزایا و معایت این ساختار ذخیره داده بیان کردیم.

از آنجا که پشته در ساختمان داده، یکی از مهم‌ترین ساختارهای ذخیره داده است و تقریبا در تمام برنامه‌های موجود کاربرد دارد، داشتن شناخت کافی و تسلط به کار بر روی آن یکی از امتیازات برنامه‌نویسان حرفه‌ای است. پشته‌ها برای نگهداری داده‌هایی استفاده می‌شوند که نظم ورود و خروج در آن‌ها بسیار مهم است. با بررسی دقیق مطالب مربوط به ساختمان داده مانند پشته‌ها و صف‌ها، دانش و مهارت خود را برای حل مسائل پیچیده برنامه‌نویسی تا حد قابل قبولی ارتقا می‌دهیم.