队列的实现---超详细

队列的实现—超详细

一、队列的模型

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。

所以我们可以思考一下，这种结构如果用顺序表来实现一定是十分麻烦的，因为顺序表的头删的时间复杂度是O(N)。所以我们应该要采取链表来实现队列结构。
至于是单链表还是带头双向循环链表，其实都是无伤大雅的，在这里我们选择单链表。
结构：

typedef int SDataType;

typedef struct Queue
{
	struct Queue* next;
	SDataType val;
}QU;
1
2
3
4
5
6
7

其实这样我们已经把单链表构建出来了，但是请大家思考两个问题:
如果是入队时，难道我每次入队都需要去找一次尾吗？
如果是计算队列长度时，这是一个不在连续空间存储的数据结构，我们如果简单的计算出长度呢？

所以我们可以再次引入一个结构体，将这个链表的头、尾和长度都计算出来。

typedef struct queue
{
	QU* phead;
	QU* tail;
	int size;
}q;
1
2
3
4
5
6

二、代码实现以及测试用例

①队列初始化

void QIni(q* p)
{
	assert(p);
	p->phead = p->tail = NULL;
	p->size = 0;
}
1
2
3
4
5
6

②入队

void QPush(q* p, QDataType x)
{
	assert(p);
	QU* newnode = (QU*)malloc(sizeof(QU));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->val = x;
	if (p->tail == NULL)
	{
		p->phead = p->tail = newnode;
	}
	else
	{
		p->tail->next = newnode;
		p->tail = newnode;
	}
	p->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

③出队

void QPop(q* p)
{
	assert(p);
	assert(p->phead);
	QU* tmp = p->phead->next;
	free(p->phead);
	p->phead = tmp;
	if (p->phead == NULL)
	{
		p->tail = NULL;//很关键
	}
	p->size--;
}

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

④输出队头

QDataType QFront(q* p)
{
	assert(p);
	assert(p->phead);
	return p->phead->val;
}
1
2
3
4
5
6

⑤输出队尾

QDataType QBack(q* p)
{
	assert(p);
	assert(p->tail);
	return p->tail->val;
}
1
2
3
4
5
6

⑥判断队列是否为空

bool QEmpty(q* p)
{
	assert(p);
	return p->phead == NULL;
}
1
2
3
4
5

⑦队列的长度

int QSize(q* p)
{
	assert(p);
	return p->size;
}
1
2
3
4
5

⑧队列的销毁

void QDestroy(q* p)
{
	assert(p);
	//assert(p->phead);
	QU* tmp = p->phead;
	while (tmp)
	{
		QU* tmp2 = tmp->next;
		free(tmp);
		tmp = tmp2;
	}
	p->phead = p->tail = NULL;
	p->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

⑨测试用例

void test2()
{
	q p;
	QIni(&p);
	QPush(&p, 1);
	QPush(&p, 2);
	QPush(&p, 3);
	QPush(&p, 4);
	QPush(&p, 5);
	while (!QEmpty(&p))
	{
		printf("%d ", QFront(&p));
		QPop(&p);
	}
	printf("\n");
	QDestroy(&p);
}

int main()
{
	test2();
	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