数据结构与算法实战：栈队列实现与应用解析-开发者社区

1. 数据结构与算法实战：从基础栈队列到经典问题解析

在算法竞赛和编程面试中，栈、队列以及它们的变体是最基础也最常用的数据结构。很多复杂问题都可以通过巧妙运用这些基础结构来解决。本文将带大家从零开始实现基础的栈和队列，逐步深入到括号匹配、后缀表达式计算等经典问题，最后攻克NOIP级别的算法题。

2. 基础数据结构实现

2.1 数组模拟栈的实现

栈是一种LIFO（后进先出）的数据结构，就像一叠盘子，你只能从最上面拿取或放入。用数组模拟栈的关键是维护一个栈顶指针：

const int maxn = 1e6+100; ull a[maxn], cnt; // 栈数组和栈顶指针 void push(ull x) { a[++cnt] = x; // 栈顶指针先+1再存值 } void pop() { if(cnt > 0) cnt--; // 指针下移相当于删除 } ull top() { return a[cnt]; // 访问栈顶元素 }

注意：在实际工程中，应该检查栈是否为空再进行pop或top操作，这里简化为核心逻辑

2.2 数组模拟队列的实现

队列是FIFO（先进先出）结构，就像排队买票。数组模拟队列需要维护队首和队尾两个指针：

const int maxn = 2e6+100; ll a[maxn]; int L = 1e6, R = 1e6-1; // 初始时队尾在队首左侧 void enqueue(ll x) { a[++R] = x; // 队尾右移插入 } void dequeue() { if(L <= R) L++; // 队首右移删除 } ll front() { return a[L]; // 访问队首 }

技巧：将初始指针设置在数组中间可以避免过早的越界问题

3. 栈的经典应用场景

3.1 括号匹配问题

括号匹配是栈的经典应用，算法思路是：

遇到左括号入栈
遇到右括号时检查栈顶是否匹配
最后检查栈是否为空

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

时间复杂度：O(n)，空间复杂度：O(n)

3.2 后缀表达式计算

后缀表达式（逆波兰表示法）不需要括号就能明确运算顺序。计算步骤：

遇到数字入栈
遇到运算符时弹出栈顶两个数运算
将结果压回栈中

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

注意除法和减法的操作数顺序，a和b不能颠倒

4. 队列的高级应用

4.1 滑动窗口最值问题

单调队列可以在O(n)时间内解决滑动窗口最值问题。以最大值为例：

vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; vector<int> res; for(int i = 0; i < nums.size(); ++i) { // 移除超出窗口的元素 if(!dq.empty() && dq.front() == i - k) dq.pop_front(); // 维护单调递减队列 while(!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back(); dq.push_back(i); // 窗口形成后记录结果 if(i >= k - 1) res.push_back(nums[dq.front()]); } return res; }

4.2 单调队列优化DP

单调队列可以优化某些DP问题，如带限制的最大子段和：

int constrainedMaxSum(vector<int>& nums, int k) { deque<int> dq; vector<int> dp(nums.size()); int res = nums[0]; dp[0] = nums[0]; dq.push_back(0); for(int i = 1; i < nums.size(); ++i) { // 移除超出范围的索引 while(!dq.empty() && dq.front() < i - k) dq.pop_front(); dp[i] = max(nums[i], dp[dq.front()] + nums[i]); res = max(res, dp[i]); // 维护单调递减队列 while(!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back(); dq.push_back(i); } return res; }

5. 单调栈的妙用

5.1 下一个更大元素

单调栈可以高效解决"下一个更大元素"类问题：

vector<int> nextGreaterElements(vector<int>& nums) { stack<int> st; vector<int> res(nums.size(), -1); for(int i = 0; i < nums.size(); ++i) { while(!st.empty() && nums[st.top()] < nums[i]) { res[st.top()] = nums[i]; st.pop(); } st.push(i); } return res; }

5.2 柱状图中最大矩形

单调栈解决柱状图最大矩形问题的模板：

int largestRectangleArea(vector<int>& heights) { stack<int> st; heights.push_back(0); // 哨兵 int res = 0; for(int i = 0; i < heights.size(); ++i) { while(!st.empty() && heights[st.top()] > heights[i]) { int h = heights[st.top()]; st.pop(); int w = st.empty() ? i : i - st.top() - 1; res = max(res, h * w); } st.push(i); } return res; }

6. 综合应用：NOIP2011选择客栈

这个问题需要统计满足特定条件的客栈组合数。优化思路是利用前缀和：

int solve(vector<int>& color, vector<int>& cost, int p) { int n = color.size(); vector<int> last(n + 1, -1); // 记录每种颜色上次满足条件的位置 vector<int> cnt(n + 1, 0); // 记录每种颜色的累计满足条件的客栈数 int res = 0, valid_pos = -1; for(int i = 0; i < n; ++i) { if(cost[i] <= p) { valid_pos = i; // 更新最近满足条件的位置 } if(valid_pos >= last[color[i]]) { cnt[color[i]] = 0; // 重置计数 last[color[i]] = i; } res += cnt[color[i]]; cnt[color[i]]++; } return res; }

这个解法的时间复杂度是O(n)，空间复杂度是O(n)，能够高效处理大规模数据。