پرش به محتوای اصلی
رزرو مشاوره تلفنی تک جلسه‌ای با استاد رضوی
رزرو مشاوره تلفنی
کنکور کامپیوتر
0
اشتراک
 

ساختمان داده پشته ⚡️ پشته چیست؟ کاربرد پشته در ساختمان داده

این مقاله عالی توضیح داده که پشته چیست و کاربرد پشته در ساختمان داده چیست، همچنین نحوه کارکرد پشته، پیاده سازی پشته و عملیات های پشته را معرفی کرده

پشته بر اساس ساختار LIFO طراحی می‌شود. ساختار LIFO یا Last In First Out بدین معنی است که آخرین عنصری که وارد شده، اولین عنصری است که خارج می‌شود. برای درک بهتر پشته به مثال زیر توجه کنید:

فرض کنید چندتا بشقاب روی هم چیده شده‌اند، ما هربار می‌توانیم دو کار زیر را انجام دهیم:

  • یک بشقاب روی این بشقاب‌ها بگذاریم.
  • بالاترین بشقاب را برداریم.

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

فرض کنید در ابتدا بشقاب A را داریم و سپس به ترتیب بشقاب‌های C ،B و D را روی آن قرار می‌دهیم، حال می‌خواهیم یکی از بشقاب‌ها را برداریم، کدام بشقاب را می‌توانیم برداریم؟ آفرین! بشقاب D. در این مثال با یک نمونه پشته در دنیای واقعی آشنا شدیم.

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

در ادامه این مقاله فیلم های رایگان ساختمان داده که به آنها نیاز دارید نیز در اختیارتان قرار گرفته است.

خب حالا مجددا به توضیح پشته در ساختمان داده ادامه می‌دهیم

نحوه کارکرد پشته

حالا که متوجه شدیم پشته چیست، می‌توانیم نگاهی عمیق‌تر به نحوه کارکرد آن بیندازیم:

  • در پشته برای اضافه کردن عنصر یا برای برداشتن آن باید همیشه جایگاه بالاترین عنصر را بدانیم. برای این منظور یک متغیر به اسم TOP تعریف می‌کنیم که مقدارش همیشه برابر با جایگاه بالاترین عنصر است.
  • در ابتدا که پشته، خالی است و هیچ عنصری در آن وجود ندارد، مقدار TOP را برابر 1- قرار می‌دهیم.
  • در هربار اضافه کردن عنصر (Push)، مقدار TOP را یکی اضافه می‌کنیم یعنی با Push کردن اولین عنصر، مقدار TOP برابر 0 خواهد شد. با Push کردن عنصر بعدی، مقدار TOP برابر 1 خواهد شد و ...
  • با هربار برداشتن عنصر از پشته (Pop)، مقدار TOP را یکی کاهش می‌دهیم.

این تصویر نحوه کارکرد پشته را نمایش می دهد

فیلم های رایگان ساختمان داده که به آنها نیاز دارید

پیاده سازی پشته

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

پیاده سازی پشته با Python

# Stack implementation in python

# Creating a stack
def create_stack():
    stack = []
    return stack


# Creating an empty stack
def check_empty(stack):
    return len(stack) == 0


# Adding items into the stack
def push(stack, item):
    stack.append(item)
    print("pushed item: " + item)


# Removing an element from the stack
def pop(stack):
    if (check_empty(stack)):
        return "stack is empty"

    return stack.pop()


stack = create_stack()
push(stack, str(1))
push(stack, str(2))
push(stack, str(3))
push(stack, str(4))
print("popped item: " + pop(stack))
print("stack after popping an element: " + str(stack))

پیاده سازی پشته با Java

// Stack implementation in Java

class Stack {
  private int arr[];
  private int top;
  private int capacity;

  // Creating a stack
  Stack(int size) {
    arr = new int[size];
    capacity = size;
    top = -1;
  }

  // Add elements into stack
  public void push(int x) {
    if (isFull()) {
      System.out.println("OverFlow\nProgram Terminated\n");
      System.exit(1);
    }

    System.out.println("Inserting " + x);
    arr[++top] = x;
  }

  // Remove element from stack
  public int pop() {
    if (isEmpty()) {
      System.out.println("STACK EMPTY");
      System.exit(1);
    }
    return arr[top--];
  }

  // Utility function to return the size of the stack
  public int size() {
    return top + 1;
  }

  // Check if the stack is empty
  public Boolean isEmpty() {
    return top == -1;
  }

  // Check if the stack is full
  public Boolean isFull() {
    return top == capacity - 1;
  }

