引入

传说越南河内某间寺院有三根银棒

• 其中一根银棒上串 64 个金盘
• 金盘从上到下，由小至大。
• 一次只移动一片，不管在那根针上
• 但小片必须在大片上
• 从一根银棒按照同样的要求，全部移动到另外一根银棒上，任务完成

若传说属实，僧侣们需要 $2^{64}-1$步才能完成这个任务
若他们每秒可完成一个盘子的移动，就需要 5845 亿年才能完成。整个宇宙现在也不过 137 亿年。

汉诺塔玩具

(图片来自于维基百科)

引入

递归学习过编程的基本上都应该大体知道，但是递归的效率并不高，我们通常使用迭代循环，但我在探索未知的情况下，递归可能会更好。我们通过斐波那契数列来了解一下递归。

斐波那契数列

因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34…
即开始有一对儿兔子，然后3个月后兔子长大了，这对兔子会生一对儿兔子，之后的每个月这对儿兔子又生一对儿，假设兔子不会死亡，那么 N 个月后有多少对儿兔子。

理解

数列：1、1、2、3、5、8、13、21、34…
找到数列的规律之后，我们发现，3号数是1号+2号，6号数是4号+5号，即该数前两个数的和。

迭代循环解题

#include <stdio.h>
int main(){
    int f1=1,f2=1,f3;
    //将第1、2个月的数先赋值，作为计算基底
    printf("%12d\t%12d\t",f1,f2);
    //由于已经赋值了，所以就先输出
    for(int i=3;i<41;i++){
        f3=f1+f2;
        printf("%12d\t",f3);
        //利用循环输出第三个月的数，也就是前两个月的和
        if(i%4==0){
            printf("\n");
        }
        //判断换行
        f1=f2;
        f2=f3;
        //将用于相加的两个数向前推移
    }
}

引入

前面我们讲了，如何初始化一个循环队列，今天我们就来讲讲如何在队列中插入和删除数据。

入队列操作

如何判断队列已经满了

利用取模这个思路判断满栈就是

• 就是让尾指针从头到尾不断的移动
• 利用取模，让尾指针不断的在0~4之间移动
• 如果尾指针指向了头部，也就是说
• 可以插入的位置等于队列的第一个结点的位置了
• 那就证明满栈了

void InsertQueue(struct Queue *q , int e){
    if((q->rear+1)% MAXSIZE==q->front){
        return;
    }
    q->base[q->rear]=e;
    q->rear = (q->rear+1) % MAXSIZE;
}

引入

我们之前说，队列我们一般使用的是链式存储结构，而不是顺序存储结构。我们今天就看看如何构造队列的顺序存储结构，然后看看顺序存储结构给队列带来了哪些问题。

想一想

我们假设，有一个队列

• 有 n 个元素
• 那么顺序存储结构就需要大于 n 的存储单元
• 数组下标 0 是头部，n 个元素存储在数组的前 n 个存储单元中。

（图片来自于鱼 C 工作室）

入队

• 0 号下标是队头
• 然后数据不断进来，不断移动队尾指针。
• 只需要将队尾指针+1即可
• 时间复杂度为 O ( 1 )

引入

我们学习了什么是队列，也了解了队列的一些基本特性，以及如何初始化一个队列，今天我们来看看如何创建和删除以及销毁一个队列。

创建一个队列

创建一个队列要注意以下两点

• 创建一个头结点
• 队列的头指针、尾指针都指向该结点
• 因为队列是空的，这样就创建完成了

#include <stdio.h>
#include <stdlib.h>
#define sizeof(struct Queue)

struct Queue{
int data;
struct Queue *next;
};

struct Queue_link{
struct Queue *front;
struct Queue *rear;
}

void init(Queue_link *q){
q->frout=q->rear=(struct Queue *)malloc(LEN);
if(!q->front){
exit(0);
}
q->frount->next=NULL;
}

引入

介绍完栈的各种定义，今天我们来介绍一下队列。我们常常会把栈和队列放在一起讲，因为它们有相似的地方，也有所不同，我们今天来看看什么是队列，以及如何初始化一个队列。

