四、考研数据结构笔记——栈与队列基础知识（栈与队列的理解，易混淆点，熟记的代码）

2021/11/27 23:40:55

编程Tag： data return 队列考研 front maxSize rear 熟记

本文主要是介绍四、考研数据结构笔记——栈与队列基础知识（栈与队列的理解，易混淆点，熟记的代码），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、栈与队列概念考点提炼

栈与队列都是一种操作受限的线性表，都是 线性结构。逻辑结构相同。
栈概括为LIFO（后进先出）；队列概括为FIFO（先进先出）
对于栈，n个不同的元素，出栈元素不同的排列的个数（如下）

二、栈的基本操作（要背的代码）

2.1 栈的结构体

#define MaxSize 50
typedef struct{
	ElemType data[MaxSize];	//存放栈的中元素
	int top;				//栈顶指针
}

2.2 初始化栈

void InitStack(SqStack &S){
	S.top=-1;		//初始化栈顶指针为-1
}

2.3 判断栈是否为空

bool StackEmpty(SqStack &S){
	if(S.top==-1)	//栈空
		return true;
	else
		return false;
}

2.4 进栈

bool Push(SqStack &S,ElemType x){
	if(S.top == MaxSize -1)		//栈满，报错
		return false;
	S.data[++S.top] = x;		//这条是核心
	return true;
	//
这一段代码可能有一点变化，考试可能会把初始S.top设置为0；这样的话，
}

2.5 出栈

bool Pop(SqStack &S,ElemType &x){
	if(S.top == -1)		//栈空，报错
		return false;
	x=S.data[S.top--];	//这段是核心
	return true;
}

2.6 读取栈顶元素

bool GetTop(SqStack &S,ElemType &x){
	if(S.top == -1)		//栈空报错
		return false;
	x=S.data[S.top];		
	return true;
}

2.7 更改初始条件（灵活）

有的题目会把指针由-1变为0。如下图
请添加图片描述

此时初始化，进栈和出栈的关键代码需要更改，

初始化：S.top=0
进栈：S.data[top++] =x;
出栈：x = S.data[- -S.top];

三、共享栈与链栈（理解就行）

3.1 共享栈定义

由两个指针，两个栈顶向中间延展，目的就是更好利用存储空间
top0=-1，表示从下往上的栈0为空；
top1=maxSize，表示从上往下的栈1为空；
当top1-top0=1时，表示两个栈都满了。
其存储的时间复杂度为O(1);

3.2 共享栈结构体

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int top0;	//0号栈顶指针
	int top1;	//1号栈顶指针
}

3.3 共享栈初始化

void InitStack(ShStack &S){
	S.top0 = -1;
	S.top1 =MaxSize;
}

3.4 链栈概念

其实就是单链表，所有的插入元素在头结点进行，可以看上一篇的单链表
优点：不存在栈溢出的情况，无限延展。便于多个栈共享存储空间并提高效率

3.5 链栈结构体

typedef struct LinkNode{
	ElemType data;	//数据域
	struct LinkNode *next;//指针域
} *LiStack;

四、队列定义

一种操作受限的线性表。允许在表的一端进行插入（入队），另一端进行删除（出队）。
先进先出。FIFO
front 表头，rear 表尾

五、队列顺序存储结构体

define MaxSize 50
typedef struct{
	ElemType data[MaxSize];
	int front,rear;
}SqQueue;

六、顺序队列转循环队列

一般顺序队列如下

队空状态 Q.front == Q.rear=0
进队状态：队尾加一
出队状态：对头加一

但是 队列是一个线性表，一直往上移会出现指针出界，所以一般都是把队列想象成一个环状 这样就不会出现上面的情况。

所以 一般考试中，所讨论的队列都是循环队列 ，这个一定要理解。不然不知道怎么突然来的循环队列

七、循环队列基本操作（要背的代码）

7.1 循环队列初始化

void InitQueue(SqQueue &Q){
	Q.rear = Q.front = 0;		//初始化队首，队尾指针
}

7.2 循环队列判队空

bool isEmpty(SqQueue Q){
	if(Q.rear == Q.front)
		return true;
	else
		return false;
}

7.3 循环队列入队

bool EnQueue(SqQueue &Q,Elemtype x){
	if((Q.rear+1)%MaxSize==Q.front)	//队列已经满了，这个一定要记住
		return false;
	Q.data[Q.rear] = x;
	Q.rear=(Q.rear + 1) %MaxSize;
	return true;
}

7.4 循环队列出队

bool DeQueue(SqQueue &Q,ElemType &x){
	if(Q.rear == Q.front)	//队空报错
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front+1)%MaxSize;	//队头指针+1
	return true;

}

7.5 其他几个常考操作

队满：（Q.rear +1）%MaxSize==Q.front
队中元素个数：（Q.rear -Q.front+ MaxSize）% MaxSize
入队（增加元素）指针变化：Q.front =（Q.front+1）%MaxSize
出队（删除元素）指针变化：Q.rear=（Q.rear+1）%MaxSize

7.6 选择题考法1

经常给一个数组，然后给当前的rear和front的值，算现在一共多少个元素在队列中
用上面的公式计算即可

7.7 选择题考法2

一个数组，给出初始rear和front值，删除n个元素和插入n个元素之后的rear和front值分别是多少
用上述公式，front和rear都是＋1。只不过删除元素的个数加的是front，增加元素的个数加的是rear。
其次，不要忘了%MaxSize

六、循环队列判断空和满的不同方式

6.1 方式一

该方式也是最默认的方式，牺牲一个元素来进行判定。
结构体

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int front,rear;
}SqQueue;

初始化：Q.rear=Q.front=0
队空：Q.rear == Q.front
队满：Q.rear =（Q.rear+1）%MaxSize

在这里插入图片描述

6.2 方式二

考试的时候，就是想把方式一中浪费的那一块给填补上去
结构体

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int front,rear;
	int size;	//队列当前长度
}SqQueue;

初始化：①rear = front = 0;② int size=0
队空：①front == rear ；②size ==0
队满：①front == rear ；②size ==MaxSize