C语言实现队列Queue

文章来源：http://blog.csdn.net/zqixiao_09/article/details/50420527

http://yangzhizhen.iteye.com/blog/1472348

 还是先放这张图，以便对比和理解：

 

   队列是限制在两端进行插入操作和删除操作的线性表，允许进行存入操作的一端称为“队尾”，允许进行删除操作的一端称为“队头”。当线性表中没有元素时，称为“空队”。特点：先进先出（FIFO）。

一、顺序队列        建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置，如图所示

     每次在队尾插入一个元素是，rear增1；每次哎队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。

    在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从N（MaxSize）增1变到0，可用取余运算rear%N和front%N来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。

    在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。

总结：

1、队头指针front，指向队头元素的位置的前一个位置。即指向预留的位置；

2、队尾指针rear，指向队尾元素的位置；

3、入队： rear = (rear + 1) % N (maxsize)，然后元素放入队尾rear所指向的位置；

4、出队： front = (front + 1) % N，然后取出队头指针front所指向的元素；

5、队空： front == rear;

6、队满： (rear + 1) % N == front, N为数组的元素个数；

7、为了区别空队和满队，满队元素个数比数组元素个数少一个。

下面是顺序队列的运算：

   顺序队列也是顺序表的一种，具有顺序表同样的存储结构，由数组定义，配合使用数组下表表示的队头指针和队尾完成各种操作：

[cpp] view plain copy

1. #define N 64  //队列中数据元素的数据类型  
2. typedef int data_t;  
3. typedef struct  
4. {  
5.     data_t data[N]; //用数组作为队列的储存空间  
6.     int front,rear; //指示队头位置和队尾位置的指针  
7. }sequeue_t;  

1、创建空队列

[cpp] view plain copy

1. sequeue_t *CreateEmptySequeue()  
2. {  
3.     sequeue_t *queue;  
4.     queue = (sequeue_t *)malloc(sizeof(sequeue_t));  
5.     if (NULL == queue) return NULL;  
6.       
7.     queue->front = queue->rear = 0;  
8.   
9.     return queue;  
10. }  

2、摧毁一个队列

[cpp] view plain copy

1. void DestroySequeue(sequeue_t *queue)  
2. {  
3.     if (NULL != queue)   
4.     {  
5.         free(queue);  
6.     }  
7. }  

3、判断一个队列是否为空

[cpp] view plain copy

1. int EmptySequeue(sequeue_t *queue)  
2. {  
3.     if (NULL == queue)   
4.         return -1;  
5.   
6.     return (queue->front == queue->rear ? 1 : 0);  
7. }  

4、判断一个队列是否为满

[cpp] view plain copy

1. int FullSequeue(sequeue_t *queue)  
2. {  
3.     if (NULL == queue) return -1;  
4.   
5.     return ((queue->rear + 1) % N == queue->front ? 1 : 0);  
6. }  

5、清空一个队列

[cpp] view plain copy

1. void ClearSequeue(sequeue_t *queue)  
2. {  
3.     if (NULL == queue) return;  
4.       
5.     queue->front = queue->rear = 0;  
6.   
7.     return;  
8. }  

6、入队

[cpp] view plain copy

1. int EnQueue(sequeue_t *queue, data_t x)  
2. {  
3.     if (NULL == queue) return - 1;  
4.   
5.     if (1 == FullSequeue(queue)) return -1; /* full */  
6.   
7.     queue->rear = (queue->rear + 1) % N;  
8.     queue->data[queue->rear] = x;  
9.   
10.     return 0;  
11. }  

7、出队

[cpp] view plain copy

1. int DeQueue(sequeue_t *queue, data_t *x)  
2. {  
3.     if (NULL == queue) return -1;  
4.   
5.     if (1 == EmptySequeue(queue)) return -1; /* empty */  
6.   
7.     queue->front = (queue->front + 1) % N;  
8.   
9.     if (NULL != x) {  
10.         *x = queue->data[queue->front];  
11.     }  
12.   
13.     return 0;  
14. }  

数据结构之队列(C实现)

博客分类： 
• C

数据结构 队列实现 静态队列 基于数组队列的实现 

一、队列是什么

    队列是一种可以实现“先进先出”的存储结构。其实，说简单点，队列就是排队，跟我们日常生活中到银行取钱排队，排队打饭在道理上是一样的。

    队列通常可以分为两种类型：
       ①链式队列（由链表实现）。
       ②静态队列（由数组实现），静态队列通常都必须是循环队列。
    由于链式队列跟链表差不多，所以在这里只针对循环队列来说明并实践。
    循环队列的两个参数：
       ①front,front指向队列的第一个元素。
       ②rear,rear指向队列的最后一个有效元素的下一元素。
    队列的两个基本操作：出队和入队。

二、队列的结构

    下面是一个循环队列（基于数组实现）的结构图：

    

三、队列的操作

      入队（尾部入队） 
            ①将值存入rear所代表的位置。
            ②rear = (rear+1)%数组的长度。
      出队（头部出队） 
            front = (front+1)%数组的长度。
      队列是否为空   
            front和rear的值相等，则该队列就一定为空。
      队列是否已满
            注意：循环队列中，有n个位置，通常放n-1个值，空1个
                    在循环队列中，front和rear指向的值不相关，无规律。front可能比rear指向的值大，也可能比rear指向的值小，也可能两者相等。
            算法：
            ①多增加一个标识参数。
            ②少用一个元素，rear和front指向的值紧挨着，则队列已满。

