برنامه مسیر ۸ ماهه تا کنکور: مشاوره خصوصیت با استاد رضوی رو رزرو کن!
رزرو مشاوره
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

نمایش بیشتر
نمایش کمتر

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

حالا که با نحوه پیاده سازی پشته هم آشنا شدیم وقت آن است که یک پشته ساده را پیاده کنیم. متداول‌ترین روش پیاده سازی پشته، استفاده از آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100آموزش آرایه در ساختمان داده به زبان ساده و از 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))

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

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

۳۰٪ تخفیف

990,000 تومان 695,000 تومان
رامین رضوی
۶۴ ساعت
Ramin Razavi 1

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

۳۰٪ تخفیف

900,000 تومان 630,000 تومان
رامین رضوی
۶۶ ساعت

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

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

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

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

تبدیل عبارت

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

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

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

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

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

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

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

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

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

مدیریت حافظه

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

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.75 1 1 1 1 1 1 1 1 1 14.75 امتیاز (2 رای)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام تماس با پشتیبانی: 09378555200 تماس با پشتیبانی: 09378555200