پشته ها، ساختارهای داده – انجمن DEV

پشته ها

پشته یک ساختار داده بنیادی در علوم کامپیوتر است که بر اساس اصل Last In, First Out (LIFO) عمل می کند. این بدان معنی است که آخرین عنصر اضافه شده به پشته اولین عنصری است که حذف می شود. پشته ها مشابه انبوهی از صفحات هستند که شما فقط می توانید صفحه بالایی را اضافه یا حذف کنید. این سادگی و محدودیت در نحوه افزودن و حذف عناصر، پشته ها را به ویژه برای انواع خاصی از مسائل و الگوریتم ها مفید می کند.

مفاهیم اولیه پشته ها

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

2. عملیات پاپ: این عملیات عنصر بالایی را از پشته حذف می کند. اگر پشته خالی باشد، ممکن است یک خطای زیر جریان پشته رخ دهد.

3. عملیات زیرچشمی (یا بالا).: این عملیات عنصر بالای پشته را بدون حذف آن برمی گرداند. برای دسترسی به عنصر بالا بدون تغییر پشته مفید است.

4. عملیات خالی است: این عملیات خالی بودن پشته را بررسی می کند. اگر پشته هیچ عنصری نداشته باشد true را برمی گرداند، در غیر این صورت false.

5. عملیات اندازه: این عملیات تعداد عناصر موجود در پشته را برمی گرداند.

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

ویژگی های پشته ها

1. ساختار LIFO: مشخصه تعیین کننده یک پشته ماهیت Last In, First Out (LIFO) آن است. این بدان معنی است که جدیدترین عنصر اضافه شده اولین عنصری است که حذف می شود. این ویژگی برای سناریوهایی که در آن موارد اخیر باید ابتدا پردازش شوند بسیار مهم است.

2. عملیات در یک انتها انجام می شود: تمام عملیات (فشار، پاپ، زیرچشمی) در انتهای بالای پشته انجام می شود. این باعث می شود که عملیات پشته از نظر پیچیدگی زمانی بسیار کارآمد باشد، معمولاً O(1) برای این عملیات.

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

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

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

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

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

1. پیاده سازی مبتنی بر آرایه

در یک پشته مبتنی بر آرایه، یک آرایه با اندازه ثابت برای ذخیره عناصر پشته استفاده می شود. یک شاخص (که اغلب به آن شاخص “بالا” گفته می شود) موقعیت آخرین عنصر اضافه شده را پیگیری می کند.

• مزایای:

  • ساده برای پیاده سازی.
  • دسترسی سریع به عناصر (O(1) برای عملیات فشار و پاپ) را فراهم می کند.
  • حافظه به هم پیوسته است که منجر به عملکرد بهتر کش می شود.

• محدودیت ها:

  • اندازه ثابت، به این معنی که اگر پشته از ظرفیت آرایه بیشتر شود، می‌تواند سرریز شود.
  • تغییر اندازه آرایه (برای مدیریت سرریز) می تواند زمان بر و حافظه فشرده باشد.

2. پیاده سازی مبتنی بر لیست پیوندی

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

• مزایای:

  • اندازه پویا، به این معنی که می تواند در صورت نیاز بدون نگرانی در مورد سرریز شدن رشد کرده و کوچک شود (تا زمانی که حافظه در دسترس باشد).
  • نیازی به از پیش تعریف کردن اندازه پشته نیست.

• محدودیت ها:

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

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

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

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

ایجاد پشته

برای پیاده سازی یک پشته با استفاده از آرایه ها در C++، ابتدا یک کلاس تعریف می کنیم Stack با ویژگی های اصلی و سازنده اش. در زیر بخشی از کد برای Stack کلاس با ویژگی های اساسی و سازنده آن:

#include 
using namespace std;

class Stack {
private:
    int* arr;
    int top;
    int capacity;

public:
    // Constructor to initialize stack
    Stack(int size) {
        arr = new int[size];
        capacity = size;
        top = -1;
    }

    // Destructor to free memory allocated to the array
    ~Stack() {
        delete[] arr;
    }
};

توضیح صفات:

1. arr: این یک اشاره گر به یک آرایه عدد صحیح است که عناصر پشته را ذخیره می کند. آرایه به صورت پویا بر اساس ظرفیت ارائه شده در طول اولیه سازی پشته تخصیص می یابد.

