1. Queue 在 C++ 编程世界里，标准模板库（STL）宛如一座宝库，为开发者们提供了丰富且强大的数据结构与算法工具。其中，queue 作为一种特殊的数据结构，在众多场景中扮演着不可或缺的角色。本文将深入剖析 queue 的特性、底层实现、操作方法以及应用场景，帮助读者全面掌握这一重要工具。 1.1 概述 queue，即队列，是一种遵循先进先…

1. Stack 1.1 基础概念 在计算机科学领域，stack（栈）是一种极为重要的数据结构，遵循 “先进后出（First In Last Out，FIFO）” 原则。形象地说，它就像一个只有一端开口的容器，你从开口处放入物品，最后放入的物品总是最先被取出。在 C++ 的 STL 中，stack 被实现为一个容器适配器。所谓容器适配器，是对其他容…

List List是一个能够存放任意性别的双向链表（doubly linked list) 可以向List中介入一个子链表 为了使用List，必须用include指令包含如下文件，并通过std命名空间去访问： #include <list> int main() { std::list l; } List 的优势 List 的优势在于其…

条款 41：了解隐式接口和编译期多态。 描述引入template带来的变化，在template世界中，多态会前移到编译阶段。 请记住 classes和templates都支持接口和多态。 对classes而言接口是显示的，以函数签名为中心。多态则是通过virtual函数发生于运行期。 对template参数而言，接口是隐式的，奠基于有效表达式。多态…

  减治法(reduce and conquer method)同样是把一个大问题划分为若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解进行合并。所以，严格地说，减治法应该是一种退化了的分治法。应用减治法技术设计的算法通常具有很高的效率，一般来说其时间复杂性是$O(log_2n)$。 …

  回溯法(back trace method)是一种有组织的系统化搜索技术，可以看作是蛮力法穷举搜索的改进。蛮力法穷举搜索首先生成问题的可能解，然后再去评估可能解是否满足约束条件。而回溯法每次只构造可能解的一部分，然后评估这个部分解，如果这个部分解有可能导致一个完整解，对其进一步构造，否则，就不必继续构造这个部分解了。回溯法常…

  分治者，分而治之也（感觉有点废话）。分治法（divide and conquer method)是最著名的算法设计技术，作为解决问题的一般性策略，分治法在政治和军事领域也是克敌制胜的法宝。 概述   分冶法的设计思想是将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地…

  贪心法(greedy method)是一个把复杂问题分解为一系列较为简单的局部最优选择，每一步选择都是相对于当前解的一个扩展，直到获得问题的完整解。贪心法的典型应用是求解最优化问题，而且对许多问题都能得到整体最优解，即使不能得到整体最优解，通常也是最优解的很好近似。 概述 贪心法的设计思想   贪心法在解…

  蛮力法(brute force method)，也称穷举法，是一种简单而直接地解决问题的方法，常常直接基于问题的描述，因此，也是最容易应用的方法。 蛮力法的设计思想   满立法所依赖的技术是扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解。依次处理所有元素是蛮力法的关键，为了…

[TOC] 下界   对于任何待求解的问题，如果能找到一个尽可能大的函数g(n)(n为问题规模)，使得求解该问题的所有算法都可以在$\Omega(g(n))$的时间内完成，则称函数g(n)为该问题计算复杂性的下界(lower bound)。如果已经知道一个和下界的效率类型相同的算法，则称该下界是紧密(close)的。 平凡下界 …