【数据结构复习04】队列的链式存储实现以及基本操作

1
2
3
4
5
6
7
8
typedef struct Node{		//链式队列节点
	int data;
	struct Node *next;
}LinkNode;
typedef struct Queue{		//链式队列
	LinkNode *front,*rear;	//队头与队尾指针
}LiQueue;

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<stdio.h>
#include<stdlib.h>

typedef struct Node{
	int data;
	struct Node *next;
}LinkNode;
typedef struct Queue{
	LinkNode *front,*rear;
}LiQueue;

//初始化 
bool InitQueue(LiQueue &queue){
	if(queue.front=queue.rear=(Node *)malloc(sizeof(Node)))	//带头节点 
		return false;
	
	queue.rear->next=NULL;									//初始栈为空 
	return true;
}

//判空 
bool EmptyQueue(LiQueue queue){
	if(queue.front->next==NULL)
		return true;
	return false;
}
//入队列 
bool EnQueue(LiQueue &queue,int e){
	LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
	if(p==NULL)
		return false;
	p->data=e;
	p->next=NULL;
	queue.rear->next=p;
	queue.rear=p;
	return true;
}
//获取队头 
bool GetHead(LiQueue queue,int &head){
	if(EmptyQueue(queue))
	{
		printf("队列为空，无队头！n");
		return false;
	}
		
	head=queue.front->next->data;
	return true;
}

//出队列 
bool DeQueue(LiQueue &queue,int &de){
	if(EmptyQueue(queue)){
		return false;
	}
	de=queue.front->next->data;
	LinkNode *p;
	p=queue.front->next;
	if(p==queue.rear)
		queue.rear=queue.front;
	queue.front->next=p->next;
	 
	free(p);
	return true;
} 

//得到队列长度
int GetLen(LiQueue queue)
{
	if(EmptyQueue(queue))
		return 0;
	int len=0;
	while(queue.front->next!=NULL){
		len++;
		queue.front=queue.front->next;
	}
	return len;
		
}

//输出队列 
bool PrintQueue(LiQueue queue){
	if(EmptyQueue(queue))
		return false;
		
	LinkNode *p;
	p=queue.front->next;
	printf("队列为:");
	while(p!=NULL){
		printf("t%dn",p->data);
		p=p->next;
	}
	return true;
} 

int main()
{
	
	LiQueue queue;
	int head,de;
	
	InitQueue(queue);
	
	EnQueue(queue,1);
	
	EnQueue(queue,2);
	
	EnQueue(queue,3);
	
	EnQueue(queue,4);
	
	EnQueue(queue,5);
	
	EnQueue(queue,6);
	
	PrintQueue(queue);
	
	printf("Len:%dn",GetLen(queue));
	
	if(GetHead(queue,head)){
		printf("head:%dn",head);		
	}
	
	printf("head:%dn",head);
	
	if(DeQueue(queue,de))	
		printf("de:%dn",de);
	else
		printf("栈为空！n"); 
	
	if(DeQueue(queue,de))	
		printf("de:%dn",de);
	else
		printf("栈为空！n"); 
	
	if(DeQueue(queue,de))	
		printf("de:%dn",de);
	else
		printf("栈为空！n"); 
		
	EnQueue(queue,2);
	
	if(GetHead(queue,head)){
		printf("head:%dn",head);		
	}
	
	PrintQueue(queue);
	system("pause");
	return 0;
 }