C++ stack适配器后进先出数据结构应用-C++-PHP中文网

C++ stack适配器后进先出数据结构应用

P粉602998670

发布： 2025-08-20 10:10:02

原创

198人浏览过

C++ stack适配器基于vector、deque或list实现LIFO结构，提供push、pop、top操作，适用于括号匹配、表达式求值等场景，可通过自定义容器实现有界栈以满足特定需求。

c++ stack适配器后进先出数据结构应用

C++

stack

登录后复制

适配器本质上是利用现有的容器（如

vector

登录后复制

、

deque

登录后复制

或

list

登录后复制

）来实现后进先出（LIFO）的数据结构。它提供了一种方便的方式来管理数据的进出顺序，常用于解决需要追踪最近操作或需要回溯算法的问题。

解决方案

C++

stack

登录后复制

适配器允许你使用标准容器作为底层存储，并提供

push

登录后复制

、

pop

登录后复制

、

top

登录后复制

等方法来实现栈的功能。

#include <iostream>
#include <stack>
#include <vector>

int main() {
    // 使用 vector 作为底层容器
    std::stack<int, std::vector<int>> myStack;

    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    std::cout << "Top element: " << myStack.top() << std::endl; // 输出: 30

    myStack.pop();
    std::cout << "Top element after pop: " << myStack.top() << std::endl; // 输出: 20

    std::cout << "Stack size: " << myStack.size() << std::endl; // 输出: 2

    return 0;
}

登录后复制

在这个例子中，我们使用了

std::vector

登录后复制

作为

std::stack

登录后复制

的底层容器。当然，你也可以选择

std::deque

登录后复制

或

std::list

登录后复制

，这取决于你的具体需求。例如，如果你需要频繁地在栈的底部进行操作，

std::deque

登录后复制

可能更合适，因为它在两端插入和删除元素的时间复杂度都是 O(1)。

如何选择 stack 的底层容器？性能考量

选择

stack

登录后复制

的底层容器时，需要考虑你的应用场景和性能需求。

vector

登录后复制

通常是默认的选择，因为它在大多数情况下提供了良好的性能。但是，

vector

登录后复制

在内存重新分配时可能会导致性能下降。

deque

登录后复制

在两端插入和删除元素时具有更好的性能，但访问中间元素可能会比较慢。

list

登录后复制

在插入和删除元素时具有最佳性能，但访问任何元素都需要线性时间。

立即学习“C++免费学习笔记（深入）”；

例如，如果你的栈需要频繁地插入和删除元素，但很少访问中间元素，那么

list

登录后复制

可能是一个不错的选择。但是，如果你的栈需要频繁地访问中间元素，那么

vector

登录后复制

或

deque

登录后复制

可能会更好。

#include <iostream>
#include <stack>
#include <deque>

int main() {
    // 使用 deque 作为底层容器
    std::stack<int, std::deque<int>> myStack;

    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    std::cout << "Top element: " << myStack.top() << std::endl;

    return 0;
}

登录后复制

stack 在解决算法问题中的典型应用场景

stack

登录后复制

在解决算法问题中有很多典型的应用场景，例如：

即构数智人

即构数智人是由即构科技推出的AI虚拟数字人视频创作平台，支持数字人形象定制、短视频创作、数字人直播等。

查看详情

括号匹配： 检查表达式中的括号是否正确匹配。
表达式求值： 将中缀表达式转换为后缀表达式，并计算表达式的值。
深度优先搜索（DFS）： 在图或树中进行深度优先搜索。
函数调用栈： 模拟函数调用栈的行为。
浏览器的前进/后退功能： 记录用户浏览历史。

下面是一个使用

stack

登录后复制

实现括号匹配的例子：

#include <iostream>
#include <stack>
#include <string>

bool isMatching(const std::string& expression) {
    std::stack<char> s;
    for (char c : expression) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (s.empty()) {
                return false; // 缺少左括号
            }
            char top = s.top();
            s.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false; // 括号不匹配
            }
        }
    }
    return s.empty(); // 所有括号都匹配
}

int main() {
    std::string expression1 = "([]{})";
    std::string expression2 = "([)]";

    std::cout << expression1 << " is matching: " << isMatching(expression1) << std::endl; // 输出: true
    std::cout << expression2 << " is matching: " << isMatching(expression2) << std::endl; // 输出: false

    return 0;
}

登录后复制

如何自定义 stack 的底层容器以满足特定需求

虽然

vector

登录后复制

、

deque

登录后复制

和

list

登录后复制

已经提供了很好的通用性，但在某些特殊情况下，你可能需要自定义

stack

登录后复制

的底层容器。例如，你可能需要使用一个固定大小的数组来实现一个有界栈，或者你可能需要使用一个自定义的内存分配器来优化内存使用。

要自定义

stack

登录后复制

的底层容器，你需要创建一个满足以下要求的类：

提供
```
push_back
```
登录后复制
方法，用于在容器末尾添加元素。
提供
```
pop_back
```
登录后复制
方法，用于删除容器末尾的元素。
提供
```
back
```
登录后复制
方法，用于访问容器末尾的元素。
提供
```
empty
```
登录后复制
方法，用于检查容器是否为空。
提供
```
size
```
登录后复制
方法，用于获取容器的大小。

下面是一个使用固定大小数组实现有界栈的例子：

#include <iostream>
#include <stack>

template <typename T, size_t N>
class BoundedArray {
private:
    T data[N];
    size_t currentSize = 0;

public:
    void push_back(const T& value) {
        if (currentSize == N) {
            throw std::overflow_error("Stack overflow");
        }
        data[currentSize++] = value;
    }

    void pop_back() {
        if (currentSize == 0) {
            throw std::underflow_error("Stack underflow");
        }
        currentSize--;
    }

    T& back() {
        if (currentSize == 0) {
            throw std::underflow_error("Stack is empty");
        }
        return data[currentSize - 1];
    }

    bool empty() const {
        return currentSize == 0;
    }

    size_t size() const {
        return currentSize;
    }
};

int main() {
    std::stack<int, BoundedArray<int, 5>> myStack;

    try {
        myStack.push(10);
        myStack.push(20);
        myStack.push(30);
        myStack.push(40);
        myStack.push(50);
        myStack.push(60); // 触发 overflow
    } catch (const std::exception& e) {
        std::cerr << "Exception: " << e.what() << std::endl; // 输出: Stack overflow
    }

    std::cout << "Stack size: " << myStack.size() << std::endl; // 输出: 5

    return 0;
}

登录后复制

在这个例子中，我们创建了一个