栈和队列
1,栈(stack)
栈是限定仅在表尾进行插入或者删除操作的线性表
栈 :线性表
->
一对一的关系
-》
数组
链表
栈是有限制的线性表(阉割版的线性表)
栈更重要的是一种思想
先进后出,后进先出
在程序设计或算法中,会经常用到这种思想
“撸串”
“死胡同堵车”
“压子弹”
栈顶(top):进行插入或者删除的那一端
栈尾(bottom):不允许进行插入或者删除的一端
栈的基本操作:
类型的实现
数组
链表
操作的实现
常用的操作
initStack:初始化栈
clearStack :清空栈 -》把栈的所有元素都干掉
destroyStack:销毁一个栈
pop:出栈
push:入栈(压栈)
不是很常用的操作
getTop:获取栈顶元素,但是不出栈
stackIsEmtpy:判断栈是否为空
stackLength:栈的长度
(1)顺序栈:用顺序结构的线性表来实现栈
顺序结构的线性表 -》 数组
栈顶和栈尾分别对应数组的哪一端比较好?
栈顶是经常要进行插入或者删除的,那么怎么方便你就怎么选
经过分析:选择a[n-1]这端做完栈顶,a[0]端作为栈尾
-》
typedef int ElemType;//栈元素的类型
#define MAX_ELEM_NUM 100
struct sqStack
{
ElemType stack[MAX_ELEM_NUM];//用来保存数据
int top;//栈顶元素在stack中的下标
}
typedef struct sqStack STACK;
(2)链式栈:用链式的线性表来实现栈
链式的线性表 -> 链表
typedef int ElemType;
struct node //定义了一个新的类型,叫做 struct node
{
ElemType data;//存储数据 -》数据域
struct node * next;//存储下一个元素的地址,因为下一个
//元素和当前元素是一个类型,所以他的类型是
//struct node * next ->指针域
};
typedef struct node NODE;//给struct node取一个别名NODE
struct stack //<-这是我们声明的新类型 “头结点”
{
//这个头结点的成员变量,不是确定的,是按你的需求增加
//你觉得这个链表中,哪些信息对你比较重要或者经常用到
//你就保存它
int nodeNum;//用来保存链表中的节点的个数
NODE * first;//指向栈顶元素
NODE * last;//指向栈尾元素
//.......按需增加
};
typedef struct stack STACK;
first和last哪端作为栈顶比较好?
对于插入而言:头插和尾插都很方便
对于删除而言:删除first和删除last哪个方便?
删除first比较简单
->
采用first作为栈的栈顶
作业:
输入一个整数,然后倒序输出这个整数的各位数字,用栈实现
12345
->
5 4 3 2 1
设输入序列1、2、3、4,则下述序列中()不可能是出栈序列。
A. 1、2、3、4 B. 4、 3、2、1
C. 1、3、4、2 D.4、1、2、3
1、若入栈序列是 a, b, c, d, e,则不可能的出栈序列是()。
(A) edcba(B)decba(C)dceab (D)abcde
2, 队列
队列(Queue)是一种先进先出,后进后出的线性表。
它只允许在表的一端进行插入,在另一端进行删除。
队尾:允许插入的一端叫做队尾
对头:允许删除的一端叫队头
“排队”
队列更重要的是一种思想,“先进先出”
队列的实现
队列类型的实现
(1)顺序队列:用顺序结构的线性表来实现队列
“环形数组”
开辟一段连续的地址空间用来保存队列中的每一个元素 Q[]
定义两个变量,保存两个重要的信息:
1,d :队头元素的下标(打饭的阿姨的位置)
2,e : 下一个入队元素的下标
(下一位打饭的同学要加入的位置,其实就是当前队列队尾的下一个)
typedef int ElemType;//队列元素的类型
#define QUEUE_MAX_NUM 100
typedef struct SqQueue
{
ElemType queue[QUEUE_MAX_NUM];
int d;//队头下标
int e;//下一个队尾的下标
int num;//队列中元素的个数(当前排队的人数)
}SqQueue;
(2)链式队列:用链式结构的线性表来实现队列
链表
"带头结点的单向链表"
typedef int ElemType;//队列的元素
struct node
{
ElemType data;
struct node * next;
}
typedef struct node NODE;
typedef struct LkQueue
{
NODE * first;//指向队头元素
NODE * last;//指向队尾
int num;//队列中元素的个数
}LkQueue;
first指向队头,last指向队尾。因为队头要删除节点,作为单向链表而言,last作为对头的话,极不方便
设计好,实现起来就会轻松
设计不好,很麻烦
操作的实现
initQueue:初始化队列
clearQueue:清空一个队列
destroyQueue:销毁一个队列
EnQueue:入队
DeQueue:出队
getHead:返回队头元素
queueIsEmpty:是否为空
queueLength:返回队列元素的个数,即队列的长度
-----------------------------------------------------------
我们知道,线性表(链表,栈和队列),都是一个具有相同属性的数据
的集合。
集合中的元素:必须要是同一类型的?是的
那如果我需要用线性表保存不同类型的集合,是不是
就得写多份代码
现在一个项目中,既需要用到保存Int型数据的链表
又需要用到保存char型数据的链表
还需要用到保存double型数据的链表
也就是说需要三个或者多个不同类型的链表
那么是不是得把同一个代码写多份,才能满足
int double char ......
共同点?
我们可以保存他们的地址,因为他们的地址都是四个字节
作业:
求表达式的值
表达式是以字符串的形式输入
如:
char a[100] = "3+2*8-4*3+5-6+7/2+10-5";
//不考虑括号,运算符只考虑 ,所有的操作数都是int
1,创建两个栈s1 ,s2
s1 存操作数的栈
s2 存运算符的栈
2,按照要求把这个表达式的操作数和运算符入栈
flag 第一个操作数和第一个运算符直接入栈
后面的操作数x怎么处理呢?分两种情况
s2的栈顶元素c2与x的后面的运算符c1做比较(比较优先级)
如果c2<c1 :x直接入栈
如果c2>=c1:则计算 y c2 x的值 -》当做新的x
(y是s1的出栈元素,c2是s2的出栈元素,y和c2都需要出栈)
goto flag (循环什么时候结束?字符串入栈完毕)
3,把s1,s2出栈
进行运算 -》结果
标签:struct,队列,元素,链表,int,线性表 From: https://blog.51cto.com/u_16228319/7113188