队列

发表于   |   分类于

声明: 本人只一在校学生，不足之处，谨请指教！有些内容可能会引起某些读者不适, 请小心阅读. 有些内容并没有详细介绍， 可能简单理解也是错误的， 但是这都是为了尽量简单。

前言: 我自己认为, 对想要学习编程的人而言， C语言是一门必须要学习的语言, 但是其实就现在这个时代的话, 你没有学习C语言的绝对必要。使用别的高级语言（比如python）站在巨人的肩膀上很好， 也很爽。

推荐书目：

  • 《C语言程序设计》
  • 《C标准库》
  • 《C primer plus》
  • 《C缺陷和陷阱》
  • 《C专家编程》
  • 《linux程序设计》

队列是一种很重要的数据结构，因为它环绕我们生活的各个方面，这篇文章关注于：

  • 什么是队列？
  • 代码实现队列的基本套路
  • 队列的方法
  • 循环队列的一些想法

我们将通过队列的数组实现来理解队列， 链表实现不是我们考虑的。

什么是队列？

队列是一种先进先出的数据结构。 举个栗子，生活中买票的时候需要排队：

  • 先到的人先享受售票服务
  • 在一个时刻， 只有最前面的那个人在享受售票服务
  • 后来的人，只能跟在队列的最末端

C语言的代码实现

1
2
3
4
5
struct queue
{
	void* q[QUE_SIZE];
	int front, rear;
};

这里是结构定义, 我们自定义的结构体类型queue中有一个成员是数组，它的元素的类型是空类型指针，以便于指向各种数据类型。

1
2
3
4
void queue_init(struct queue *q)
{
	q->front = q->rear = -1;
};

这里是队列初始化， 因为一开始是一个空队列， 所以我们需要把front指针和rear指针指向非法的数组index值-1

套路是:

  • front指向队列第一个数据的前面。
  • rear指向对尾（可以追加数据的空位置的前面）。

套路是不需要解释的，慢慢体会就可以


我们现在可以看到，当front和rear相等的时候，队列是空的。

队列的一些方法

追加（append）一个对象.

我们先考虑在空的队列里面增加一个数据的情况，我们现在队列里面还没有任何数据。

1
2
3
4
5
6
7
8
// 构造一个q指针
struct queue *q = (struct queue*)malloc(sizeof(struct queue));
// 构造一个p指针
int a = 10;
void *p = &a;
//追加操作
q->q[q->rear++] = p; // q是一个指向queue类型数据的指针， p是一个空类型的指针，是待加入的数据


我们在这里增加了一个数据q,所以队尾指针发生了改变，但依然指向了可以添加数据的前一个位置，而队头指针front仍然指向第一个队头数据的前面。

出队操作.

1
printf("%d", *(int*)q->q[++q->front]);

在这里我们把队头指针向右移动了一下， 然后转为原来的数据类型的指针， 解引用。得到了原来的数据类型。

所以，我们学会了增加数据，学会了取出数据。也很容易的能看出来：当rear指向数组的最后一个节点的时候，队列满了，不能进行进队操作。当front到达最后一个节点的时候，队列空了，没有数据可供出队了。

问题

问题是，随着出队操作的执行。队头指针右移会导致左侧的有效空间无法使用，因为我们不管是进队操作，还是出队操作，都要依靠front和rear的位置。而他们只能向右移动。所以我们可能会面临这样的一种情况：

明明有可用空间，但是我们无法进行进队操作了。

图示情况可以简单的把front和rear重置为-1。但如果是只有队尾指针到了最后一个位置，队列中还有数据，就不能简单的重置指针了（否则会丢失数据）。其实可以移动数据，但同样不理想。

这种设计队列全满的情况（rear-front = que_max）请自己研究一下

循环队列的一些想法

设计

如果我们可以让rear到了队列的末尾（rear= QUE_SIZE-1的情况）的下一个值是0， 也就是队列的开头，这样的话我们就又可以使用数组的空间了。

之前我们是简单的++来进行移动操作的，进队：++rear， 写入数据；出队，++front, 拿出数据。而如果我们想要让rear可以转回去，就不能简单的进行++。 首先想到的是一个判断：

1
q->rear = (q->rear == QUE_SIZE-1)? 0 : (q->rear+1);

我们依靠此来制作一个循环队列。实质是front和rear指针的循环。另一种想法是：
1
q->rear = (++q->rear) % QUE_SIZE;

简单的考虑这个代码，当quesize=3的时候，那么rear=2是rear指向队列末尾的情况，它的下一个位置应该是2+1的结果对3取余，得到0。正是我们需要的结果!

问题

很简单的，我们可以知道当front=rear的时候，队列是空着的，比如一开始的时候。但是当rear指针进行过一次循环转到了和front相同的位置，也就是说此时队列满了，同时front和rear的值相等了。这样就产生了一个问题：我们不能通过判断front是否=rear来得到队列满还是队列空的结果。基于队列满了就不能进队，队列空了就不能出队。无法判断队列满还是队列空，是不可以接受的。