  public void printStack() {
    for (int i = 0; i <= top; i++) {
      System.out.println(arr[i]);
    }
  }

  public static void main(String[] args) {
    Stack stack = new Stack(5);

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    stack.pop();
    System.out.println("\nAfter popping out");

    stack.printStack();

  }
}

پیاده سازی پشته با C

// Stack implementation in C

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

int count = 0;

// Creating a stack
struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

void createEmptyStack(st *s) {
  s->top = -1;
}

// Check if the stack is full
int isfull(st *s) {
  if (s->top == MAX - 1)
    return 1;
  else
    return 0;
}

// Check if the stack is empty
int isempty(st *s) {
  if (s->top == -1)
    return 1;
  else
    return 0;
}

// Add elements into stack
void push(st *s, int newitem) {
  if (isfull(s)) {
    printf("STACK FULL");
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  count++;
}

// Remove element from stack
void pop(st *s) {
  if (isempty(s)) {
    printf("\n STACK EMPTY \n");
  } else {
    printf("Item popped= %d", s->items[s->top]);
    s->top--;
  }
  count--;
  printf("\n");
}

// Print elements of stack
void printStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i items[i]);
  }
  printf("\n");
}

// Driver code
int main() {
  int ch;
  st *s = (st *)malloc(sizeof(st));

  createEmptyStack(s);

  push(s, 1);
  push(s, 2);
  push(s, 3);
  push(s, 4);

  printStack(s);

  pop(s);

  printf("\nAfter popping out\n");
  printStack(s);
}

پیاده سازی پشته با C++

// Stack implementation in C++

#include <stdlib.h>
#include <iostream>

using namespace std;

#define MAX 10
int size = 0;

// Creating a stack
struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

void createEmptyStack(st *s) {
  s->top = -1;
}

// Check if the stack is full
int isfull(st *s) {
  if (s->top == MAX - 1)
    return 1;
  else
    return 0;
}

// Check if the stack is empty
int isempty(st *s) {
  if (s->top == -1)
    return 1;
  else
    return 0;
}

// Add elements into stack
void push(st *s, int newitem) {
  if (isfull(s)) {
    cout << "STACK FULL";
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  size++;
}

// Remove element from stack
void pop(st *s) {
  if (isempty(s)) {
    cout << "\n STACK EMPTY \n";
  } else {
    cout << "Item popped= " << s->items[s->top];
    s->top--;
  }
  size--;
  cout << endl;
}

// Print elements of stack
void printStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i < size; i++) {
    cout << s->items[i] << " ";
  }
  cout << endl;
}

// Driver code
int main() {
  int ch;
  st *s = (st *)malloc(sizeof(st));

  createEmptyStack(s);

  push(s, 1);
  push(s, 2);
  push(s, 3);
  push(s, 4);

  printStack(s);

  pop(s);

  cout << "\nAfter popping out\n";
  printStack(s);
}

خرید فیلم های ساختمان داده

در حال حاضر فیلم آموزش ساختمان داده استاد رضوی پرطرفدارترین و پرفروش‌ترین فیلم آموزشی ساختمان داده و الگوریتم کشور است و هر سال بیش از ۶۰۰۰ نفر این فیلم را تهیه می‌کنند

Ramin Razavi 1 30%
ویدیو درس ساختمان داده

تخفیف تا دوشنبه، ۴ آبان

1,800,000 تومان 1,260,000 تومان
رامین رضوی ۶۴ ساعت
Ramin Razavi 1 30%
ویدیو نکته و تست ساختمان داده و طراحی الگوریتم

تخفیف تا دوشنبه، ۴ آبان

1,700,000 تومان 1,190,000 تومان
رامین رضوی ۶۶ ساعت

عملیات های پشته

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

  • Push: یک عنصر را به بالای پشته اضافه می‌کند.
  • Pop: مقدار بالاترین عنصر پشته را می‌خواند و آن را از پشته حذف می‌کند.
  • IsEmpty: بررسی می‌کند که پشته خالی است یا خیر.
  • IsFull: بررسی می‌کند که پشته پر است یا خیر.
  • Peek: مقدار بالاترین عنصر را می‌خواند ولی آن را حذف نمی‌کند.
  • Count: تعداد عناصر پشته را برمی‌گرداند.
  • Display: تمام عناصر پشته را نمایش می‌دهد.

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

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

کاربردهای پشته

تبدیل عبارت

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

  • Infix Prefix
  • Infix Postfix
  • Prefix Infix
  • Prefix Postfix
  • Postfix Infix

