浅谈数据结构之顺序队列(五)

　　队列：是指只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出的线性表，这与栈的后进先出正好相反；其中允许插入的一端我们称为队尾，允许删除的一端我们称为队头(或队首)。假设队列Q=(a1,a2,......an)，那么a1就是队头元素，an就是队尾元素；我们删除数据时，总是从队头元素a1开始，而插入数据时，则是从队尾元素an后面开始插入，这也比较符合我们生活中的习惯，排在第一的当然优先出列，后来的当然排在队伍的后面。

　　线性表有顺序存储和链式存储，栈是线性表，所以也有这两种存储方式。同样的，队列作为一种特殊的线性表，也有这两种存储方式。下面，我们先来看看队列的顺序存储结构。

　　我们假设一个队列有n个元素，则顺序存储的队列需要建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元中，数组下标为0的一端即为队首。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此它的时间复杂度为0(1)。与栈不同的是，队列元素的出队列在队头，这也就意味着，队列中所有元素都得向前移动，以保证队列队头元素不为空，即数组下标为0的位置不为空，此时的时间复杂度为0(n)。在现实中也是如此，比如说一群人在排队买票，前面的人买好了票就离开，后面的人则向前一步，补上前面的空位。

　　通常我们为了避免当只有一个元素时，队头与队尾重合使操作变得麻烦，所以引入了两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front=rear时，此队列不是只剩下一个元素，而是一个空队列。若设队列的长度为QueueSize，则通用的计算队列的长度公式为：(rear-front+QueueSize)%QueueSize。接下来我们重点看一下队列的插入、删除等操作是怎样实现的，具体操作源程序代码如下所示：

  1 #include <stdio.h>
  2 #include <stdlib.h> 
  3 
  4 #define OK 1
  5 #define ERROR 0
  6 #define TRUE 1
  7 #define FALSE 0
  8 
  9 #define MAXSIZE 10                /* 存储空间初始分配量 */
 10 
 11 typedef int Status; 
 12 typedef int QElemType;             /* QElemType类型根据实际情况而定，这里假设为int */
 13 
 14 /* 循环队列的顺序存储结构 */
 15 typedef struct
 16 {
 17     QElemType data[MAXSIZE];
 18     int front;                   /* 头指针 */
 19     int rear;                    /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
 20 }SqQueue;
 21 
 22 Status visit(QElemType c)
 23 {
 24     printf("%d ",c);
 25     return OK;
 26 }
 27 
 28 /* 初始化一个空队列Q */
 29 Status InitQueue(SqQueue *Q)
 30 {
 31     Q->front=0;
 32     Q->rear=0;
 33     return  OK;
 34 }
 35 
 36 /* 将Q清为空队列 */
 37 Status ClearQueue(SqQueue *Q)
 38 {
 39     Q->front=Q->rear=0;
 40     return OK;
 41 }
 42 
 43 /* 返回Q的元素个数，也就是队列的当前长度 */
 44 int QueueLength(SqQueue Q)
 45 {
 46     return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
 47 }
 48 
 49 /* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
 50 Status GetHead(SqQueue Q,QElemType *e)
 51 {
 52     if(Q.front==Q.rear)     /* 队列空 */
 53         return ERROR;
 54     *e=Q.data[Q.front];
 55     return OK;
 56 }
 57 
 58 /* 若队列未满，则插入元素e为Q新的队尾元素 */
 59 Status EnQueue(SqQueue *Q,QElemType e)
 60 {
 61     if ((Q->rear+1)%MAXSIZE == Q->front)    /* 队列满的判断 */
 62         return ERROR;
 63     Q->data[Q->rear]=e;                     /* 将元素e赋值给队尾 */
 64     Q->rear=(Q->rear+1)%MAXSIZE;            /* rear指针向后移一位置， */
 65                                             /* 若到最后则转到数组头部 */
 66     return  OK;
 67 }
 68 
 69 /* 若队列不空，则删除Q中队头元素，用e返回其值 */
 70 Status DeQueue(SqQueue *Q,QElemType *e)
 71 {
 72     if (Q->front == Q->rear)                /* 队列空的判断 */
 73         return ERROR;
 74     *e=Q->data[Q->front];                   /* 将队头元素赋值给e */
 75     Q->front=(Q->front+1)%MAXSIZE;          /* front指针向后移一位置， */
 76                                             /* 若到最后则转到数组头部 */
 77     return  OK;
 78 }
 79 
 80 /* 从队头到队尾依次对队列Q中每个元素输出 */
 81 Status QueueTraverse(SqQueue Q)
 82 { 
 83     int i;
 84     i=Q.front;
 85     while((i+Q.front)!=Q.rear)
 86     {
 87         visit(Q.data[i]);
 88         i=(i+1)%MAXSIZE;
 89     }
 90     printf("
");
 91     return OK;
 92 }
 93 
 94 int main()
 95 {    
 96     SqQueue Q;
 97     QElemType e;
 98     Status i;
 99     int j,k=0;
100 
101     i=InitQueue(&Q);
102     printf("1.初始化队列Q后，队列Q的长度为：Q.length=%d
",QueueLength(Q));
103     
104     printf("2.请输入整型队列元素(不超过%d个),-1为提前结束符: 
",MAXSIZE-1);
105     do
106     {
107         e=k+10;
108         if(e==-1)
109             break;
110         k++;
111         EnQueue(&Q,e);
112     }while(k<MAXSIZE-1);
113     
114     printf("3.连续%d次由队头删除元素,队尾插入元素:
",MAXSIZE);
115     for(j=1;j<=MAXSIZE;j++)
116     {
117         DeQueue(&Q,&e);
118         printf("删除的元素是%d,插入的元素:%d 
",e,j+100);
119         e=j+100;
120         EnQueue(&Q,e);
121     }
122 
123     printf("4.现在队列中的元素为: 
");
124     QueueTraverse(Q);
125     
126     printf("5.现在队列Q的长度为：Q.length=%d
",QueueLength(Q));
127  
128     DeQueue(&Q,&e);
129     printf("6.在队列Q的队头处删除元素后：Q.data=");
130     QueueTraverse(Q); 
131     
132     GetHead(Q,&e);
133     printf("7.现在队列Q的队头元素是：%d
",e); 
134      
135     i=ClearQueue(&Q);
136     printf("8.将队列Q清空后，队列Q的长度为：Q.length=%d
",QueueLength(Q));
137      
138     return 0;
139 }