数据结构——队列的链式存储（优缺点及代码实现:C语言）_链式储存队列的优势是

队列

队列是运算受限的线性表，和线性表一样也是线性结构，只不过插入只能在队尾插入称为入队，删除只能在队头删除称为出队，和日常生活中的排队顺序一样，是先进先出（FIFO）的线性表。队列存储结构分为顺序存储和链式存储，本文主要介绍 队列的链式存储.

优点：

动态扩容：链式存储结构可以根据实际需求动态扩容，不需要预先确定队列的最大长度，能够更灵活地处理不确定长度的队列。
不会出现溢出问题：链式存储结构不会出现循环队列的溢出问题，可以无限扩展，适合处理大规模数据。
缺点：

占用额外的存储空间：链式存储结构需要额外的指针空间来存储节点之间的关系，占用了额外的存储空间。
**操作复杂：**链式存储结构在插入和删除操作时需要涉及指针的操作，相对于循环顺序存储结构来说，操作可能更加复杂，时间复杂度为O(n)。

代码实现（C语言）

定义

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int DataType;
typedef struct QNode
{
	DataType data;        //定义结点的数据域
	struct QNode *next;	  //定义结点的指针域
}QNode;     

typedef  struct{
	QNode *front,*rear;  //定义队列的头指针和尾指针
}LinkQueue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

初始化

Status InitQueue(LinkQueue *Q) 
{
	Q->front =Q->rear = (QNode *)malloc(sizeof(QNode));
	Q->front->next = NULL;  //带头结点的链队列   
//	Q->front =Q->rear =NULL; 不带头结点
	return OK;
} 
1
2
3
4
5
6
7

销毁

Status DestroyQueue(LinkQueue *Q)
{
	while(Q->front)
	{
		Q->rear = Q->front->next;   //这里Q->rear 只是当作一个中继指针使用，不做尾指针，也可用一个新的指针
		free(Q->front);
		Q->front = Q->rear;
	}
	return OK;
}
1
2
3
4
5
6
7
8
9
10

判队空

Status IsEmpty(LinkQueue *Q)
{
	return Q->front == Q->rear;  //带头结点的     
	   // Q-front == NULL; 不带头结点
}
1
2
3
4
5

入队

1.链队不需要考虑队满情况，申请一个新结点
2.新结点数据域赋值，因为在队尾插入，所以指针域next赋空.
3.队尾指针的next域指向新结点
4.修改队尾指针指向新结点

//入队
Status EnQueue(LinkQueue *Q, DataType x)
{
	QNode *p = (QNode *)malloc(sizeof(QNode));
	if(!p)
		exit(OVERFLOW);
	p->data = x;
	p->next =NULL;
	Q->rear->next = p;
	Q->rear = p;
	return OK;
	/* 不带头节点的话，要判断是否为空队列，如果空队列，要对front和rear指针都进行修改*/
}
1
2
3
4
5
6
7
8
9
10
11
12
13

出队

1.判断队列是否为空，为空则不能出队
2.申请一个结点做为中继结点指向出队元素
3. 出队元素
4. 修改队头指针指向新元素
5. 判断 队中是不是只有这一个元素，如果是修改队尾元素指向队头
6. 清除掉中继结点的内存

