引入
我们学习了什么是队列,也了解了队列的一些基本特性,以及如何初始化一个队列,今天我们来看看如何创建和删除以及销毁一个队列。
创建一个队列
创建一个队列要注意以下两点
- 创建一个头结点
- 队列的头指针、尾指针都指向该结点
- 因为队列是空的,这样就创建完成了
1 |
|
高树靡阴,独木不林。
我们学习了什么是队列,也了解了队列的一些基本特性,以及如何初始化一个队列,今天我们来看看如何创建和删除以及销毁一个队列。
创建一个队列要注意以下两点
1 | #include <stdio.h> |
介绍完栈的各种定义,今天我们来介绍一下队列。我们常常会把栈和队列放在一起讲,因为它们有相似的地方,也有所不同,我们今天来看看什么是队列,以及如何初始化一个队列。
队列嘛,我们就可以想象成排队
理解了上面的例子,要理解栈和队列,那就简单了
队列
(queue)是只允许在一端进行插入
操作,而在另一端进行删除
操作的线性表
。
需要顺序表或链表作为基础。
在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$
其实就是计算非零数相加。
我们学习了栈的初始化、压栈、出栈,今天我们来看看如何清空和销毁一个栈。
也就是将栈内的元素全部删除,但栈本身的物理空间,即内存地址是不会发生改变的。这个和销毁是有很大区别的。那么该如何清空呢?
非常简单1
2
3ClaerStack( sqstack *s ){
s->top=s->base; //让顶部等于底部
}
上一节,我们了解了栈的基本信息,知道了栈的各种特性,并且试着初始化了一个空栈。今天我们就来看看,如何将数据存入栈中。
入栈,我们有称之为压栈,简单来说就是向栈中存放数据。
入栈从栈顶
进行。1 | #define StackSize 100 //首先设置一个容量 |
今天,我们开始讲一种特殊的线性表,栈。既然是特殊的线性表,那么有哪些不一样的呢?我们一起来看看!
下面的图片是一个弹夹
我们知道,如果子弹没有了,那么我们需要一颗一个的将子弹装入弹夹
也就是说,最后被装入的子弹,最先被发射出去。我们将这种情况称之为后进先出
。
前面我们简单了解了一下双链表,以及在插入和删除时的一些变化。这一节,我们就跟着一个凯撒密码,来看看双循环链表的初始化、插入、操作结点等过程。
凯撒密码是一种代换密码。据说凯撒是率先使用加密函的古代将领之一,因此这种加密方法被称为凯撒密码。他的基本思想是
有26个英文字母,我们需要设计一个程序
我们介绍了单链表、介绍了将单链表头尾相连组成循环链表,又讲了循环链表中一些有趣得应用,现在是时候了解线性表中的大拿,双循环链表了。
在单循环链表中,链表中的各个节点是这样的,一个结点指向下一个结点
A -> B -> C -> D -> E -> F
如果我们需要从 A 到达 D 结点,那么需要
A -> B -> C -> D
如果到了 D 之后,有需要到 C,那么就麻烦了
D -> E -> F -> A -> B -> C
明明相邻得两个结点,为什么要转一圈才能找到彼此呢?
答案很简单,因为结点都是向后指的,单循环链表嘛~
而解决这个问题的答案更简单,那我们就把结点
既指向它的前驱节点,也指向它的后继节点不就好了~
这就是双向链表
。