栈和队列

队列嘛，我们就可以想象成排队

• 先来的排在前面，后来的排在后面
• 不能插队，因为要讲究先来后到
• 所以先来的先出队，后来的排在队尾

理解了上面的例子，要理解栈和队列，那就简单了

• **栈：**后进先出，只能在顶端进行插入和删除，也就是压栈和出栈
• **队列：**先进先出，队列只能在尾部出，头部入队。

队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

• **与栈相反：**队列是先进先出（First In First Out），简称为FIFO 的线性表。
• **与栈相同：**队列也是一种重要的线性结构，实现一个队列同样需要顺序表或链表作为基础。

引入

在20世纪30年代，波兰逻辑学家扬·卢卡西维茨（Jan Łukasiewicz）,发明了一种将所有操作符置于操作数的后面，因此也被称为后缀表示法。我们称之为逆波兰记法。逆波兰记法不需要括号来标识操作符的优先级。

逆波兰表示法

上面的引入感觉很高大上，我们来个例题，对于解

$(1-2)\times (4+5)$

连小朋友都知道，先算括号里面的，再算括号外面的，最后结果相乘。
如果计算机来解题的话，就会用很多 if…else… 进行判断，显然对于我们人类方便的括号优先级表达法，对计算机不那么友好。
那么能不能对计算机友好一点？逆波兰表达式出现了，对于上面的问题：

普通式为：$(1-2)\times (4+5)$
逆波兰表达式为：$12-45\times$

基本的转换方法如下

• 所有数字从左到右写，位置不用动
• 遇到括号，先写出括号内的数字
• 然后在数字后面，以先乘除后加减的方式写出括号内的运算符
• 然后继续写数字，直到所有数字写完
• 然后在数字后面，以先乘除后加减的方式写出剩余的运算符

引入

我们之前，讲解了栈的顺序存储结构，那么既然是线性表，如何用链式存储结构来使用栈呢？链式存储和顺序存储在栈中又会有什么不一样呢？我们一起来看一下~

想一想

我们在开始之前先想一想，栈和链式存储结构的特点
链式存储结构

• 有头部
• 根据头部存储的指针信息，一环扣一环

顺序存储结构的栈

• 后进先出
• 插入和删除只能在顶端进行

链式存储结构的栈呢

• 有头部
• 每个结点存储着指针信息，一环扣一环
• 后进先出
• 插入和删除只能再顶端进行

引入

我们学习了栈的基本操作，今天我们就看看，栈能为我们做哪些服务，以及如何灵活的使用栈的这些特性。我们就从二进制数转换为十进制数的例子说起。

方法

首先，我们先说明一下二进制转十进制的公式

公式 $n\times 2^{n-1}$

N 表示二进制的从右向左的位数，然后把所有位的和相加，就是十进制结果。

演示
二进制数：$100101$
第 1 位：$1 \times 2^{1-1}=1 \times 1=1$
第 2 位：$0 \times 2^{2-1}=0 \times 2=0$
第 3 位：$1 \times 2^{3-1}=1 \times 4=4$
第 4 位：$0 \times 2^{4-1}=0 \times 8=0$
第 5 位：$0 \times 2^{5-1}=0 \times 16=0$
第 6 位：$1 \times 2^{6-1}=1 \times 32=32$
结果是：$1+0+4+0+0+32=37$
其实就是计算非零数相加。

引入

我们学习了栈的初始化、压栈、出栈，今天我们来看看如何清空和销毁一个栈。

清空栈

也就是将栈内的元素全部删除，但栈本身的物理空间，即内存地址是不会发生改变的。这个和销毁是有很大区别的。那么该如何清空呢？

• 将 s->top 赋值为 s->base 即可，也就是让顶部和底部相等。
• 可以这么理解，数据还在那，找数据的地址全没了。
• 新数据写入的时候，会覆盖掉原来这个地址的数据。

代码实现

非常简单

ClaerStack( sqstack *s ){
s->top=s->base;   //让顶部等于底部
}