王道考研数据结构之------队列链式实现(不带头结点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>

typedef ElemType int;

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

typedef struct{//链式队列
	LinkNode *front, *rear;//队列的队头和队尾指针
}LinkQueue;
//初始化队列 06 02:58
void InitQueue(LinkQueue &Q){
	//初始化时front和rear都指向NULL
	Q.front = Q.rear = NULL;
}
/*************************************/
//判断队列是否为空(不带头结点)06 02:58
bool IsEmpty(LinkQueue Q){
	//看头指针的值是否为空
	return (Q.front == NULL);
}
/*************************************/
//新元素入队,从尾部入队(不带头结点)06 04:21
void EnQueue(LinkQueue &Q, ElemType x){
	//新建节点s并分配内存空间
	LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
	//赋值
	s->data = x;
	//s->next == NULL
	s->next = NULL;
	//判断队列是否为空(如果为空的话)
	if(Q.front == NULL){
		//头指针指向s
		Q.front = s;
		//尾指针指向s
		Q.rear = s;
	//(如果队列不为空的话)
	}else{
		//s插入到rear节点之后
		Q.rear->next = s;
		//队尾指针移动到s的位置
		Q.rear = s;
	}
	//返回
	return true;
}
/*************************************/
//队头元素出队,(不带头结点)06 06:34
bool DeQueue(LinkQueue &Q, ElemType &x){
	//判断队列是否为空
	if(Q.front == NULL) return false;
	//新建节点p指向Q.front
	LinkNode *p = Q.front;
	//将p节点的data赋值给x
	x = p->data;
	//移除节点p
	Q.front->next = p->next;
	//如果队尾指针就是p的话
	if(Q.rear == p){
		//队头指针指向NULL
		Q.front = NULL;
		//队尾指针指向NULL
		Q.rear = NULL;
	}
	//释放p
	free(P);
	//返回
	return true;
}