单调栈

顾名思义, 单调栈就是其元素单调的栈, 满足两个特性:

union 改名操作

比如以下这个类，我期望外部不仅能通过P1这个名字访问P1这个成员变量，也能通过Y/R等名字访问他的P1。

问题

先来看一段代码:

问题

先来看一个问题:

一维链表

链表不需要一块很大的连续的存储空间是其优点, 但是对一串有序序列, 使用一维链表查询的时间复杂度是$O(n)$, 能否如查找二叉树之类, 将其查找时间复杂度降为$O(logn)$呢?

堆的结构

同二叉查找树类似, 堆也是一种特殊的二叉树:

平衡树

对于一个普通的二叉查找树, 我们可以发现一个问题, 存在一定的可能性, 一般的二叉查找树会退化成一般的链表.

什么是二叉查找树

对一般容器的查找, 我们可以按顺序遍历, 找到符合要求的元素就返回; 对于元素是有序的容器, 可以使用二分查找等方法查找, 减少操作的时间复杂度.

容易知道, 一般查找的平均时间复杂度是O(n), 二分查找的平均时间复杂度是O(logn).

stdarg.h

这里用到的是stdarg.h这个库, 可以在C语言里面实现可变长参数.

当然C++会简单得多, C++11之后的模板原生支持可变长参数.

几个函数va_list、va_start、va_arg、va_end，定义在stdarg.h

问题

先看以下代码