网站截图环境 php网站导航网站开发

网站截图环境 php,网站导航网站开发,WordPress简约资讯主题,一个网上商城多少钱stack(栈) stack的基本介绍 栈#xff08;Stack#xff09;是一种后进先出#xff08;LIFO#xff09;的线性数据结构#xff0c;只能在容器的一端#xff08;称为栈顶#xff09;进行插入和删除操作。 **核心特性 仅允许在栈顶插入和删除元素不支持随机访问没有迭代器Stack是一种后进先出LIFO的线性数据结构只能在容器的一端称为栈顶进行插入和删除操作。**核心特性仅允许在栈顶插入和删除元素不支持随机访问没有迭代器只能访问栈顶元素templateclassT,classContainerdequeTclassstack;stack的常用接口函数声明功能说明stack()构造空栈empty()检测栈是否为空size()返回栈中元素个数top()返回栈顶元素的引用push(val)将元素val压入栈顶pop()弹出栈顶元素stack的模拟实现templateclassT,classContainerdequeTclassStack{private:Container _con;// 底层容器public:Stack()default;voidpush(constTval){_con.push_back(val);// 尾部作为栈顶}voidpop(){_con.pop_back();}Ttop(){return_con.back();}constTtop()const{return_con.back();}boolempty()const{return_con.empty();}size_tsize()const{return_con.size();}};queue队列queue的基本介绍**队列Queue是一种先进先出FIFO**的线性数据结构允许在队尾插入元素在队头删除元素。templateclassT,classContainerdequeTclassqueue;queue的常用接口函数声明功能说明queue()构造空队列empty()检测队列是否为空size()返回队列中元素个数front()返回队头元素的引用back()返回队尾元素的引用push(val)在队尾插入元素valpop()删除队头元素queue的模拟实现templateclassT,classContainerdequeTclassQueue{private:Container _con;public:Queue()default;voidpush(constTval){_con.push_back(val);}voidpop(){_con.pop_front();// 需要底层支持pop_front}Tfront(){return_con.front();}Tback(){return_con.back();}boolempty()const{return_con.empty();}size_tsize()const{return_con.size();}};priority_queue的基本介绍优先队列Priority Queue是一种特殊的队列其中的元素按照优先级排序。默认情况下优先级最高的元素最大堆总是在队头。templateclassT,classContainervectorT,classComparelesstypenameContainer::value_typeclasspriority_queue;核心特性底层通常使用**堆heap**实现默认是大根堆最大元素在顶部支持插入和删除最大/最小元素的操作O(log n)支持查看堆顶元素O(1)priority_queue的基本用法// 默认大根堆priority_queueintmaxHeap;// 小根堆priority_queueint,vectorint,greaterintminHeap;// 使用数组初始化vectorintnums{3,1,4,1,5,9};priority_queueintpq(nums.begin(),nums.end());priority_queue的模拟实现templateclassT,classContainervectorT,classComparelessTclassPriorityQueue{private:Container _con;Compare _comp;// 向上调整用于插入voidshiftUp(intidx){while(idx0){intparent(idx-1)/2;if(!_comp(_con[parent],_con[idx]))break;swap(_con[parent],_con[idx]);idxparent;}}// 向下调整用于删除voidshiftDown(intidx){intsize_con.size();while(idx*21size){intchildidx*21;if(child1size_comp(_con[child],_con[child1])){child;}if(!_comp(_con[idx],_con[child]))break;swap(_con[idx],_con[child]);idxchild;}}public:PriorityQueue()default;voidpush(constTval){_con.push_back(val);shiftUp(_con.size()-1);}voidpop(){if(empty())return;_con[0]_con.back();_con.pop_back();if(!empty())shiftDown(0);}constTtop()const{return_con.front();}boolempty()const{return_con.empty();}size_tsize()const{return_con.size();}};注释版/** * 优先队列堆模板类 * tparam T 元素类型 * tparam Container 底层容器类型默认为vectorT * tparam Compare 比较器类型默认为lessT最大堆 */templateclassT,classContainervectorT,classComparelessTclassPriorityQueue{private:Container _con;// 底层容器通常为数组Compare _comp;// 比较函数对象/** * 向上调整堆化 - 用于插入新元素后维护堆性质 * param idx 需要向上调整的节点索引 * 时间复杂度O(log n) */voidshiftUp(intidx){// 从当前节点开始向上遍历直到根节点while(idx0){intparent(idx-1)/2;// 计算父节点索引// 如果当前节点不比父节点优先则停止调整if(!_comp(_con[parent],_con[idx]))break;// 交换父子节点swap(_con[parent],_con[idx]);idxparent;// 继续向上检查}}/** * 向下调整堆化 - 用于删除堆顶后维护堆性质 * param idx 需要向下调整的节点索引 * 时间复杂度O(log n) */voidshiftDown(intidx){intsize_con.size();// 当当前节点至少有一个子节点时继续调整while(idx*21size){intchildidx*21;// 左子节点索引// 如果存在右子节点且右子节点比左子节点更优先if(child1size_comp(_con[child],_con[child1])){child;// 选择更优先的子节点}// 如果当前节点比子节点优先则停止调整if(!_comp(_con[idx],_con[child]))break;// 交换父子节点swap(_con[idx],_con[child]);idxchild;// 继续向下检查}}public:// 默认构造函数PriorityQueue()default;/** * 插入元素到优先队列 * param val 要插入的值 * 步骤1. 添加到末尾 2. 向上调整恢复堆性质 */voidpush(constTval){_con.push_back(val);// 在末尾添加新元素shiftUp(_con.size()-1);// 从新元素位置开始向上调整}/** * 移除堆顶元素优先级最高的元素 * 步骤1. 用末尾元素替换堆顶 2. 删除末尾 3. 向下调整恢复堆性质 */voidpop(){if(empty())return;// 空队列检查_con[0]_con.back();// 用最后一个元素覆盖堆顶_con.pop_back();// 删除最后一个元素if(!empty())shiftDown(0);// 从堆顶开始向下调整}/** * 获取堆顶元素优先级最高的元素 * return 堆顶元素的常量引用 * 注意调用前需确保队列非空 */constTtop()const{return_con.front();// 堆顶位于容器首部}/** * 检查优先队列是否为空 * return bool 队列为空返回true */boolempty()const{return_con.empty();}/** * 获取优先队列中元素数量 * return size_t 元素个数 */size_tsize()const{return_con.size();}};// 使用示例说明// PriorityQueueint pq; // 最大堆默认// PriorityQueueint, vectorint, greaterint min_pq; // 最小堆容器适配器**适配器Adapter**是一种设计模式它将一个类的接口转换成客户期望的另一个接口。STL中的容器适配器是在现有容器的基础上封装新的接口。STL中的容器适配器适配器底层容器要求默认容器特性stack支持push_back(),pop_back(),back()dequeLIFOqueue支持push_back(),pop_front(),front(),back()dequeFIFOpriority_queue支持随机访问迭代器、push_back(),pop_back(),front()vector优先队列deque双端队列deque的结构原理**dequeDouble-ended Queue**是一个双开口的连续空间数据结构支持在头部和尾部高效插入/删除O(1)实际是分段连续空间动态二维数组通过**中控器map**管理多个固定大小的缓冲区deque的底层结构中控器map[ptr0]-[缓冲区0:012][ptr1]-[缓冲区1:345][ptr2]-[缓冲区2:678]...迭代器设计deque迭代器需要维护:当前元素位置当前缓冲区指针缓冲区边界信息deque的优缺点分析优点头尾插入删除高效O(1)时间复杂度空间利用率较高比list连续无需额外指针开销扩容代价较低无需像vector一样整体搬移缺点遍历效率低需要频繁检查缓冲区边界随机访问较慢需要计算定位到具体缓冲区中间插入删除效率低需要移动元素deque作为默认容器的原因// STL中的默认定义templateclassT,classContainerdequeTclassstack;templateclassT,classContainerdequeTclassqueue;选择deque的原因对于stack只需要尾插尾删deque效率高比vector扩容代价小比list空间利用率高对于queue需要头删尾插deque在两端操作都是O(1)vector不支持高效的头删list空间开销大综合优势避免了vector的大规模数据搬移避免了list的额外指针开销完美适配stack和queue的操作需求容器选择总结数据结构适用场景时间复杂度注意事项stack括号匹配、函数调用栈、DFS、表达式求值插入/删除O(1)访问O(1)只能访问栈顶元素queueBFS、任务调度、缓冲区、消息队列插入/删除O(1)访问O(1)只能访问队头队尾priority_queue任务调度、TopK问题、Dijkstra算法插入/删除O(log n)访问O(1)只能访问堆顶元素deque需要两端操作的场景头尾操作O(1)随机访问O(1)遍历效率较低// 根据需求自定义底层容器// 1. 如果需要频繁遍历stackint,vectorintst1;// 使用vectorqueueint,listintq1;// 使用list// 2. 如果对内存敏感stackint,listintst2;// 无扩容问题queueint,dequeintq2;// 折中方案// 3. 如果对性能要求极高stackint,dequeintst3;// 默认最优queueint,dequeintq3;// 默认最优// 4. priority_queue的特殊需求priority_queueint,vectorintpq1;// 默认随机访问快priority_queueint,dequeintpq2;// 扩容代价小