2. بالا: این متغیر عدد صحیح شاخص عنصر بالای پشته را ردیابی می کند. در ابتدا روی -1 تنظیم می شود که نشان دهنده خالی بودن پشته است.

3. ظرفیت: این متغیر عدد صحیح حداکثر تعداد عناصری را که پشته می تواند نگه دارد را مشخص می کند. زمانی تنظیم می شود که پشته مقدار دهی اولیه شود و در طول عمر پشته تغییر نمی کند.

توضیح سازنده:

سازنده Stack(int size) پشته را با ظرفیت مشخص مقداردهی اولیه می کند:

• arr = int جدید[size]: حافظه را برای آرایه پشته بر اساس اندازه داده شده اختصاص می دهد.
• ظرفیت = اندازه: ظرفیت پشته را تنظیم می کند.
• بالا = -1: شاخص بالا را به -1 راه اندازی می کند که نشان می دهد پشته در حال حاضر خالی است.

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

عملیات روی پشته ها (پیاده سازی آرایه)

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

عملیات فشار

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

void push(int x) {
    if (isFull()) {
        cout << "Overflow: Stack is full.\n";
        return;
    }
    arr[++top] = x;
}

Time Complexity: O(1)

عملیات پاپ

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

int pop() {
    if (isEmpty()) {
        cout << "Underflow: Stack is empty.\n";
        return -1;
    }
    return arr[top--];
}

Time Complexity: O(1)

عملیات زیرچشمی

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

int peek() {
    if (!isEmpty()) {
        return arr[top];
    } else {
        cout << "Stack is empty.\n";
        return -1;
    }
}

Time Complexity: O(1)

عملیات خالی است

عملیات isEmpty با بررسی اینکه آیا شاخص بالایی -1 است، خالی بودن پشته را بررسی می کند.

bool isEmpty() {
    return top == -1;
}

Time Complexity: O(1)

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

عملیات isFull با مقایسه شاخص بالایی با حداکثر ظرفیت منهای یک، پر بودن پشته را بررسی می کند.

bool isFull() {
    return top == capacity - 1;
}

Time Complexity: O(1)

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

پیاده سازی کد کامل پشته ها با استفاده از آرایه ها

در زیر پیاده سازی کامل یک پشته با استفاده از آرایه ها در C++ آمده است. این پیاده سازی عملیات پشته را در یک کلاس محصور می کند و راهی تمیز و کارآمد برای مدیریت داده های پشته ارائه می کند.

#include 
using namespace std;

class Stack {
private:
    int* arr;
    int top;
    int capacity;

public:
    // Constructor to initialize stack
    Stack(int size) {
        arr = new int[size];
        capacity = size;
        top = -1;
    }

    // Destructor to free memory allocated to the array
    ~Stack() {
        delete[] arr;
    }

    // Utility function to add an element `x` to the stack
    void push(int x) {
        if (isFull()) {
            cout << "Overflow: Stack is full.\n";
            return;
        }
        arr[++top] = x;
    }

    // Utility function to pop the top element from the stack
    int pop() {
        if (isEmpty()) {
            cout << "Underflow: Stack is empty.\n";
            return -1;
        }
        return arr[top--];
    }

    // Utility function to return the top element of the stack
    int peek() {
        if (!isEmpty()) {
            return arr[top];
        } else {
            cout << "Stack is empty.\n";
            return -1;
        }
    }

    // Utility function to check if the stack is empty
    bool isEmpty() {
        return top == -1;
    }

    // Utility function to check if the stack is full
    bool isFull() {
        return top == capacity - 1;
    }

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

int main() {
    Stack stack(3);

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

    cout << "Top element is: " << stack.peek() << endl;

    cout << "Stack size is " << stack.size() << endl;

    stack.pop();
    stack.pop();
    stack.pop();

    if (stack.isEmpty()) {
        cout << "Stack is empty\n";
    } else {
        cout << "Stack is not empty\n";
    }

    return 0;
}

پیاده سازی پشته با استفاده از لیست پیوندی در C++

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

ایجاد پشته

برای پیاده سازی یک پشته با استفاده از یک لیست پیوندی در C++، پشته را در یک کلاس کپسوله می کنیم. در زیر یک پیاده‌سازی مبتنی بر کلاس از یک پشته با استفاده از یک لیست پیوندی، شامل ویژگی‌ها و سازنده آن است.

#include 
using namespace std;

class Stack {
private:
    struct Node {
        int data;
        Node* next;
        Node(int val) : data(val), next(nullptr) {}
    };