这也有两个方法来解决：

  • 设置一个标记
    我们可以设置增加一个标记，如果在进队操作之后，front=rear，那么我们就设置这个标志为队列满了。在出队操作之后，front=rear则设置标志为队列为空。这样我们就可以得到正确的队列慢还是队列空的信息了。
    1
    2
    3
    4
    5
    6
    7
    8
    enum queue_tag{empty, full};
    struct queue
    {
    	void* q[QUE_SIZE];
    	int front, rear;
    	enum queue_tag tag;
    };
  • 空掉一个队列的空间
    1
    q->rear = (++q->rear) % QUE_SIZE-1; // 空出最后一个数组元素
    这样的话，队空的情况就是rear=front， 而如果rear的下一个位置是front的话，那队列就满了。

代码实现

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
#include <stdio.h>
#include <stdlib.h>
#define QUE_SIZE 3
// 结构定义
struct queue
{
	void* q[QUE_SIZE];
	int front, rear;
	enum queue_tag{ queue_empty, queue_full }tag;
};
// 初始化
void queue_init(struct queue *q)
{
	q->front = q->rear = -1;
	q->tag = queue_empty;
};
// 入队
int queue_in(struct queue *q, void *p)
{
	if (q->tag == queue_full) 
	{
		return -1;
	}
	else
	{
		q->rear = (q->rear + 1) % QUE_SIZE;
		q->q[q->rear] = p;
		if (q->rear == q->front) { q->tag = queue_full; }
		return 0;
	}
}
// 出队
void* queue_out(struct queue *q, void *p)
{
	if (q->tag == queue_empty)
	{
		return NULL;
	}
	else
	{
		q->front = (q->front + 1) % QUE_SIZE;
		void *ret = q->q[q->front];
		if (q->front == q->rear) { q->tag = queue_empty; }
		return ret;
	}
}

这段代码有问题，因为初始化的关系，如果一直进行入队操作而不进行出队操作。那么front一直是-1，而rear一直在[0, QUE_SIZE-1]的范围内, front不可能等于rear,所以这样是无法设置为队满的。入队操作可以无休止的进行，这样是错误的！！！

重新设计front和rear指针

  • front指针指向第一个队列数据
  • rear指向可以存放新数据的位置
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
#include <stdio.h>
#include <stdlib.h>
#define QUE_SIZE 3
enum queue_tag{ queue_empty, queue_full };
struct queue
{
	void* q[QUE_SIZE];
	int front, rear;
	enum queue_tag tag;
};
void queue_init(struct queue *q)
{
	q->front = q->rear = 0;
	q->tag = queue_empty;
};
int queue_in(struct queue *q, void *p)
{
	if (q->tag == queue_full) 
	{
		return -1;
	}
	else
	{
		q->q[q->rear] = p;
		q->rear = (q->rear + 1) % QUE_SIZE;
		if (q->rear == q->front) { q->tag = queue_full; }
		return 0;
	}
}
void* queue_out(struct queue *q)
{
	if (q->tag == queue_empty)
	{
		return NULL;
	}
	else
	{
		void *ret = q->q[q->front];
		q->front = (q->front + 1) % QUE_SIZE;
		if (q->front == q->rear) { q->tag = queue_empty; }
		return ret;
	}
}

进队和出队有一些改动，就是我们先进行数据操作，再进行front或者rear下一位置的计算，依此设置是否队满的标记。

测试结果：

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
int main(void)
{
	// 构造一个q指针
	struct queue *q = (struct queue*)malloc(sizeof(struct queue));
	queue_init(q);
	// 构造一个p指针
	int a = 10;
	void *p = &a;
	// 设置一个返回值
	int ret = -1;
	// 预计成功的操作
	ret = queue_in(q, p);
	if (ret == 0)  printf("插入成功\n") ; 
	else printf("插入失败\n");
	ret = queue_in(q, p);
	if (ret == 0)  printf("插入成功\n") ; 
	else printf("插入失败\n");
	ret = queue_in(q, p);
	if (ret == 0)  printf("插入成功\n") ; 
	else printf("插入失败\n");
	// 预计失败的操作
	ret = queue_in(q, p);
	if (ret == 0)  printf("插入成功\n") ; 
	else printf("插入失败\n");
		
	return 0;
}


看起来好像没什么问题，但其实这代码还是有问题的，因为如果进队不到队满，那么tag值不会被修改。则队列标记一直是empty。而已经进入队列的数据无法出队进行处理。

我现在也不想用什么tag了，直接用len来表示进入数据的个数

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
#include <stdio.h>
#include <stdlib.h>
#define QUE_SIZE 3
struct queue
{
	void* q[QUE_SIZE];
	int front, rear;
	int len;
};
void queue_init(struct queue *q)
{
	q->front = q->rear = 0;
	q->len = 0;
};
int queue_in(struct queue *q, void *p)
{
	if (q->len == QUE_SIZE)
	{
		return -1;
	}
	else
	{
		q->q[q->rear] = p;
		q->rear = (q->rear + 1) % QUE_SIZE;
		++q->len;
		return 0;
	}
}
void* queue_out(struct queue *q)
{
	if (q->len == 0)
	{
		return NULL;
	}
	else
	{
		void *ret = (q->q)[q->front];
		q->front = (q->front + 1) % QUE_SIZE;
		--q->len;
		return ret;
	}
}

最终：

当然，这样搞的话。我们就无法修改队列最大值的定义超过int的最大值了。