学习笔记分享，部分内容参考网络教学视频，侵删

栈

先进后出，后进先出

原则：只能从栈顶增加和减少元素

顺序栈

依赖可扩容数组实现

这种写法top恰好是栈中元素的个数，也是下一个元素的下标

• top = 0，栈初始化，栈是空的
• 入栈：arr[top] = 10; top++; arr[top] = 20; top++;
• 访问栈顶元素：arr[top - 1]
• 出栈：top--;
• 栈空：top == 0
• 栈满：top == sizeof(arr) / sizeof(arr[0]) (top 等于元素个数)

代码：

#include <iostream>
using namespace std;

class SeqStack
{
public:
    SeqStack(int size = 10) : mtop(0),
                              mcap(size)
    {
        mpStack = new int[mcap];
    }
    ~SeqStack()
    {
        delete[] mpStack;
        mpStack = nullptr;
    }

public:
    // 入栈
    void push(int val)
    {
        if (mtop == mcap) // 如果满了就扩容
        {
            expand(2 * mcap);
        }
        mpStack[mtop++] = val;
    }

    // 出栈
    void pop()
    {
        if (mtop == 0)
        {
            throw "The stack is empty!";
        }
        mtop--;
    }

    // 获取栈顶元素
    int top() const
    {
        if (mtop == 0)
        {
            throw "The stack is empty!";
        }
        return mpStack[mtop - 1];
    }

    // 判断栈空
    bool empty() const
    {
        return mtop == 0;
    }

    int size() const
    {
        return mtop;
    }

private:
    void expand(int targetSize)
    {
        int *p = new int[targetSize];
        for (int i = 0; i < targetSize; i++)
        {
            p[i] = mpStack[i];
        }
        delete[] mpStack;
        mpStack = p;
        mcap = targetSize;
    }

private:
    int *mpStack;
    int mtop; // 栈顶位置
    int mcap; // 栈空间大小
};

int main()
{
    int arr[] = {12,4,56,7,89,31,53,75};
    SeqStack s;

    for(int v : arr)
    {
        s.push(v);
    }

    // 遍历经典写法：从栈顶访问元素，打印完出栈
    while(!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;

    return 0;
}

链式栈

依赖链表实现

解决数组扩容效率低的问题

我们把头节点处当作入栈的位置，这样就能达到顺序头插，顺着链表逆序打印

为了方便计数，我们比普通链表多封装一个成员变量size_

#include<iostream>
using namespace std;

class LinkStack
{
public:
    LinkStack():size_(0)
    {
        head_ = new Node();
    }
    ~LinkStack()
    {
        Node *p = head_;
        while(p != nullptr)
        {
            head_ = head_->next_;
            delete p;
            p = head_;
        }
        head_ = nullptr;
    }

public:
    // 入栈：头插
    void push(int val)
    {
        Node *node = new Node(val);
        node->next_ = head_->next_;
        head_->next_ = node;
        size_++;
    }

    // 出栈
    void pop()
    {
        if(head_->next_ == nullptr)
        {
            throw "The stack is empty!";
        }
        Node *del = head_->next_;
        head_->next_ = del->next_;
        delete del;
        size_--;
    }

    // 获取栈顶元素
    int top()
    {
        if(head_->next_ == nullptr)
        {
            throw "The stack is empty!";
        }
        return head_->next_->data_;
    }

    // 空
    bool empty() const
    {
        return head_->next_ == nullptr;
    }

    // 返回栈元素个数
    int size() const
    {
        return size_;
    }

private:
    struct Node
    {
        Node(int data = 0) : data_(data),
                             next_(nullptr)
        {
        }
        int data_;
        Node *next_;
    };

    Node *head_;
    int size_;
};

int main()
{
    int arr[] = {12,4,56,7,89,31,53,75};
    LinkStack s;

    for(int v : arr)
    {
        s.push(v);
    }
    cout << "size = " << s.size() << endl;

    // 遍历：从栈顶访问元素，打印完出栈
    while(!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
    cout << "size = " << s.size() << endl;

    return 0;
}

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

**输入：**s = "()"

**输出：**true

示例 2：

输入：s = "()[]{}"

**输出：**true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

**输出：**true

示例 5：

输入：s = "([)]"

**输出：**false

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

代码实现：

#include <iostream>
#include <string>
#include <stack>
using namespace std;

/*
思路：
1. 遍历字符串，遇到左括号入栈
2. 遇到右括号，从栈顶取元素看是否匹配
*/

class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> cs;

        for (char ch : s)
        {
            if (ch == '(' || ch == '[' || ch == '{')
            {
                cs.push(ch);
            }
            else
            {
                // 栈内没有左括号
                if (cs.empty())
                {
                    return false;
                }

                // 遇到右括号
                char cmp = cs.top();
                cs.pop();

                // 遍历到右括号，发现和栈顶左括号不匹配
                if (ch == ')' && cmp != '(' || ch == ']' && cmp != '[' || ch == '}' && cmp != '{')
                {
                    return false;
                }
            }
        }

        // 如果没有处理完有剩余左括号
        return cs.empty();
    }
};

逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

• 1 <= tokens.length <= 104
• tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

代码实现：

#include <iostream>
#include <vector>
#include <string>
#include <stack>
// #include <string>
using namespace std;

/*
思路：
遇到数字入栈，遇到符号出栈
第一个出栈的是右操作数，第二个是左操作数
运算结果再入栈
*/

class Solution
{
public:
    int calculate(int left, int right, char sign)
    {
        switch (sign)
        {
        case '+':
            return left + right;
        case '-':
            return left - right;
        case '*':
            return left * right;
        case '/':
            return left / right;
        }
        throw "Illegal sign!";
    }

    // 向evalRPN传入的是一个装着很多字符串的容器，这些字符串有的是数字有的是符号
    int evalRPN(vector<string> &tokens)
    {
        stack<int> intStack;

        for (string &str : tokens) // 复杂类型优先使用引用
        {
            // 遇到运算符
            // str.size() == 1 避免把符号误判成运算符
            if (str.size() == 1 && (str[0] == '+' || str[0] == '-' || str[0] == '*' || str[0] == '/'))
            {
                int right = intStack.top();
                intStack.pop();

                int left = intStack.top();
                intStack.pop();

                intStack.push(calculate(left, right, str[0]));
            }
            else
            {
                // 遇到数字入栈
                // stoi是包含在string头文件的函数，表示string转int
                intStack.push(stoi(str));
            }
        }
        return intStack.top();
    }
};

中缀表达式转后缀表达式

核心原则：

1. 操作数直接输出（如 3、5 直接加入结果）。
2. 运算符根据优先级入栈 / 出栈：栈顶运算符优先级 ≥ 当前运算符时，弹出栈顶运算符并输出，新的栈顶和当前元素运算符继续比较；否则当前运算符入栈。
3. 括号特殊处理：左括号 ( 直接入栈；遇到右括号 ) 时，弹出栈中运算符直到遇到 (（( 只弹出不输出）。
4. 遍历结束后，弹出栈中剩余运算符。

示例1：

输入：(1+2)*(3+4)

输出：1 2 + 3 + 4 *

示例2：

输入：2+(4+6)/2+6/3

输出：2 4 6 + 2 / + 3 6 / +

代码实现：

#include <iostream>
#include <string>
#include <stack>
using namespace std;

// 判断运算符优先级的函数
int getPrecedence(char op)
{
    switch (op)
    {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    case '(':
        return 0; // 左括号优先级最低
    default:
        return -1; // 非法运算符
    }
}

string MiddleToEnd(string expr)
{
    string result;
    stack<char> s;

    // 遍历字符串
    for (size_t i = 0; i < expr.size(); ++i)
    {
        char ch = expr[i];
        if (ch == ' ')
            continue; // 跳过空格

        // 处理多位数字
        if (isdigit(ch))
        {
            result += ch;
            while (i + 1 < expr.size() && isdigit(expr[i + 1]))
            {
                result += expr[++i];
            }
            result += ' '; // 数字后添加空格
        }
        // 处理左括号
        else if (ch == '(')
        {
            s.push(ch);
        }
        // 处理右括号
        else if (ch == ')')
        {
            while (!s.empty() && s.top() != '(')
            {
                result += s.top();
                result += ' '; // 运算符后添加空格
                s.pop();
            }
            if (!s.empty())
                s.pop(); // 弹出左括号
        }
        // 处理运算符
        else
        {
            while (!s.empty() && getPrecedence(s.top()) >= getPrecedence(ch))
            {
                result += s.top();
                result += ' '; // 运算符后添加空格
                s.pop();
            }
            s.push(ch);
        }
    }

    // 弹出剩余运算符
    while (!s.empty())
    {
        result += s.top();
        result += ' '; // 运算符后添加空格
        s.pop();
    }

    // 移除末尾多余空格
    if (!result.empty() && result.back() == ' ')
    {
        result.pop_back();
    }

    return result;
}

int main()
{
    // 测试用例
    string testCases[] = {
        "3+4*(2-1)",             // 预期: 3 4 2 1 - * +
        "123+45*67",             // 预期: 123 45 67 * +
        "(3+4)*5-6/2",           // 预期: 3 4 + 5 * 6 2 / -
        "5+3*(2+4*2)/(1+3*2-4)", // 预期: 5 3 2 4 2 * + * 1 3 2 * + 4 - / +
    };

    for (const auto &expr : testCases)
    {
        cout << "中缀表达式: " << expr << endl;
        cout << "后缀表达式: " << MiddleToEnd(expr) << endl;
        cout << "------------------------" << endl;
    }

    return 0;
}