C++队列，栈，树的知识全解

C++队列知识全解

队列是一种先进先出（FIFO）的数据结构，元素从队尾入队，从队头出队。C++中可用<queue>库实现。

基本操作：

• push(x)：将x加入队尾
• pop()：移除队头元素
• front()：返回队头元素
• back()：返回队尾元素
• empty()：判断队列是否为空
• size()：返回队列元素数量

队列例题1：用队列实现栈

思考过程：使用两个队列模拟栈的LIFO特性。主队列存储元素，辅助队列用于反转顺序。每次插入新元素时，先将新元素加入辅助队列，再将主队列元素依次移入辅助队列，最后交换两个队列。

代码实现：

#include <queue> class MyStack { private: queue<int> q1, q2; public: void push(int x) { q2.push(x); while (!q1.empty()) { q2.push(q1.front()); q1.pop(); } swap(q1, q2); } int pop() { int val = q1.front(); q1.pop(); return val; } int top() { return q1.front(); } bool empty() { return q1.empty(); } };

队列例题2：滑动窗口最大值

思考过程：使用双端队列维护窗口内元素的递减序列。遍历数组时，移除队尾小于当前元素的无效值，保证队头始终是当前窗口最大值。同时需处理队头元素超出窗口范围的情况。

代码实现：

vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; vector<int> res; 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) res.push_back(nums[dq.front()]); } return res; }

C++栈知识全解

栈是一种后进先出（LIFO）的数据结构，C++中可用<stack>库实现。

基本操作：

• push(x)：压栈
• pop()：弹栈
• top()：返回栈顶元素
• empty()：判断栈是否为空
• size()：返回栈元素数量

栈例题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; if ((c == ')' && st.top() != '(') || (c == '}' && st.top() != '{') || (c == ']' && st.top() != '[')) return false; st.pop(); } } return st.empty(); }

栈例题2：逆波兰表达式求值

思考过程：遇到数字压栈，遇到运算符弹出栈顶两个数字运算后将结果压栈。注意除法向零取整和操作数顺序。

代码实现：

int evalRPN(vector<string>& tokens) { stack<int> st; for (string s : tokens) { if (s.size() > 1 || isdigit(s[0])) { st.push(stoi(s)); } else { 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); } } return st.top(); }

C++树知识全解

树是由节点组成的层次结构，每个节点有零个或多个子节点。二叉树是每个节点最多有两个子树的树结构。

常见术语：

• 根节点：没有父节点的节点
• 叶子节点：没有子节点的节点
• 深度：根到节点的路径长度
• 高度：节点到最深叶子节点的路径长度

树例题1：二叉树的中序遍历

思考过程：递归法：先遍历左子树，访问根节点，再遍历右子树。迭代法：用栈模拟递归过程，沿着左子树深入到底部，然后回溯处理节点。

递归实现：

void inorder(TreeNode* root, vector<int>& res) { if (!root) return; inorder(root->left, res); res.push_back(root->val); inorder(root->right, res); } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; inorder(root, res); return res; }

迭代实现：

vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; while (root || !st.empty()) { while (root) { st.push(root); root = root->left; } root = st.top(); st.pop(); res.push_back(root->val); root = root->right; } return res; }

树例题2：验证二叉搜索树

思考过程：利用BST中序遍历有序的性质，检查当前节点值是否大于前驱节点值。递归法需传递上下界，迭代法则需维护前驱节点指针。

递归实现：

bool isValidBST(TreeNode* root, TreeNode* min = nullptr, TreeNode* max = nullptr) { if (!root) return true; if ((min && root->val <= min->val) || (max && root->val >= max->val)) return false; return isValidBST(root->left, min, root) && isValidBST(root->right, root, max); }

迭代实现：

bool isValidBST(TreeNode* root) { stack<TreeNode*> st; TreeNode* prev = nullptr; while (root || !st.empty()) { while (root) { st.push(root); root = root->left; } root = st.top(); st.pop(); if (prev && root->val <= prev->val) return false; prev = root; root = root->right; } return true; }

C++队列知识总结

队列是一种先进先出（FIFO）的数据结构，支持在队尾插入（enqueue）和队头删除（dequeue）操作。

常用实现方式

• STLqueue：基于其他容器（如deque或list）封装，提供以下操作：

  #include <queue> queue<int> q; q.push(1); // 入队 q.pop(); // 出队（不返回元素） int front = q.front(); // 访问队头 bool isEmpty = q.empty(); // 判断空

• 循环队列：固定大小的数组实现，通过模运算避免数据搬移。

应用场景

• 广度优先搜索（BFS）
• 任务调度（如打印机队列）

C++栈知识总结

栈是一种后进先出（LIFO）的数据结构，支持在栈顶插入（push）和删除（pop）操作。

常用实现方式

• STLstack：默认基于deque实现，操作示例：

  #include <stack> stack<int> s; s.push(1); // 压栈 s.pop(); // 弹栈（不返回元素） int top = s.top(); // 访问栈顶

• 数组模拟：通过变量top记录栈顶位置。

应用场景

• 函数调用栈
• 表达式求值（如括号匹配）

C++树知识总结

树是分层数据的非线性结构，常见类型包括二叉树、二叉搜索树（BST）、AVL树等。

二叉树基本操作

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 前序遍历 void preorder(TreeNode* root) { if (!root) return; cout << root->val << " "; preorder(root->left); preorder(root->right); }

二叉搜索树（BST）特性

• 左子树所有节点值小于根节点，右子树所有节点值大于根节点。
• 中序遍历结果为有序序列。

平衡树（AVL/红黑树）

• 通过旋转保持高度平衡，确保操作时间复杂度为O(log n)。
• STLmap/set基于红黑树实现。

应用场景

• 数据库索引
• 文件系统目录结构

关键区别与选择建议

• 队列 vs 栈：根据FIFO或LIFO需求选择。
• 树的选择：
  • 需要快速查找/插入/删除时用BST；
  • 需严格平衡时用AVL或红黑树。