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

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

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

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

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

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

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

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

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

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

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

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

فیلم ساختمان داده جلسه 1

فیلم ساختمان داده جلسه 2

فیلم ساختمان داده جلسه 3

فیلم ساختمان داده جلسه 4

فیلم ساختمان داده جلسه 5

فیلم ساختمان داده جلسه 6

فیلم ساختمان داده جلسه 7

فیلم ساختمان داده جلسه 8

حل تست ساختمان و الگوریتم جلسه 1

حل تست ساختمان و الگوریتم جلسه 2

حل تست ساختمان و الگوریتم جلسه 3

حل تست ساختمان و الگوریتم جلسه 4

انواع پیمایش‌های درخت

نحوه ساخت درخت BST

آموزش درخت B-Tree

بررسی مرتبه ساخت هیپ

آموزش مرتب سازی سریع

آموزش شبکه شار

حل سوالات ساختمان ارشد کامپیوتر 99

حل ساختمان ارشد 95 بخش 1

حل ساختمان ارشد 95 بخش 2

نمایش بیشتر

نمایش کمتر

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

حالا که با نحوه پیاده سازی پشته هم آشنا شدیم وقت آن است که یک پشته ساده را پیاده کنیم. متداول‌ترین روش پیاده سازی پشته، استفاده از آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100در این مقاله موارد زیر بررسی شده است : 1- آرایه چیست 2- انواع اندیس گذاری در آرایه 3- انواع آرایه 4- محاسبه آدرس در آرایه 5- محاسبه شماره در آرایه 6- آرایه در برنامه نویسی 7- مزایای استفاده از آرایه است ولی می‌توان آن را با استفاده از لیست هم پیاده‌سازی کرد.

پیاده سازی پشته با 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))

# 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();

  }
}

// 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);
}

// 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);
}

// 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);
}

کپی کردن کد

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

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

ویدیو درس ساختمان داده

جشنواره به‌وقت بهار

20% 730,000 تومان 584,000 تومان

رامین رضوی

۶۴ ساعت

اطلاعات دوره

ویدیو نکته و تست ساختمان داده و طراحی الگوریتم

جشنواره به‌وقت بهار

15% 650,000 تومان 552,500 تومان

رامین رضوی

۶۶ ساعت

اطلاعات دوره

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

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

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

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

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

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

تبدیل عبارت

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

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

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

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

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

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

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

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

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

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

مدیریت حافظه

مدیریت حافظه یکی از مهمترین وظایف سیستم عاملسیستم عامل چیست به زبان ساده، چرا باید از OS استفاده کنیم؟این مقاله عالی به معرفی سیستم عامل (Operating System|OS) به زبان ساده پرداخته، همچنین بررسی کرده که چرا باید از سیستم عامل استفاده کنیم است. سیستم عامل به‌صورت گسترده از پشته برای مدیریت حافظه استفاده می‌کند.

UNDO/REDO

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

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

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

جمع‌بندی

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

مطالب مرتبط

همه مقالات

درخت تصمیم یا درخت تصمیم گیری چیست و چگونه کار می کند؟

درخت قرمز سیاه، آموزش درخت قرمز سیاه در ساختمان داده

گیت (Git) چیست؟ و چگونه از آن استفاده کنیم؟

هیپ فیبوناچی یا هرم فیبوناچی