    Node* top;

public:
    // Constructor to initialize stack
    Stack() : top(nullptr) {}

    // Destructor to free memory allocated to the linked list
    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }
};

توضیح صفات:

1. بالا: این یک اشاره گر به گره بالای پشته است که نشان دهنده آخرین عنصری است که روی پشته فشار داده شده است.

توضیح سازنده:

سازنده Stack() با تنظیم نشانگر بالا، پشته را مقداردهی اولیه می کند nullptr، که یک پشته خالی را نشان می دهد.

• بالا = nullptr: نشانگر بالا را به مقدار دهی اولیه می کند nullptr، نشان می دهد که پشته خالی است.

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

عملیات روی پشته ها (پیاده سازی لیست پیوندی)

اجرای عملیات پشته با استفاده از یک لیست پیوندی امکان تخصیص حافظه پویا و دستکاری موثر عناصر را فراهم می کند. در زیر عملیات اساسی یک پشته – push، pop، peek و isEmpty – به همراه پیاده سازی های مربوطه آنها با استفاده از یک لیست پیوندی آورده شده است.

عملیات فشار

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

// Utility function to add an element `x` to the stack
void push(int x) {
    Node* newNode = new Node(x);
    newNode->next = top;
    top = newNode;
}

Time Complexity: O(1)

عملیات پاپ

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

// Utility function to pop the top element from the stack
int pop() {
    if (isEmpty()) {
        cout << "Underflow: Stack is empty.\n";
        return -1;
    }
    Node* temp = top;
    int poppedValue = temp->data;
    top = top->next;
    delete temp;
    return poppedValue;
}

Time Complexity: O(1)

عملیات زیرچشمی

عملیات peek عنصر بالایی پشته را بدون حذف آن برمی گرداند. این عملیات شامل دسترسی به داده های گره بالایی است.

// Utility function to return the top element of the stack
int peek() {
    if (isEmpty()) {
        cout << "Stack is empty.\n";
        return -1;
    }
    return top->data;
}

Time Complexity: O(1)

عملیات خالی است

عملیات isEmpty با بررسی اینکه آیا نشانگر بالایی وجود دارد یا خیر، خالی بودن پشته را بررسی می کند nullptr.

// Utility function to check if the stack is empty
bool isEmpty() {
    return top == nullptr;
}

Time Complexity: O(1)

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

با اجرای این عملیات، اطمینان حاصل می کنیم که پشته می تواند به طور موثر برای اهداف مورد نظر خود، مانند مدیریت داده ها به ترتیب Last-In-First-Out (LIFO) استفاده شود. هر عملیات به گونه ای طراحی شده است که در زمان ثابت اجرا شود و عملکرد سریع و قابل پیش بینی را تضمین کند.

پیاده سازی کد کامل پشته ها با استفاده از لیست پیوندی

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

#include 
using namespace std;

class Stack {
private:
    struct Node {
        int data;
        Node* next;
        Node(int val) : data(val), next(nullptr) {}
    };

    Node* top;

public:
    // Constructor to initialize stack
    Stack() : top(nullptr) {}

    // Destructor to free memory allocated to the linked list
    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }

    // Utility function to add an element `x` to the stack
    void push(int x) {
        Node* newNode = new Node(x);
        newNode->next = top;
        top = newNode;
    }

    // Utility function to pop the top element from the stack
    int pop() {
        if (isEmpty()) {
            cout << "Underflow: Stack is empty.\n";
            return -1;
        }
        Node* temp = top;
        int poppedValue = temp->data;
        top = top->next;
        delete temp;
        return poppedValue;
    }

    // Utility function to return the top element of the stack
    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty.\n";
            return -1;
        }
        return top->data;
    }

    // Utility function to check if the stack is empty
    bool isEmpty() {
        return top == nullptr;
    }
};

int main() {
    Stack stack;

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

    cout << "Top element is: " << stack.peek() << endl;

    cout << "Popping elements from the stack:\n";
    cout << stack.pop() << " ";
    cout << stack.pop() << " ";
    cout << stack.pop() << endl;

    if (stack.isEmpty()) {
        cout << "Stack is empty\n";
    } else {
        cout << "Stack is not empty\n";
    }

    return 0;
}

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