九、队列

---

 

---

1.定义

一种可以实现”先进先出”的存储结构

2.分类

链式队列 – 用链表实现

静态队列 –用数组实现

静态队列通常都必须是循环队列

循环队列的理解：

1. 静态队列为什么必须是循环队列

传统的数组会使下面这部分内存无法使用！

所以必须是一个循环队列才行

2. 循环队列需要几个参数来确定

需要2个参数来确定

front

rear

3. 循环队列各个参数的含义

2个参数不同场合有不同的含义

1）队列初始化

front和rear的值都是零

2）队列非空

front代表的是队列的第一个元素

rear代表的是队列的最后一个有效元素的下一个元素

3）队列空

front和rear的值相等，但不一定是零

4. 循环队里入队伪算法讲解

1）将值存入r所代表的位置

2）错误的写法r=r+1

正确的写法是：r=（r+1）%数组的长度

5. 循环队列出队伪算法讲解

f=（f+1）%数组长度

6. 如何判断循环队列是否为空

如果 front 与 rear 的值相等，

则该队列就一定为空

7. 如何判断循环队列是否已满

两种方式：

1. 多增加一个标识参数

2. 少用一个元素（常用）

若果r和f的值紧挨着，则队列已满

if（（r+1）%数组长度 == f）

已满

else

不满

3.算法演示

队列的结构和所需的方法

1. typedef struct Queue

2. {

3. int * pBase;

4. int front;

5. int rear;

6. }QUEUE;

7. void init(QUEUE *);

8. bool en_queue(QUEUE *, int);

9. bool full_queue(QUEUE *);

10. bool empty_queue(QUEUE *);

11. void traverse_queue(QUEUE *);

12. bool out_queue(QUEUE *, int *);

init方法

1. void init(QUEUE *pQ)

2. {

3. pQ->pBase = (int *)malloc(sizeof(int) * 6);//创建一个数组

4. pQ->front = 0;

5. pQ->rear = 0;

6. }

en_queue方法

1. bool en_queue(QUEUE * pQ, int val)

2. {

3. if (full_queue(pQ))

4. {

5. return false;

6. }

7. else

8. {

9. pQ->pBase[pQ->rear] = val;

10. pQ->rear = (pQ->rear + 1) % 6;

11. return true;

12. }

13. }

full_queue方法

1. bool full_queue(QUEUE * pQ)

2. {

3. //当rear到了5号元素时，判断为满，因此5号元素无法被赋值

4. if ((pQ->rear + 1) % 6 == pQ->front)

5. return true;

6. else

7. return false;

8. }

empty_queue方法

1. bool empty_queue(QUEUE * pQ)

2. {

3. if (pQ->rear == pQ->front)

4. return true;

5. else

6. return false;

7. }

traverse_queue方法

1. void traverse_queue(QUEUE * pQ)

2. {

3. if (empty_queue(pQ))

4. {

5. return;

6. }

7. int i = pQ->front;

8. while (i != pQ->rear)

9. {

10. printf(“%d”, pQ->pBase[i]);

11. i = (i + 1) % 6;

12. }

13. printf(“n”);

14. return;

15. }

out_queue方法

1. bool out_queue(QUEUE * pQ, int * pVal)

2. {

3. if (empty_queue(pQ))

4. return false;

5. *pVal = pQ->pBase[pQ->front];

6. pQ->front = (pQ->front + 1) % 6;

7. return true;

8. }

4.具体应用

所有和时间有关的操作都与队列有关