数据结构与算法(7)——队列_queueentry *next;

队列

队列是一种操作受限的线性表，跟栈的“先进后出”特性相反，队列具有“先进先出”(FIFO)的特性。在队列中，插入操作在一端进行，删除操作在另一端进行。插入端称为队尾，删除端称为队头。

和栈一样，队列的实现也包括顺序存储和链式存储两种结构。

队列的顺序存储

需要分配一段连续的空间来存储队列中的元素，因为队头和队尾都是可变化的，还需要设置队头指针和队尾指针。

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

//使用顺序存储结构要预先估计空间大小
#define MAXQUEUE 10

typedef int QueueEntry;

typedef struct queue
{
	int front, rear;
	QueueEntry entry[MAXQUEUE];
}Queue, *QueuePtr;

typedef enum Status{
	success,fail,fatal,range_error,overflow,underflow
}Status;

Status Queue_Init(QueuePtr* q)
{
	Status outcome = fatal;

	QueuePtr queueptr = (QueuePtr)malloc(sizeof(Queue));
	if (queueptr)
	{
		queueptr->front = -1;
		queueptr->rear = -1;
		*q = queueptr;
		outcome = success;
	}

	return outcome;
}

void Queue_Destroy(QueuePtr* q)
{
	if (*q)
	{
		free(*q);
		*q = NULL;
	}
}

void Queue_Clear(QueuePtr q)
{
	q->front = -1;
	q->rear = -1;
}

bool Queue_Empty(QueuePtr q)
{
	return (q->front % MAXQUEUE) == (q->rear % MAXQUEUE);
}

bool Queue_Full(QueuePtr q)
{
	return ((q->rear + 1) % MAXQUEUE) == (q->front % MAXQUEUE);
}

Status Queue_EnQueue(QueuePtr q, QueueEntry item)
{
	Status outcome = overflow;

	if (!Queue_Full(q))
	{
		q->rear++;
		q->entry[q->rear] = item;
		outcome = success;
	}

	return outcome;
}

Status Queue_DeQueue(QueuePtr q, QueueEntry* item)
{
	Status outcome = underflow;

	if (!Queue_Empty(q))
	{
		q->front++;
		*item = q->entry[q->front];
		outcome = success;
	}

	return outcome;
}

int Queue_Size(QueuePtr q)
{
	return (q->rear - q->front);
}

int main()
{
	QueuePtr q = NULL;
	Status outcome;

	outcome = Queue_Init(&q);
	if (outcome == success)
	{
		printf("init success\n");
	}

	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

需要注意，队列空和满的情况下都有

(front % MAXQUEUE) == (rear % MAXQUEUE)
1

因此，我们牺牲一个存储单元，用以下表达式表示队列已满，避免只通过比较front和rear无法区分队列空或者满的情况。

((rear + 1) % MAXQUEUE) == (front % MAXQUEUE)
1

队列的链式存储

用单链表来实现链队列。只有表头指针不方便在表尾进行插入操作，为了操作方便，需要增加一个尾指针。一个链队列就由一个头指针和尾指针唯一确定。在实现时，可以将两个指针封装为一个结构。

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

typedef int QueueEntry;

typedef struct node
{
	QueueEntry entry;
	struct node* next;
}QueueNode,*QueueNodePtr;

typedef struct queue
{
	QueueNode* front;
	QueueNode* rear;
}Queue,*QueuePtr;

typedef enum Status
{
	succes,fail,fatal,range_error,overflow,underflow
}Status;

Status Queue_Init(QueuePtr q)
{
	Status outcome = fatal;
	QueueNodePtr ptr = (QueueNodePtr)malloc(sizeof(QueueNode));
	
	if (ptr)
	{
		q->front = ptr;
		q->rear = ptr;
		ptr->next = NULL;
		outcome = succes;
	}
	return outcome;
}

bool Queue_Empty(QueuePtr q)
{
	return (q->front->next == NULL && q->rear->next == NULL);
}

Status Queue_EnQueue(QueuePtr q, QueueEntry item)
{
	Status outcome = succes;
	QueueNodePtr ptr = (QueueNodePtr)malloc(sizeof(QueueNode));

	if (ptr == NULL)
	{
		outcome = fatal;
		return outcome;
	}
	ptr->entry = item;
	ptr->next = NULL;
	q->rear->next = ptr;
	q->rear = ptr;

	return  outcome;
}

Status Queue_DeQueue(QueuePtr q, QueueEntry* item)
{
	Status outcome = succes;
	QueueNodePtr ptr;
	QueueEntry x;

	if (Queue_Empty(q))
	{
		outcome = underflow;
		return outcome;
	}
	ptr = q->front->next;
	x = ptr->entry;
	q->front->next = ptr->next;
	//这里需要注意，如果队列只有一个元素，DeQueue后，rear重新需要指向头结点
	if (q->rear == ptr)
	{
		q->rear = q->front;
	}
	free(ptr);
	*item = x;

	return outcome;
}

void Queue_Clear(QueuePtr q)
{
	QueueEntry item;

	while (!Queue_Empty(q))
	{
		Queue_DeQueue(q, &item);
	}
}

void Queue_Destroy(QueuePtr q)
{
	Queue_Clear(q);
	free(q->front);
}

int Queue_Size(QueuePtr q)
{
	int count = 0;
	QueueNodePtr ptr = q->front->next;

	while (ptr != NULL)
	{
		count++;
		ptr = ptr->next;
	}

	return count;
}

int main()
{
	QueuePtr q = (QueuePtr)malloc(sizeof(Queue));
	Status outcome;
	QueueEntry item;

	outcome = Queue_Init(q);
	if (outcome == succes)
	{
		printf("init success\n");
	}
	Queue_EnQueue(q, 1);
	Queue_DeQueue(q, &item);
	printf("%d\n", item);
	
	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