队列--c语言实现

1. 队列概念和特点

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点

2. 队列结构

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低，链表中删除头数据直接free，改变头指针指向即可，但是数组就要依次向前移动数据覆盖

typedef int	QueueDataType;

typedef struct QueueNode
{
	int data;
	struct QueueNode* next;
}QueueNode;

typedef struct QueueLinkList
{
	QueueNode* head; //队头
	QueueNode* tail; //队尾
	int size; //元素总数
}QLL;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

为什么这里需要队头和队尾指针呢？

原因：队列有队尾和队头两端，我们会查看队尾数据和队头数据，所以这里就有两个指针用来指向队头和队尾的结点

这里的嵌套结构怎么理解呢？

3. 初始化

需不需要初始化？

需要，因为size不初始化就是0，head和tail也是野指针

void QLLInit(QLL* queue)
{
	assert(queue);

	queue->head = NULL;
	queue->tail = NULL;
	queue->size = 0;
}
1
2
3
4
5
6
7
8

4. 数据进队

void QLLPush(QLL* queue, QueueDataType x)
{
	assert(queue);

	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("QLLPush:malloc is failed!\n");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;
	
    //特殊情况，头指针为NULL时，改变头指针指向
	if (queue->head == NULL)
	{
		queue->head = queue->tail = newnode;
	}
    //通常情况，尾插
	else
	{
		queue->tail->next = newnode;
		queue->tail = newnode;
	}

	queue->size++;
}
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

为什么传结构体指针？

改变QLL结构体中的内容，所以要传结构体指针对结构体更改

5. 数据出队

void QLLPop(QLL* queue)
{
	assert(queue != NULL);
	assert(QLLEmpty(queue) != true);
		
	//只有一个结点时
	if (queue->head->next == NULL)
	{
		free(queue->head);
		queue->head = queue->tail = NULL;
	}
	else
	{
		//通常情况
		QueueNode* del = queue->head;
		queue->head = queue->head->next;
		free(del);
		//无需置空
	}

	queue->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

为什么只有一个结点时，要对头尾指针都置空？

都需要置空，以免出现野指针，不置空该两个指针依旧指向这块空间

为什么del指针不需要置空？

del是局部变量，出了函数栈帧自动销毁

6. 拿到队头数据

QueueDataType QLLFront(QLL* queue)
{
	assert(queue != NULL);
	assert(QLLEmpty(queue) != true);

	return queue->head->data;
}
1
2
3
4
5
6
7

注意：队列为NULL断言，为NULL拿到不数据

7. 拿到队尾数据

QueueDataType QLLBack(QLL* queue)
{
	assert(queue != NULL);
	assert(QLLEmpty(queue) != true);

	return queue->tail->data;
}
1
2
3
4
5
6
7

注意：队列为NULL断言，为NULL拿到不数据

8. 判断队列是否为NULL

bool QLLEmpty(QLL* queue)
{
	assert(queue);

	//return queue->size == 0; //也可以这种
	return queue->head == NULL && queue->tail == NULL;
}
1
2
3
4
5
6
7

9. 队列总数据个数

int QLLSize(QLL* queue)
{
	assert(queue);

	return queue->size;
}
1
2
3
4
5
6

10. 销毁队列

void QLLDestroy(QLL* queue)
{
	assert(queue);
	assert(QLLEmpty(queue) != true);

	QueueNode* cur = queue->head;
	while (cur != NULL)
	{
		QueueNode* del = cur;
		cur = cur->next;
		free(del);
        //无需置空，原因同上
	}

	queue->head = queue->tail = NULL;
	queue->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

为什么head和tail都需置空？

原因：head和tail不置空此指针依旧指向那块空间