جستجوی عقبگرد

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

فراخوانی توابع بازگشتی

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

بررسی پرانتزگذاری

برای اینکه بررسی کنیم که در یک عبارت پرانتزگذاری‌ها به درستی انجام شده‌اند و معتبر هستند از پشته استفاده می‌کنیم. برای مثال در عبارت ((a + b) * (c + d)) پرانتزگذاری‌ها معتبر هستند ولی در عبارت {{a+b})) *(b+d}] پرانتزگذاری‌ها نامعتبر هستند.

برعکس کردن رشته

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

مدیریت حافظه

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

UNDO/REDO

احتمالا تا حالا در حین استفاده از نرم‌افزارهای کامپیوتری با کلیدهای UNDO و REDO برخورد کردید. فرض کنید در یک نرم‌افزار ویرایش متن ما ابتدا حرف A، سپس حرف B و سپس حرف C را وارد کردیم. حال عبارت ABC در نرم‌افزار ویرایش متن وارد شده‌است. متن ایجاد شده به‌ترتیب مراحل ایجاد در پشته ذخیره می‌شود، یعنی ابتدا عبارت A در پشته Push شده، سپس عبارت AB در پشته Push می‌شود و در نهایت عبارت ABC در پشته Push می‌شود. حال اگر جایی در وارد کردن متن موردنظر اشتباه کنیم و بخواهیم به مرحله قبل برگردیم، نرم‌افزار عبارت قبلی را از پشته Pop می‌کند.

جستجوی عمق اول

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

جمع‌بندی

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

پشته چیست؟

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

پشته چگونه کار می‌کند؟

هربار که می‌خواهیم عنصری را به پشته اضافه کنیم، آن را در بالای پشته Push می‌کنیم و هربار که می‌خواهیم عنصر بالایی پشته را حذف کنیم، آن را Pop می‌کنیم.

چه زمانی از پشته استفاده می‌کنیم؟

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

تفاوت صف و پشته چیست؟

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

پیچیدگی زمانی عملیات‌های Push و Pop کردن در پشته از چه مرتبه‌ای است؟

پیچیدگی زمانی عملیات‌های Push و Pop در پشته از مرتبه O(1) است. یعنی این دو عملیات به تعداد عناصر موجود در پشته وابسته نیستند. این ویژگی، پشته را به یک ساختمان داده مناسب برای ذخیره و بازیابی عناصر با ترتیب ثابت تبدیل می‌کند.

این مطلب چقدر به کارت آمد؟4.833333333333311111111114.83 از ۵ 3 رأی
اشتراک

پرسش و پاسخ داوطلبان کنکور ارشد کامپیوتر

سوال شما توسط استاد رضوی پاسخ داده می‌شود و از طریق پیامک به شما اطلاع رسانی می‌شود
×
kb
2 پرسش و پاسخ
avatar
صبا صادقی
پشته عناصر از نوع intاست. در بازه [5,1] کدامیک از خروجی های زیر را نمی توان تولید کرد.
5،4،3،2،1 1،2،3،4،5
1،2،4،3،5 4،3،5،1،2(جواب)
لطفا دلیل انتخاب گزینه آخر روبفرمایید متشکرم
avatar
رامین رضوی
سلام وقت بخیر، سوالات مشاوه‌ای را پاسخ گو هستیم. موفق و پیروز باشید
هیچ نظری ارسال شده در اینجا وجود ندارد
تلگرام اینستاگرام تماس با پشتیبانی: 09378555200 تماس با پشتیبانی: 09378555200
خدمات ما
پشتیبانی کنکور کامپیوتر

سؤالی داری؟ از ۸ صبح تا ۱۰ شب پاسخ‌گوییم.

تماس با پشتیبانی۰۹۳۷۸۵۵۵۲۰۰ پشتیبانی در تلگرامپاسخ‌گویی پیامی
شبکه‌های اجتماعی
کانال تلگرام اینستاگرام آپارات یوتیوب
اشتراک‌گذاری این مطلب

ساختمان داده پشته ⚡️ پشته چیست؟ کاربرد پشته در ساختمان داده

تلگرام واتس‌اپ ایکس
https://www.konkurcomputer.ir/پشته-چیست-stack-data-structure.html
خدمات کنکور کامپیوتر
هر چیزی که برای قبولی لازم داری، یک‌جاخدمات ما

از مشاوره‌ی شخصی با استاد رضوی تا فیلم‌های دروس، پلتفرم‌ها و ابزارهای رایگان

مشاوره‌ی شخصی با استاد رضوی
تماس با پشتیبانی