dc的house
large picture of the cover

栈与队列总结

栈与队列是计算机科学中最基础的数据结构之一，广泛应用于算法设计、系统开发、编译器实现等领域。尽管它们的概念简单，但深入理解其底层实现和应用场景，对于提升编程能力和解决复杂问题至关重要。本文将从理论基础、经典题目、系统应用等多个角度，全面总结栈与队列的知识点，并结合代码示例帮助读者更好地掌握这些内容。

一、栈与队列的理论基础

1. 栈与队列的基本概念

  • 栈（Stack）：一种后进先出（LIFO, Last In First Out）的数据结构。只允许在一端（栈顶）进行插入和删除操作。
  • 队列（Queue）：一种先进先出（FIFO, First In First Out）的数据结构。允许在一端（队尾）插入元素，在另一端（队头）删除元素。

2. 栈与队列的实现

在C++中，栈和队列是通过容器适配器（Container Adapter）实现的，它们的底层容器可以是 deque、list 或 vector 等。

灵魂四问

  1. C++中 stack 和 queue 是容器吗？

    • 不是。它们是容器适配器，基于其他容器（如 deque）实现。

  2. 我们使用的 stack 和 queue 属于哪个版本的STL？

    • 它们属于C++标准模板库（STL），是C++标准的一部分。

  3. stack 和 queue 是如何实现的？

    • 默认情况下，stack 和 queue 的底层容器是 deque。deque 是一种双端队列，支持在两端高效地插入和删除元素。

  4. stack 和 queue 提供迭代器来遍历空间吗？

    • 不提供。栈和队列的设计目的是限制访问方式，因此不支持迭代器。

3. 栈与队列的内存分布

  • 栈：栈的元素在内存中不一定是连续分布的，因为其底层容器可能是 deque，而 deque 的内存分布是不连续的。
  • 队列：队列的元素在内存中同样不一定是连续的，原因与栈相同。

面试题：栈里面的元素在内存中是连续分布的吗？

  • 陷阱1：栈是容器适配器，底层容器可以是 deque、list 或 vector，因此元素在内存中不一定是连续的。
  • 陷阱2：默认情况下，栈的底层容器是 deque，而 deque 的内存分布是不连续的。

二、栈与队列的基本操作

1. 用栈实现队列

题目要求使用栈实现队列的功能。我们可以使用两个栈，一个用于输入，一个用于输出。

class MyQueue {
private:
    stack<int> inStack, outStack;

    void moveElements() {
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }

public:
    void push(int x) {
        inStack.push(x);
    }

    int pop() {
        if (outStack.empty()) {
            moveElements();
        }
        int x = outStack.top();
        outStack.pop();
        return x;
    }

    int peek() {
        if (outStack.empty()) {
            moveElements();
        }
        return outStack.top();
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

2. 用队列实现栈

题目要求使用队列实现栈的功能。我们可以使用一个队列，通过调整元素顺序来模拟栈的行为。

class MyStack {
private:
    queue<int> q;

public:
    void push(int x) {
        q.push(x);
        for (int i = 0; i < q.size() - 1; i++) {
            q.push(q.front());
            q.pop();
        }
    }

    int pop() {
        int x = q.front();
        q.pop();
        return x;
    }

    int top() {
        return q.front();
    }

    bool empty() {
        return q.empty();
    }
};

三、栈的经典题目

1. 括号匹配问题

题目要求判断一个字符串中的括号是否匹配。我们可以使用栈来解决这个问题。

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            if ((c == ')' && top != '(') || 
                (c == ']' && top != '[') || 
                (c == '}' && top != '{')) {
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}

2. 字符串去重问题

题目要求删除字符串中所有相邻的重复字符。我们可以使用栈来解决这个问题。

string removeDuplicates(string s) {
    stack<char> st;
    for (char c : s) {
        if (!st.empty() && st.top() == c) {
            st.pop();
        } else {
            st.push(c);
        }
    }
    string result;
    while (!st.empty()) {
        result += st.top();
        st.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}

3. 逆波兰表达式求值

题目要求计算逆波兰表达式的值。我们可以使用栈来解决这个问题。

int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (string token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (token == "+") st.push(a + b);
            else if (token == "-") st.push(a - b);
            else if (token == "*") st.push(a * b);
            else if (token == "/") st.push(a / b);
        } else {
            st.push(stoi(token));
        }
    }
    return st.top();
}

四、队列的经典题目

1. 滑动窗口最大值

题目要求找出滑动窗口中的最大值。我们可以使用单调队列来解决这个问题。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> result;
    for (int i = 0; i < nums.size(); i++) {
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (dq.front() == i - k) {
            dq.pop_front();
        }
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

2. 求前 K 个高频元素

题目要求找出数组中前 K 个高频元素。我们可以使用优先级队列（堆）来解决这个问题。

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freqMap;
    for (int num : nums) {
        freqMap[num]++;
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (auto& entry : freqMap) {
        pq.push({entry.second, entry.first});
        if (pq.size() > k) {
            pq.pop();
        }
    }

    vector<int> result;
    while (!pq.empty()) {
        result.push_back(pq.top().second);
        pq.pop();
    }
    return result;
}

五、栈与队列的系统应用

1. 编译器中的栈

编译器在词法分析过程中使用栈来处理括号、花括号等符号的匹配问题。

2. 操作系统中的栈

操作系统使用栈来管理函数调用的上下文。每次函数调用时，局部变量、参数值和返回地址都会被压入栈中。

3. 文件路径简化

在Linux系统中，cd 命令的实现依赖于栈。例如，cd a/b/c/../../ 最终会进入 a 目录。

六、总结

栈与队列是计算机科学中不可或缺的数据结构，它们的应用场景非常广泛。通过本文的学习，我们不仅掌握了栈与队列的基本操作，还深入了解了它们在算法设计和系统开发中的实际应用。希望读者能够通过本文的内容，进一步提升自己的编程能力和解决问题的能力。

参考资料

  • 《算法导论》
  • LeetCode 题库
  • C++ 标准模板库（STL）文档

相关题目推荐

  • 20. 有效的括号
    1. 删除字符串中的所有相邻重复项
    1. 逆波兰表达式求值
    1. 滑动窗口最大值
    1. 前 K 个高频元素

下一篇预告

  • 树与图：从基础到高级，掌握树与图的遍历与应用

希望这篇博客对你有所帮助！如果有任何问题或建议，欢迎留言讨论。

site logo

Hi！welcome to DC house

© 2025 dc的house