【数据结构】栈算法（算法原理+源码）

博主介绍：?全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战?有需要可以联系作者我哦！

🍅附上相关C语言版源码讲解🍅

👇🏻 精彩专栏推荐订阅👇🏻 不然下次找不到哟

目录

一、栈算法

栈的基本操作：

栈的应用：

栈的实现方式：

二、算法实现

?三、小结

大家点赞、收藏、关注、评论啦 ！

谢谢哦！如果不懂，欢迎大家下方讨论学习哦。

一、栈算法

栈（Stack）是一种具有特定规则的数据结构，它基于后进先出（Last In, First Out，LIFO）的原则。这意味着最后进栈的元素将会是最先出栈的。栈常常用于实现函数调用、表达式求值、括号匹配等问题。

栈的基本操作：

1. Push： 将元素压入栈顶。
2. Pop： 从栈顶弹出元素。
3. Top（或Peek）： 查看栈顶元素但不弹出。
4. isEmpty： 检查栈是否为空。
5. Size： 获取栈中元素的数量。

栈的应用：

1. 函数调用： 保存函数调用的上下文，包括局部变量、返回地址等。
2. 表达式求值： 中缀表达式转后缀表达式，然后使用栈进行求值。
3. 括号匹配： 检查表达式中的括号是否匹配。
4. 浏览器前进后退： 使用两个栈分别保存前进和后退的页面。
5. 撤销操作： 记录操作历史，可以通过栈实现撤销功能。

栈的实现方式：

1. 数组： 使用数组实现栈，需要注意栈的大小限制。
2. 链表： 使用链表实现栈，动态分配内存，栈大小可以灵活调整。?

二、算法实现

?通过 push、pop 和 peek 操作对栈进行操作。

#include <iostream>
#define MAX_SIZE 100

class Stack {
private:
    int arr[MAX_SIZE];
    int top;

public:
    Stack() {
        top = -1;
    }

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

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

    void push(int value) {
        if (!isFull()) {
            arr[++top] = value;
            std::cout << "Pushed: " << value << std::endl;
        } else {
            std::cout << "Stack overflow!" << std::endl;
        }
    }

    void pop() {
        if (!isEmpty()) {
            std::cout << "Popped: " << arr[top--] << std::endl;
        } else {
            std::cout << "Stack underflow!" << std::endl;
        }
    }

    int peek() {
        if (!isEmpty()) {
            return arr[top];
        } else {
            std::cout << "Stack is empty!" << std::endl;
            return -1; // Assuming -1 as an error value
        }
    }
};

int main() {
    Stack myStack;
    myStack.push(5);
    myStack.push(10);
    myStack.push(20);

    std::cout << "Top of the stack: " << myStack.peek() << std::endl;

    myStack.pop();
    myStack.pop();
    myStack.pop();
    myStack.pop(); // Trying to pop from an empty stack

    return 0;
}

执行结果：

?三、小结

堆栈（栈）是一种基本的数据结构，其优点主要应用在一下方面：

1. 简单直观： 栈的操作相对简单，主要包括入栈（Push）和出栈（Pop）两种基本操作。这种简单性使得栈易于理解和实现。

2. 高效的操作： 由于遵循后进先出（LIFO）的原则，栈的操作具有常数时间复杂度。入栈和出栈的操作都只涉及栈顶元素，不需要遍历整个数据结构，因此效率较高。

3. 内存管理： 栈的内存管理是自动的，当一个函数被调用时，其局部变量和函数调用信息被压入栈，函数执行完毕后自动弹出。这种自动管理有助于避免内存泄漏和提高程序的稳定性。

4. 函数调用： 栈被广泛用于实现函数调用。每次函数调用时，局部变量和返回地址被存储在栈中，函数执行完毕后可以轻松地回到调用点。

5. 递归： 栈为递归算法提供了自然的支持。递归调用时，每次调用都会创建一个新的栈帧，形成递归调用链。

6. 表达式求值： 栈在中缀表达式转后缀表达式、以及后缀表达式求值等方面的应用是非常常见的，提供了一种简单而有效的解决方案。

7. 回溯算法： 在深度优先搜索中，通常使用栈来存储搜索路径，以便回溯到先前的状态。

8. 括号匹配： 栈常被用来检查表达式中的括号是否匹配，这是许多编程语言编译器和解释器的基本操作。

大家点赞、收藏、关注、评论啦 ！

谢谢哦！如果不懂，欢迎大家下方讨论学习哦。