第2章 算法知识、栈、队列
2.1 算法知识
算法是对特定问题求解步骤的描述，算法有 5 个重要特征。
（1）有穷性：对于任意一组合法的输入，算法能在有限的时间内完成。
（2）确定性：算法的每一步有明确的定义，没有歧义。
（3）输入：算法应有 0 个或多个输入。（一般 0 个输入指的是有些算法的输入是嵌入到
算法之中的）
（4）输出：算法应有 1 个或者多个输出。
（5）可行性：算法必须遵循特定条件下的解题规则，算法描述的操作都应该是特定规
则中允许使用的、可执行的，并通过执行有限次来实现。
常见的算法有：穷举、高精度计算、排序、递推、递归、贪心、分治、搜索、动态规划
等。
1、算法复杂度
影响程序运行时间的因素：
（1）计算机的计算速度； （2）计算数据的大小； （3）算法的效率；
一个算法的评价一般从时间复杂度和空间复杂度来考虑。
时间复杂度：指算法所需要的计算工作量，用算法所执行的基本运算次数来度量。常见 的时间复杂度有：常数阶 O(1)，对数阶 O(log2n)，线性阶 O(n)，线性对数阶 O(n* log2n)，
平方阶 O(n2)，立方阶 O(n3)，指数阶 O(2n)等，上述时间复杂度随着问题规模 n 的增加，时 间复杂度不断增加，算法效率降低。
时间复杂度的计算步骤：
求解算法的时间复杂度的具体步骤是：
1、找出算法中的基本语句：
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
2、计算基本语句的执行次数的数量级：
（1）只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的
函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。
（2）这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
3、用大Ο记号表示算法的时间性能：
（1）将基本语句执行次数的数量级放入大Ο记号中。
（2）如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包
含并列的循环，则将并列循环的时间复杂度相加。例如：
for(i=1;i<=n;i++) x++;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++) x++;
}
第一个 for 循环的时间复杂度为Ο(n)，第二个 for 循环的时间复杂度为Ο(n2)，则整
个算法的时间复杂度为Ο(n+n2)=Ο(n2)。
下面按从快到慢的顺序列出了你经常会遇到的 5 种大 O 运行时间。（时间复杂度只需要
计算到对应的数量级，不需要计算到具体的值）
（1）O(log n)，也叫对数时间，这样的算法包括二分查找。
（2）O(n)，也叫线性时间，这样的算法包括简单查找。
（3）O(n * log n)，这样的算法包括快速排序——一种速度较快的排序算法。
（4）O(n
2)，这样的算法包括第选择排序、冒泡排序——一种速度较慢的排序算法。
（5）O(n!)，这种情况很少见，n越大，所消耗的时间就越慢。
大 O 表示法是一种特殊的表示法，指出了算法的速度有多快。例如，假设列表包含 n 个
元素。简单查找需要检查每个元素，因此需要执行 n 次操作，这个运行时间为 O(n)。
一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的
运行时间不会比任何其他情况更长。
空间复杂度：指执行这个算法所需要的内存空间。
2、常见算法的算法复杂度
（1）查找算法
查找策略 时间复杂度 备注
顺序查找 O(n)
二分查找 O(log2n) 要求数列有序
插值查找 O(log2n) 要求数列有序且相对均匀
（2）排序算法
排序 算法复杂度
冒泡排序 O(n2)
直接插入 O(n2)
快速排序、堆排序、归并排序 O(nlog2n)
选择排序 O(n2)
桶排序 O(n)
【NOIP2018普及组】8.以下排序算法中，不需要进行关键字比较操作的算法是（ ）。
A. 基数排序 B. 冒泡排序
C. 堆排序 D. 直接插入排序
答案：A
解析：基数排序，根据键值的每位数字来分配桶；
冒泡排序、堆排序和插入排序都是基于两两元素关键字比较的排序。基数排序是直接将元
素通过某些规则放到数组的相应位置，不是基于两两元素关键字比较的排序。
【NOIP2018 提高组】5. 设某算法的时间复杂度函数的递推方程是 T(n) = T(n - 1) + n
（n 为正整数）及 T(0) = 1，则该算法的时间复杂度为（ ）。
A. O(log n) B. O(n log n) C. O(n) D. O(n2 )
答案：D
解析：
T(n) = T(n - 1) + n
= T(n - 2) + (n - 1) + n
= T(n - 3) + (n - 2) + (n - 1) + n
= T(1) + 2 + …… + (n - 2) + (n - 1) + n
= T(0) + 1 + 2 + …… + (n - 2) + (n - 1) + n
= 1 + n*(n + 1) / 2 = n2 / 2 + n / 2 + 1
2.2 什么是数据结构？
1、数据结构的定义
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定
关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效
率。
如：数组。
2、数组有什么特点？
（1）数组(array)的元素(element)或项(item) 的类型是相同的
（2）数组对某元素的存取是 O(1)时间
（3）数组的插入、删除操作是 O(n)时间
由于数组通常的插入、删除操作是 O(n)时间的，在某些特定的条件下就显得低效了。
因此我们通过对数组元素操作的限制，来达到操作的高效---算法优化的突破点。
常见的“订制”数组有：栈、队列、堆等，它们操作的时候效率都很高。
注 ：虽然栈、队列、堆可以不用数组实现，但 NOIP 的实践中，用数组实现更简单实用。
2.3 栈（Stack）
1、栈的特点
（1）栈(stack)是后进先出(last-in-first-out,LIFO)或先进后出(FILO)的
（2）栈有三个基础操作压入(push),弹出(pop),取数(getTop)操作都为O(1)时间
（3）栈有一个计数器 counter 或栈顶指针
2、栈的基本操作
（1）建栈（init）：在使用栈之前，首先需要建立一个空栈，称建栈；
（2）压栈（push）：往栈顶加入一个新元素，称进栈（压栈）；
（3）出栈（pop）：删除栈顶元素，称出栈（退栈、弹出）；
（4）取栈顶（gettop）：查看当前的栈顶元素，称读栈；
（5）测试栈（empty）在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试
栈；
（6）显示栈（display）：输出栈的所有元素；
（7）释放栈（setnull）：清空栈；
3、栈的操作代码
初始化、入栈、出栈、显示栈！
#include <iostream> //常量：栈的长度
#define MAXN 5
using namespace std;
int stack[MAXN];//数组模拟栈
int top = -1;//初始化栈指针
//出栈
int pop(){
int r;
if(top < 0){
r = -1;
cout<<"栈空！"<<endl; }else{
r = stack[top];
top--;
}
return r; }
//入栈
void push(int value){
if(top >= MAXN - 1){
cout<<"栈满"<<endl; }else{
top++;
stack[top] = value;
}
}
//显示栈
void display(){
int i;
for(i = top;i >= 0;i--){
cout<<stack[i]<<" "; }
cout<<endl;
}
int main(){
int order;//指令 int x,t; cout<<"输入指令："; while(1 == 1){
cout<<"1:入栈,2:出栈,3:显示栈!"<<endl; cin>>order; if(order == 1){
cin>>x; push(x); display();
}else if(order == 2){
t = pop(); if(t != -1){
cout<<t<<"出栈!"<<endl; display();
}
}else if(order == 3){
display(); }
}
return 0;
}
4、栈的练习题
【noip2015 普及组】15. 今有一空栈 S，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次
进行进栈，进栈，出栈，进栈，进 栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为
（ ）
A. f B. c C. a D. b
答案：B
解析：画一个栈，按照题目所描述的操作模拟一遍。
【noip2017 提高组】2. 对于入栈顺序为 a, b, c, d, e, f, g 的序列，下列( )不可能
是合法的出栈序列。【不定项选择题】
A. a,b,c,d,e,f,g B. a,d,c,b,e,g,f C. a,d,b,c,g,f,e D.g,f,e,d,c,b,a
答案：C
解析：画一个栈，逐个选项判断模拟是否可行。
【noip2012普及组】18．在程序运行过程中，如果递归调用的层数过多，会因为（ ）引
发错误。
A．系统分配的栈空间溢出 B．系统分配的堆空间溢出
C．系统分配的队列空间溢出 D．系统分配的链表空间溢出
答案：A
解析：递归是用栈这种数据结构来实现的。
执行时，外层的函数先进栈，内层的函数后进栈。内层的函数把结果返回给外层的函数并出
栈。
【noip2010 普及组】15．元素 R1、R2、R3、R4、R5 入栈的顺序为 R1、R2、R3、R4、R5。如
果第一个出栈的是 R3，那么第五个出栈的不可能是（ ）。
A．R1 B．R2 C．R4 D．R5
答案：B
答案：C
解析：画一个栈，逐个选项判断模拟是否可行。
2.4 队列
1、什么是队列？
队列就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，
通常用一个队尾指针 r 指向队尾元素，即 r 总是指向最后被插入的元素；允许删除的一端称
为队首，通常也用一个队首指针 f 指向排头元素的前面。初始时 f=r=0。
举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。
举例 2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。
结论：在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素
将最后被删除，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。
2、队列的基本操作
（1）新建队列
（2）入队
（3）出队
（4）判断队列是否为空
（5）判断队列是否为满
（6）显示队列元素