四、队列的实现

    基于数组的循环队列的具体实现

C代码  

1. <span style="font-size: small;">#include<stdio.h>  
2. #include<malloc.h>        //包含了malloc函数  
3. /* 
4.  *循环队列，用数组实现 
5.  */  
6. //队列结构体定义  
7. typedef struct Queue  
8. {  
9.     int * pBase;    //用于动态分配内存,pBase保存数组的首地址  
10.     int front;      //指向头结点  
11.     int rear;       //指向最后一个元素的下一结点  
12. } QUEUE;  
13. //函数声明  
14. void initQueue(QUEUE * pQueue);                 //队列初始化的函数  
15. bool isEmpty(QUEUE * pQueue);                   //判断队列是否为空的函数  
16. bool isFull(QUEUE * pQueue);                    //判断队列是否满的函数  
17. bool enQueue(QUEUE * pQueue, int value);        //入队的函数   
18. bool outQueue(QUEUE * pQueue, int * pValue);    //出队的函数,同时保存出队的元素  
19. void traverseQueue(QUEUE * pQueue);             //遍历队列的函数  
20. /* 
21.  *主程序 
22.  */  
23. int main(void)  
24. {  
25.     int value;          //用于保存出队的元素  
26.     //创建队列对象  
27.     QUEUE queue;  
28.     //调用初始化队列的函数  
29.     initQueue(&queue);  
30.     //调用出队函数  
31.     enQueue(&queue, 1);  
32.     enQueue(&queue, 2);  
33.     enQueue(&queue, 3);  
34.     enQueue(&queue, 4);  
35.     enQueue(&queue, 5);  
36.     enQueue(&queue, 6);  
37.     enQueue(&queue, 7);  
38.     enQueue(&queue, 8);  
39.     //调用遍历队列的函数  
40.     traverseQueue(&queue);  
41.     //调用出队函数  
42.     if(outQueue(&queue, &value))  
43.     {  
44.         printf("出队一次，元素为：%d\n", value);  
45.     }  
46.     traverseQueue(&queue);  
47.     if(outQueue(&queue, &value))  
48.     {  
49.         printf("出队一次，元素为：%d\n", value);  
50.     }  
51.     traverseQueue(&queue);  
52.     getchar();  
53.     return 0;  
54. }  
55. /* 
56.  *初始化函数的实现 
57.  */  
58. void initQueue(QUEUE * pQueue)  
59. {  
60.     //分配内存  
61.     pQueue->pBase = (int *)malloc(sizeof(int) * 6);          //分配6个int型所占的空间  
62.     pQueue->front = 0;       //初始化时，front和rear值均为0  
63.     pQueue->rear = 0;  
64.     return;  
65. }  
66. /* 
67.  *入队函数的实现 
68.  */  
69. bool enQueue(QUEUE * pQueue, int value)  
70. {  
71.     if(isFull(pQueue))  
72.     {  
73.         printf("队列已满,不能再插入元素了!\n");  
74.         return false;  
75.     }  
76.     else  
77.     {  
78.         //向队列中添加新元素  
79.         pQueue->pBase[pQueue->rear] = value;  
80.         //将rear赋予新的合适的值  
81.         pQueue->rear = (pQueue->rear+1) % 6;  
82.         return true;  
83.     }  
84. }  
85. /* 
86.  *出队函数的实现 
87.  */  
88. bool outQueue(QUEUE * pQueue, int * pValue)  
89. {  
90.     //如果队列为空,则返回false  
91.     if(isEmpty(pQueue))  
92.     {  
93.         printf("队列为空，出队失败!\n");  
94.         return false;  
95.     }  
96.     else  
97.     {  
98.         *pValue = pQueue->pBase[pQueue->front];       //先进先出  
99.         pQueue->front = (pQueue->front+1) % 6;      //移到下一位置  
100.         return true;  
101.     }  
102. }  
103. /* 
104.  *遍历队列的函数实现 
105.  */  
106. void traverseQueue(QUEUE * pQueue)  
107. {  
108.     int i = pQueue->front;           //从头开始遍历  
109.     printf("遍历队列：\n");  
110.     while(i != pQueue->rear)     //如果没有到达rear位置，就循环  
111.     {  
112.         printf("%d  ", pQueue->pBase[i]);  
113.         i = (i+1) % 6;              //移到下一位置  
114.     }     
115.     printf("\n");  
116.     return;  
117. }  
118. /* 
119.  *判断队列是否满的函数的实现 
120.  */  
121. bool isFull(QUEUE * pQueue)  
122. {  
123.     if((pQueue->rear+1) % 6 == pQueue->front)     //队列满  
124.         return true;  
125.     else  
126.         return false;  
127. }  
128. /* 
129.  *判断队列是否为空函数的实现 
130.  */  
131. bool isEmpty(QUEUE * pQueue)  
132. {  
133.     if(pQueue->front == pQueue->rear)  
134.         return true;  
135.     else  
136.         return false;  
137. }</span>  

五、队列的应用

     在我们去打饭的时候总要排队，排队是与时间有关的，排在前面的人多，我们打到饭用的时间就比较长，相反，如果前面的排队的人相对较少，我们能打到饭的用的时间也就相对较短，所以说，队列总是与时间相关的。可以肯定地说：任何与时间相关的操作，基本上都会牵扯到队列。

六、结语

      最后再声明一下：附件中的工程是在Visual Studio 2010 中建的。