队列知识总结

Julia999

队列
定义：
      一种可以实现‘先进先出’的存储结构（只允许在一端进行插入操作，在另一端进行删除操作的线性表）
分类：
       链式队列---用链表实现
       静态队列---用数组实现
             静态队列通常必须是循环队列
             循环队列：
             1.静态队列为什么一定是循环队列
             2.循环队列需要几个参数来确定及其含义
                     2个参数   front 和rear
             3.循环队列各个参数的含义
             2个参数在不同场合有不同的定义
                         1）队列初始化：front和rear的值都是0
                         2）队列非空：
                                  front代表的是队列的第一个元素
                                  rear代表的是队列的最后一个有效元素的下一个元素
                         3）队列空
                                   front和rear的值相等，但不一定都是0

             4.循环队列的入队伪算法                    （如果刚开始的时候front和rear在相同的位置，那么说明这是一个空队列，那么如果需要将元素入队，那么就将元素放在front所在的位置，然后rear向后移动一个元素位置）
                    1.将值存入r所代表的位置
                    2.r=r+1;  //这样写肯定是错误的
                       正确的写法是:r=(r+1)%数组的长度
             5.循环队列的出队伪算法
                    f=(f+1)%数组的长度


             6.如何判断循环队列是否为空
                    如果front和rear的值相等，该队列一定为空


             7.如何判断循环队列是否已满
             预备知识：
             front和rear的值之间没有什么规定的谁比谁大的关系
             两种方式：【通常用第二种方式】
                   1.多增加一个标识参数
                   2.少用一个元素（如果r和f紧挨着，那么队列已满）
                   if((r+1)%数组的长度==f)
                          已满
                   else
                          不满

           队列算法
                 入队
                 出队
           队列的具体应用：
                 所有和时间有关的操作都与队列都有队列的影子

1. #include<stdio.h>
   
2. #include<mallloc.h>
   
3. 
   
4. typedef struct Queue
   
5. {
   
6.         int *pBase;
   
7.         int front;
   
8.         int rear;
   
9. 
   
10. }QUEUE;
    
11. 
    
12. void init(QUEUE *pQ)
    
13. {
    
14.         *pQ->pBase(int *)malloc(sizeof(int)*6); //指向了一个24字节的数组
    
15.         pQ->front=0;
    
16.         pQ->rear=0;
    
17. }
    
18. 
    
19. bool en_queue(QUEUE *pQ,int val)
    
20. {
    
21.         if(full_queue(pQ))   //入队失败
    
22.                 return false;
    
23.         else
    
24.         {
    
25.                 pQ->pBase[pQ->rear]=val;
    
26.                 pQ->rear=(pQ->rear+1)%6;
    
27. 
    
28.                 return true;
    
29.         }
    
30. 
    
31. }
    
32. 
    
33. bool full_queue(QUEUE *pQ)
    
34. {
    
35.         if((pQ->rear+1)%6==pQ->front)
    
36.                 return true;
    
37.         else
    
38.                 return false;
    
39. }
    
40. 
    
41. void traverse_queue(QUEUE *pQ)
    
42. {
    
43.         int i=pQ->front;
    
44.         while(i!=pQ->rear)
    
45.         {
    
46.                 printf("%d ",pQ->pBase[i]);
    
47.                 i=(i+1)%6;  //i不断往后移
    
48.         }
    
49.         printf("\n");
    
50. }
    
51. 
    
52. bool out_queue(QUEUE *pQ,int *pVal)  //出队
    
53. {
    
54.         if(empty_queue(pQ))
    
55.         {
    
56.                 return false;
    
57.         }
    
58.         else
    
59.         {
    
60.                 *pVal=pQ->pBase[pQ->front];
    
61.                 pQ->front=(pQ->front+1）%6;
    
62.                 return true;
    
63.         }
    
64. }
    
65. 
    
66. bool empty_queue(QUEUE *pQ)
    
67. {
    
68.         if(pQ->front==pQ->rear)
    
69.                 return true;
    
70.         else
    
71.                 return false;
    
72. }
    
73. int main()
    
74. {
    
75.         Queue Q;
    
76.         inti(&Q);
    
77.         int val;
    
78.         en_queue(&Q,1);
    
79.         en_queue(&Q,2);
    
80.         en_queue(&Q,3);
    
81.         en_queue(&Q,4);
    
82.         en_queue(&Q,5);
    
83.         en_queue(&Q,6);
    
84. 
    
85.         traverse_queue(&Q);
    
86.         if(out_queue(&Q,&val))
    
87.                 printf("出队成功，队列出队的元素是：%d\n",val);
    
88.         else
    
89.                 printf("出队失败！");
    
90. 
    
91.         return 0;
    
92. }
    
93. 
    

复制代码

                        
链队列
我们将队头指针指向链队列的头结点，而队尾指针指向终端结点（头结点不是必要的，但是为了方便操作，我们加上了）
空对列的时候，front和rear都指向头结点

创建一个队列需要完成两个任务：
1.在内存中创建一个头结点
2.将队列的头指针和尾指针都指向这个生成的头结点，因为此时是空队列