Status DeQueue(LinkQueue *Q,DataType *x)
{
	QNode *p;
	if(IsEmpty(Q))
	{
		printf("队空，不能出队！");         
		return ERROR; 
	}
	p = Q->front->next;         // p =Q ->front  不带头结点
	*x = p->data;
	Q->front->next =p->next;  //修改队头指针指向新元素   Q->front = p->next;不带头结点的  
	if(Q->rear == p)   //p->next == NULL;
		Q->rear = Q->front;   //Q->rear = Q->front =NULL; 不带头结点的
	free(p);
	return OK;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

取队头元素

//取队头元素
DataType GetFront(LinkQueue *Q , DataType *x)
{
	if(IsEmpty(Q))
	{
		printf("队空，不能取队头元素！");
		return ERROR;
	}
	*x = Q->front->next->data;  // *x = Q->front->data  不带头结点
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11

显示队中元素

void ShowQueue(LinkQueue *Q)
{
	QNode *p = Q->front->next;
	if (!p)
		printf("队空无元素");
	else
	{
		printf("从队头起队中各元素为：");
		while (p)
		{
			printf("%5d", p->data);
			p = p->next;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

完整示例（C语言实现）

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int DataType;
typedef struct QNode
{
	DataType data;        //定义结点的数据域
	struct QNode *next;	  //定义结点的指针域
} QNode;

typedef struct
{
	QNode *front, *rear;  //定义队列的头指针和尾指针
} LinkQueue;

//初始化
Status InitQueue(LinkQueue *Q)
{
	Q->front = Q->rear = (QNode *)malloc(sizeof(QNode));
	Q->front->next = NULL;  //带头结点的链队列   
	return OK;
}

//销毁
Status DestroyQueue(LinkQueue *Q)
{
	while (Q->front)
	{
		Q->rear = Q->front->next;
		free(Q->front);
		Q->front = Q->rear;
	}
	return OK;
}

// 判队空
Status IsEmpty(LinkQueue *Q)
{
	return Q->front == Q->rear;  //带头结点的
}

//入队
Status EnQueue(LinkQueue *Q, DataType x)
{
	QNode *p = (QNode *)malloc(sizeof(QNode));
	if (!p)
		exit(OVERFLOW);
	p->data = x;
	p->next = NULL;
	Q->rear->next = p;
	Q->rear = p;
	return OK;
}

//出队
Status DeQueue(LinkQueue *Q, DataType *x)
{
	QNode *p;
	if (IsEmpty(Q))
	{
		printf("队空，不能出队！");
		return ERROR;
	}
	p = Q->front->next;
	*x = p->data;
	Q->front->next = p->next;
	if (Q->rear == p)
		Q->rear = Q->front;
	free(p);
	return OK;
}

//取队头元素
DataType GetFront(LinkQueue *Q, DataType *x)
{
	if (IsEmpty(Q))
	{
		printf("队空，不能取队头元素！");
		return ERROR;
	}
	*x = Q->front->next->data;
	return OK;
}

//显示队中元素
void ShowQueue(LinkQueue *Q)
{
	QNode *p = Q->front->next;
	if (!p)
		printf("队空无元素");
	else
	{
		printf("从队头起队中各元素为：");
		while (p)
		{
			printf("%5d", p->data);
			p = p->next;
		}
	}
}

void MenuQueue()
{   /*显示菜单子函数*/
	printf("\n                  队列子系统");
	printf("\n==================================================");
	printf("\n|               1——初始化队列                  |");
	printf("\n|               2——销 毁 队列                  |");
	printf("\n|               3——判队空                      |");
	printf("\n|               4——入队操作                    |");
	printf("\n|               5——出队操作                    |");
	printf("\n|               6——求队头元素                  |");
	printf("\n|               7——显示队中所有元素            |");
	printf("\n|               0——返回                        |");
	printf("\n==================================================");
	printf("\n请输入菜单号（0-7）: ");
}

int main()
{
	int i, n, flag, choice;
	LinkQueue Q;
	DataType x;
	do {
		MenuQueue();
		scanf("%d", &choice);
		switch (choice)
		{
		case 1:
			if (InitQueue(&Q) == OK)
				printf("队列初始化成功！");
			break;
		case 2:
			if (DestroyQueue(&Q) == OK)
				printf("队列已销毁！");
			break;
		case 3:
			if (IsEmpty(&Q) == TRUE)
				printf("队列为空！");
			else
				printf("队列非空！");
			break;
		case 4:
			printf("请输入要入队元素的个数：");
			scanf("%d", &n);
			printf("请输入 %d 个入队的整数，中间用空格隔开： ", n);
			for (i = 0; i < n; i++)
			{
				scanf("%d", &x);
				flag = EnQueue(&Q, x);
			}
			if (flag == OK)
				printf("入队成功！");
			else
				printf("入队失败！");
			break;
		case 5:
			 printf("请输入要出队的元素个数：");
             scanf("%d",&n);
             printf("出队的元素顺序依次为："); 
             for(i=0;i<n;i++)
             {   
             	 flag=DeQueue(&Q,&x);
             	 printf("%5d",x);
             }
			if (flag == OK)
				printf("\n出队成功");
			else
				printf("\n出队失败");
			break;
		case 6:
			if (GetFront(&Q, &x) == OK)
				printf("队头元素为: %d", x);
			break;
		case 7:
			ShowQueue(&Q);
			break;
		}

	} while (choice != 0);
	return 0;
}
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

结语

主要先考虑带不带头结点，然后以链表的思想进行操作队头和队尾，插入删除时间复杂度都是O(1)
带头结点 队头结点 Q->front->next
不带头结点 Q->front

敬请各位大佬批评指正 日后也会持续更新数据结构相关内容，互相学习声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】