队列（Queue）的链式存储结构以及双端队列的相关概念（C语言）_队列的链式存储结构的实现在语句enqueue

一、队列（Queue）的链式存储结构

• 队列的链式实现

typedef struct LinkNode{	//链式队列结点
	ElemType data;
	struct LinkNode *next;
}LinkNode;

typedef struct{				//链式队列
	LinkNode *front,*rear;	//队列的队头和队尾指针
}LinkQueue;
1
2
3
4
5
6
7
8

（一）初始化

1. 初始化（带头结点）

typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}LinkNode;

typedef struct{				//链式队列
	LinkNode *front,*rear;	//队列的队头和队尾指针
}LinkQueue;

//初始化队列（带头结点）
void InitQueue(LinkQueue &Q){
	//初始化 front、rear 都指向头结点
	Q.front = Q,rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.front -> next = NULL;
}

void testLinkQueue(){
	LinkQueue Q;	//声明一个队列
	InitQueue(Q);	//初始化队列
	//...后继操作...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.初始化（不带头结点）

//初始化队列（不带头结点）
void InitQueue(LinkQueue &Q){
	//初始化时 front、rear都指向NULL
	Q.front = NULL;
	Q.rear = NULL;
}
1
2
3
4
5
6

（二）判断是否为空

1. 判断是否为空（带头结点）

//判断队列是否为空
bool IsEmpty(LinkQueue Q){
	if(Q.front == Q.rear)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7

2.判断是否为空（不带头结点）

//判断队列是否为空（不带头结点）
bool IsEmpty(LinkQueue Q){
	if(Q.front == NULL)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7

（三）入队

1. 入队（带头结点）

//新元素入队（带头结点）
void EnQueue(LinkQueue &Q,ElemType x){
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
	s -> data = x;
	s -> next = NULL;
	Q.rear -> next = s;	//新结点插入到rear之后
	Q.rear = s;			//修改表尾指针
}
1
2
3
4
5
6
7
8

2. 入队（不带头结点）

（三）出队

1. 带头结点

//队头元素出队（不带头结点）
bool DeQueue(LinkQueue &Q,ElemType &x){
	if(Q.front == Q.rear)
		return false;		//空队
	LinkNode *p = Q.front -> next;
	x = p -> data;			//用变量x返回队头元素
	Q.front -> next = p -> next;//修改头结点的next指针
	if(Q.rear == p)				//此次时最后一个结点出队
		Q.rear = Q.front;		//修改rear指针
	free(p);					//释放结点空间
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

2. 不带头结点

（1）多个结点中删除一个结点

（2）还剩一个结点，然后进行删除

//队头元素出队（不带头结点）
bool DeQueue(LinkQueue &Q, ElemType &x){
	if(Q.front == NULL)
		return false;		//空队
	LinkNode *p = Q.front;	//
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/974992