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

C队列知识全解队列是一种先进先出FIFO的数据结构元素从队尾入队从队头出队。C中可用queue库实现。基本操作push(x)将x加入队尾pop()移除队头元素front()返回队头元素back()返回队尾元素empty()判断队列是否为空size()返回队列元素数量队列例题1用队列实现栈思考过程使用两个队列模拟栈的LIFO特性。主队列存储元素辅助队列用于反转顺序。每次插入新元素时先将新元素加入辅助队列再将主队列元素依次移入辅助队列最后交换两个队列。代码实现#include queue class MyStack { private: queueint 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滑动窗口最大值思考过程使用双端队列维护窗口内元素的递减序列。遍历数组时移除队尾小于当前元素的无效值保证队头始终是当前窗口最大值。同时需处理队头元素超出窗口范围的情况。代码实现vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; vectorint 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) { stackchar 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(vectorstring tokens) { stackint 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, vectorint res) { if (!root) return; inorder(root-left, res); res.push_back(root-val); inorder(root-right, res); } vectorint inorderTraversal(TreeNode* root) { vectorint res; inorder(root, res); return res; }迭代实现vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* 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) { stackTreeNode* 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 queueint q; q.push(1); // 入队 q.pop(); // 出队不返回元素 int front q.front(); // 访问队头 bool isEmpty q.empty(); // 判断空循环队列固定大小的数组实现通过模运算避免数据搬移。应用场景广度优先搜索BFS任务调度如打印机队列C栈知识总结栈是一种后进先出LIFO的数据结构支持在栈顶插入push和删除pop操作。常用实现方式STLstack默认基于deque实现操作示例#include stack stackint 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或红黑树。