数据结构：第二十节-栈的应用

Cpp入门到精通 2024-06-13

109

点击蓝字

山月

关注我们

第二十节栈的应用

栈（Stack）是一种重要的数据结构，具有后进先出（LIFO, Last In First Out）的特点。在实际应用中，栈的这种特性使得它在很多场景下非常有用。这节我们来给出并分析栈的一些应用实例。

1.第一个要给出的典型实例就是括号匹配，栈可以用来检查括号匹配问题，确保括号的使用是成对且正确的。

例如，字符串 "{[()]}" 是匹配的，而 "{[(])}" 是不匹配的。

#include <iostream>
#include <stack>
#include <unordered_map>
#include <string>
using namespace std;
bool is_balanced(const string& ex) {
    stack<char> stack;
    unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} };


    for (char c : ex) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        }
        else if (c == ')' || c == ']' || c == '}') {
            if (stack.empty() || stack.top() != pairs[c]) {
                return false;
            }
            stack.pop();
        }
    }
    return stack.empty();
}


int main() {
    string ex1 = "{[()()]}";
    cout  << boolalpha << is_balanced(ex1) << endl;  // 输出 true


    string ex2 = "{[(])}";
    cout << boolalpha << is_balanced(ex2) << endl;  // 输出 false


    return 0;
}

在布尔函数当中，我们使用栈 stack 来保存遇到的左括号。使用哈希映射 pairs 来定义右括号与其对应的左括号的匹配关系。

在for循环当中，如果字符是左括号（(、[、{），则将其压入栈中。如果字符是右括号（)、]、}），则检查栈是否为空或者栈顶元素是否是与当前右括号匹配的左括号：如果栈为空或栈顶元素不匹配，返回 false。如果匹配，则弹出栈顶元素。

遍历完表达式后，如果栈为空，说明所有的左括号都找到了匹配的右括号，返回 true。如果栈不为空，说明有未匹配的左括号，返回 false。

在主函数中我们进行了测试，测试表达式 {[()()]}，每个左括号都能找到对应的右括号，栈最终为空，返回 true。测试表达式 {[(])}，当遇到 ] 时，栈顶元素是 (，不匹配，返回 false。

true
false

表达式1操作过程：

表达式    |  栈
---------|---------
{[()()]} | 空
[()()]}  | {          //压入{
()()]}   | {[         //压入[
)()]}    | {[(        //压入(
()]}     | {[         //压入),)匹配(,弹出)(
)]}      | {[(        //压入(
]}       | {[         //压入),)匹配(,弹出)(
}        | {          //压入],]匹配[，弹出][
         | 空         //压入}，}匹配{，弹出}{
         |            //栈空

表达式2操作过程：

表达式    |  栈
---------|---------
{[(])}   | 空
[(])}    | {        //压入{
(])}     | {[       //压入[ 
])}      | {[(      //压入(
)}       | {[(      //]不匹配(,false

第二个例子我们来看进制转换：

我们选取的案例是将十进制数转换为二进制，我们先将进制数取余，这里将十进制数除以目标进制，记录余数。将商继续除以目标进制，直到商为零。余数每次都压入栈中，然后依次弹出栈中的元素，得到转换后的结果。

比如说我们将十进制数42转换为二进制数，

计算过程：

42 ÷ 2 = 21，余数是 0

21 ÷ 2 = 10，余数是 1

10 ÷ 2 = 5，余数是 0

5 ÷ 2 = 2，余数是 1

2 ÷ 2 = 1，余数是 0

1 ÷ 2 = 0，余数是 1

栈的使用：

将每次的余数压入栈中，最终弹出栈中的元素得到结果，结果为101010。

#include <iostream>
#include <stack>
#include <string>
using namespace std;
string func(int num) {
    stack<int> stack;
    while (num > 0) {
        stack.push(num % 2);
        num = 2;
    }


    string binary = "";
    while (!stack.empty()) {
        binary += to_string(stack.top());
        stack.pop();
    }
    return binary;
}


int main() {
    int num = 42;
    string binary = func(num);
    cout << "十进制数: " << num << endl;
    cout << "二进制数: " << binary << endl;
    return 0;
}