استک‌ها در داده‌ساختارها و الگوریتم‌ها (DSA)

استک‌ها در داده‌ساختارها و الگوریتم‌ها (DSA)

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

عملیات کلیدی استک

1. Push: اضافه کردن یک عنصر به بالای استک.
2. Pop: حذف عنصر بالای استک.
3. Peek/Top: برگرداندن عنصر بالای استک بدون حذف آن.
4. isEmpty: بررسی اینکه آیا استک خالی است یا خیر.
5. Size: برگرداندن تعداد عناصر موجود در استک.

پیاده‌سازی استک

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

1. استک با استفاده از آرایه

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

عملیات استک با آرایه:

#include <stdio.h>

#include <stdlib.h>

#define MAX 5 // حداکثر اندازه استک

// ساختار استک

struct Stack {

      int arr[MAX];

      int top;

};

// تابع برای مقداردهی اولیه استک

void initStack(struct Stack *stack) {

        stack->top = -1; // استک خالی است

}

// تابع برای بررسی اینکه استک خالی است

int isEmpty(struct Stack *stack) {

          return stack->top == -1;

}

// تابع برای بررسی اینکه استک پر است

int isFull(struct Stack *stack) {

       return stack->top == MAX – 1;

}

// تابع Push برای اضافه کردن یک عنصر به استک

void push(struct Stack *stack, int value) {

       if (isFull(stack)) {

            printf(“Stack Overflow\n”);

   } else {

           stack->arr[++(stack->top)] = value; // افزایش top و اضافه کردن عنصر

           printf(“Pushed %d\n”, value);

      }

}

// تابع Pop برای حذف یک عنصر از استک

int pop(struct Stack *stack) {

      if (isEmpty(stack)) {

            printf(“Stack Underflow\n”);

            return -1;

   } else {

          int poppedValue = stack->arr[(stack->top)–]; // برگرداندن عنصر بالای استک و کاهش top

          return poppedValue;

        }

}

// تابع Peek برای برگرداندن عنصر بالای استک بدون حذف آن

int peek(struct Stack *stack) {

      if (isEmpty(stack)) {

            printf(“Stack is empty\n”);

            return -1;

   } else {

            return stack->arr[stack->top];

      }

}

int main() {

     struct Stack stack;

     initStack(&stack);

    push(&stack, 10);

    push(&stack, 20);

    push(&stack, 30);

    printf(“Top element: %d\n”, peek(&stack));

    printf(“Popped element: %d\n”, pop(&stack));

    printf(“Popped element: %d\n”, pop(&stack));

    return 0;

}

در این پیاده‌سازی:

• استک با استفاده از تابع initStack مقداردهی می‌شود، که در آن top برابر -1 قرار می‌گیرد (که نشان‌دهنده خالی بودن استک است).
• تابع push یک عنصر را به استک اضافه می‌کند و تابع pop عنصر بالای استک را حذف می‌کند.
• peek عنصر بالای استک را بدون حذف آن برمی‌گرداند.

2. استک با استفاده از لیست پیوندی

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

عملیات استک با لیست پیوندی:

#include <stdio.h>

#include <stdlib.h>

// تعریف ساختار گره

struct Node {

           int data;

          struct Node* next;

};

// تابع برای ایجاد یک گره جدید

struct Node* createNode(int value) {

       struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

       newNode->data = value;

       newNode->next = NULL;

       return newNode;

}

// تابع Push برای اضافه کردن یک عنصر به استک

void push(struct Node** top, int value) {

        struct Node* newNode = createNode(value);

        newNode->next = *top;

       *top = newNode;

       printf(“Pushed %d\n”, value);

}

// تابع Pop برای حذف یک عنصر از استک

int pop(struct Node** top) {

    if (*top == NULL) {

         printf(“Stack Underflow\n”);

         return -1;

    } else {

        struct Node* temp = *top;

        int poppedValue = temp->data;

        *top = (*top)->next; // جابجایی top به گره بعدی

        free(temp); // آزاد کردن حافظه گره قدیمی

        return poppedValue;

      }

}

// تابع Peek برای برگرداندن عنصر بالای استک بدون حذف آن

int peek(struct Node* top) {

   if (top == NULL) {

           printf(“Stack is empty\n”);

           return -1;

       } else {

           return top->data;

      }

}

// تابع برای بررسی اینکه استک خالی است

int isEmpty(struct Node* top) {

        return top == NULL;

}

int main() {

       struct Node* top = NULL; // مقداردهی اولیه استک خالی

       push(&top, 10);

       push(&top, 20);

      push(&top, 30);

     printf(“Top element: %d\n”, peek(top));

     printf(“Popped element: %d\n”, pop(&top));

     printf(“Popped element: %d\n”, pop(&top));

    return 0;

}