链队列的出队，入队_链队列的入队和出队

链队列

定义:采用链式存储结构实现的队列。
通常采用单链表来实现，因此结构与单链表类似。

由于队列的插入和删除操作分别在表的两端进行，所以需要两个分别指向对头和队尾的指针，即队头指针front和队尾指针rear。

图中头指针front和尾指针rear是两个独立的指针变量，从结构上考虑，一般将头指针和尾指针的变量front、rear封装在一个结构类型中作为链队列的数据类型。

typedef int elemtype;

typedef struct QueueNode
{
	elemtype data;//用来存放数据元素的信息
	struct QueueNode* next;
}LinkedQueueNode;

typedef struct LQueue
{
	LinkedQueueNode* front;//队头指针
	LinkedQueueNode* rear;//队尾指针
}LQueue,*LinkedQueue;//链队列结构类型
1
2
3
4
5
6
7
8
9
10
11
12
13

链队列的初始化
就是构造一个空队列，将头指针front和尾指针rear都指向头结点，并置头结点的指针域为空，因为此时队列中还没有数据元素。

//队列的初始化
LinkedQueue Init_LinkedQueue()
{
	LinkedQueue Q = (LQueue*)malloc(sizeof(LQueue));
	LinkedQueueNode* head = (LinkedQueueNode*)malloc(sizeof(LinkedQueueNode));

	Q->front = head;
	Q->rear = head;
	head->next = NULL;
	return Q;
}
1
2
3
4
5
6
7
8
9
10
11

入队
数据元素e入队就是将数据元素e插入到链队列的队尾，设置尾指针指向新入队的队尾数据元素。类似于尾插

bool in_LinkedQueue(elemtype e, LinkedQueue Q)
{
	LinkedQueueNode* L = (LinkedQueueNode*)malloc(sizeof(LinkedQueueNode));
	L->data = e;
	L->next = NULL;

	Q->rear->next = L;
	Q->rear = L;
	return true;
}
1
2
3
4
5
6
7
8
9
10

出队
就是指删除队列的队头数据元素，设置头结点指向链队列中的下一个数据元素。类似于头删。

bool out_LinkedQueue(LinkedQueue Q)
{
	LinkedQueueNode* node;

	if (Q->front == Q->rear)
	{
		return false;
	}

	node = Q->front->next;
	Q->front->next = node->next;

	if (node == Q->rear)
	{
		Q->rear = Q->front;
	}
	printf("%d,", node->data);
	free(node);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

完整代码

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

typedef int elemtype;

typedef struct QueueNode
{
	elemtype data;//用来存放数据元素的信息
	struct QueueNode* next;
}LinkedQueueNode;

typedef struct LQueue
{
	LinkedQueueNode* front;//队头指针
	LinkedQueueNode* rear;//队尾指针
}LQueue,*LinkedQueue;//链队列结构类型

//队列的初始化
LinkedQueue Init_LinkedQueue()
{
	LinkedQueue Q = (LQueue*)malloc(sizeof(LQueue));
	LinkedQueueNode* head = (LinkedQueueNode*)malloc(sizeof(LinkedQueueNode));

	Q->front = head;
	Q->rear = head;
	head->next = NULL;
	return Q;
}

//入队
bool in_LinkedQueue(elemtype e, LinkedQueue Q)
{
	LinkedQueueNode* L = (LinkedQueueNode*)malloc(sizeof(LinkedQueueNode));
	L->data = e;
	L->next = NULL;

	Q->rear->next = L;
	Q->rear = L;
	return true;
}

//出队
bool out_LinkedQueue(LinkedQueue Q)
{
	LinkedQueueNode* node;

	if (Q->front == Q->rear)
	{
		return false;
	}

	node = Q->front->next;
	Q->front->next = node->next;

	if (node == Q->rear)
	{
		Q->rear = Q->front;
	}
	printf("%d,", node->data);
	free(node);
	return true;
}
int main()
{
	LinkedQueue Q;
	Q = Init_LinkedQueue();
	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

------甜辣椒------------------------------------------------------------------