3.2 队列

3.2.1 队列的定义及其基本运算

前面所讲的栈是一种后进先出的数据结构，而在实际问题中还经常使用一种“先进先出”（First-In First-Out，FIFO）的数据结构：即插入在表一端进行，而删除在表的另一端进行，这种数据结构被称为队或队列（Queue），允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。如图3.7所示是一个有5个元素的队列。

入队的顺序依次为a1、a2、a3、a4、a5，出队时的顺序将依然是a1、a2、a3、a4、a5。

图3.7 队列示意图

显然，队列也是一种运算受限制的线性表，所以又叫先进先出表，简称FIFO表。在日常生活中队列的例子很多，如排队买东西，排前面的买完后走掉，新来的排在队尾。

在队列上进行的基本操作有以下几种。

（1）列初始化：Init_Queue(q)。

初始条件：队列q不存在。

操作结果：构造了一个空队列。

（2）入队操作：In_Queue(q, x)。

初始条件：队列q存在。

操作结果：对已存在的队列q，插入一个元素x到队尾，队列发生变化。

（3）出队操作：Out_Queue(q, x)。

初始条件：队列q存在且非空。

操作结果：删除队首元素，并返回其值，队列发生变化。

（4）读队头元素：Front_Queue(q, x)。

初始条件：队列q存在且非空。

操作结果：读队头元素，并返回其值，队列不变。

（5）判队空操作：Empty_Queue(q)。

初始条件：队列q存在。

操作结果：若q为空队列则返回为1，否则返回为0。

3.2.2 队列的存储结构和基本运算的实现

与线性表、栈类似，队列也有顺序存储和链式存储两种存储方法。

1.顺序队

顺序存储的队列称为顺序队。因为队列的队头和队尾都是活动的，因此，除了队列的数据区外还有队头、队尾两个指针。顺序队的类型定义如下：

define MAXSIZE  100                /*队列的最大容量*/
typedef struct
      { datatype  data[MAXSIZE];   /*队列的存储空间*/
        int rear，front;           /*队头队尾指针*/
      } SeQueue;

定义一个指向顺序队的指针变量：

SeQueue *sq;

申请一个顺序队的存储空间，可使用C语言的存储空间申请函数malloc，如下：

sq=malloc( sizeof ( SeQueue ) ) ;

队列的数据存储区为：

sq ->data[0] ~ sq ->data[MAXSIZE-1]

队头指针为：

sq ->front

队尾指针为：

sq ->rear

设队头指针指向队头元素前面一个位置，队尾指针指向队尾元素（这样的设置是为了某些运算的方便，并不是唯一的方法）。则置队列为空，可用以下语句设置：

sq ->front=sq ->rear=-1;

在不考虑溢出的情况下，入队操作队尾指针加1，指向新位置后，元素入队。操作如下：

sq ->rear++ ;
sq ->data[sq ->rear]=x;         /*将新元素x置入队尾*/

在不考虑队空的情况下，出队操作队头指针加1，表明队头元素出队。操作如下：

sq ->front++;
x=sq->data [sq->front];         /*原队头元素送x中*/

队中元素的个数可以通过两个指针的差来计算：

m=(sq -> rear) - (q ->front ) ;

显然，队满时m= MAXSIZE；队空时m=0。

按照上述思想建立的空队、入队、出队过程如图3.8所示，设MAXSIZE=10。

图3.8 队列操作示意图

从图3.8中可以看到，随着入队出队的进行，会使整个队列整体向后移动，这样就出现了图3.8（d）中的现象：队尾指针已经移到了最后，再有元素入队就会出现溢出，而事实上此时队中并未真的“满员”，这种现象为“假溢出”，这是由“队尾入队头出”这种受限制的操作所造成。解决假溢出的方法之一是将队列的数据区data[0..MAXSIZE-1]看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队列”，其示意图如图3.9所示。

图3.9 循环队列示意图

因为是头尾相接的循环结构，入队时的队尾指针加1操作修改为：

sq ->rear=(sq ->rear+1) % MAXSIZE;

出队时的队头指针加1操作修改为：

sq ->front=(sq ->front+1) % MAXSIZE;

设MAXSIZE=10，图3.10是对循环队列进行操作的示意图。

从图3.10所示的循环队列可以看出，图3.10（a）中具有a5，a6，a7，a8共4个元素，此时front=4，rear=8，随着a9～a14相继入队，队中具有10个元素——队满，此时front=4，rear=4，如图3.10（b）所示，可见在队满情况下有front== rear。若在图3.10（a）情况下，a5～a8相继出队，此时队空，front=8，rear=8，如图3.10（c）所示，即在队空情况下也有front== rear。也就是说，“队满”和“队空”的条件是相同的了。这显然是必须要解决的一个问题。

图3.10 对循环队列进行操作的示意图

方法一：设一个存储队列中数据元素个数的变量，如num。当num== 0时队空，当num== MAXSIZE时为队满。

方法二：少用一个元素空间，把图3.10（d）所示的情况视为队满，此时的状态是队尾指针加1就会从后面赶上队头指针，这种情况下队满的条件是：(rear+1) % MAXSIZE== front，也能和队空区别开。下面的循环队列及操作按方法一实现。循环队列的类型定义及基本运算如下：

typedef struct { datatype data[MAXSIZE];     /*数据的存储区*/
                 int front, rear;            /*队头队尾指针*/
                 int num;                    /*队中元素的个数*/
               } c_SeQueue;                  /*循环队列*/

（1）置空队。

c_SeQueue* Init_SeQueue( )
             { q=malloc (sizeof (c_SeQueue));
               q ->front=q ->rear=-1;  q->num=0;
               return  q;
}

（2）入队。

int  In_SeQueue ( c_SeQueue *q , datatype x)
    { if ( num==MAXSIZE )
        { printf ("队满");  return – 1;     /*队满不能入队*/
         }
        else { q ->rear=(q ->rear+1) % MAXSIZE;
               q ->data[q ->rear]=x;    num++ ;
               return 1;                    /*入队完成*/
             }
}

（3）出队。

int  Out_SeQueue (c_SeQueue *q , datatype *x)
   { if ( num==0 )
        { printf ("队空")；
          return – 1;                     /*队空不能出队*/
        }
       else { q->front=(q->front+1) % MAXSIZE;
              *x=q->data[q ->front];      /*读出队头元素*/
              num - -;
              return  1;                  /*出队完成*/
}
}

（4）判队空。

int  Empty_SeQueue ( c_SeQueue *q )
    { if (num==0) return 1;
       else return 0;
    }

2.链队列

链式存储的队称为链队列。和链栈类似，链队列可以用单链表来实现，根据队的FIFO原则，为了操作上的方便，可以分别设置一个头指针和一个尾指针，如图3.11所示。

图3.11 链队示意图

图3.11中头指针front和尾指针rear是两个独立的指针变量，从结构性上考虑，通常将二者封装在一个结构中。

链队列的定义如下：

typedef struct node
    { datatype  data ;
      struct node next ;
    } QNode;          /*链队列结点的类型*/
typedef struct
    {  QNode  *front, *rear;
      } LQueue;        /*将头尾指针封装在一起的链队*/

定义一个指向链队列的指针：

LQueue *q ;

按这种思想建立的带头结点的链队列如图3.12所示。

图3.12 头尾指针封装在一起的链队列

链队列的基本运算如下所述。

（1）创建一个带头结点的空队。

LQueue *Init_LQueue( )
     { LQueue *q, *p;
       q=malloc (sizeof(LQueue));      /*申请头尾指针结点*/
       p=malloc (sizeof(QNode));       /*申请链队头结点*/
       p ->next=NULL;
       q ->front=p; q->rear=p;
       return q;
}

（2）入队。

void In_LQueue(LQueue *q , datatype x)
    { QNode *p;
      p=malloc(sizeof (QNode));     /*申请新结点*/
      p ->data=x;  p ->next=NULL;
      q ->rear ->next=p;
      q ->rear=p;
}

（3）判队空。

int Empty_LQueue( LQueue *q)
   { if (q ->front==q->rear)  return 0;
     else return 1;
}

（4）出队。

int Out_LQueue(LQueue *q , datatype *x)
   { QNode *p;
     if (Empty_LQueue(q) )
     { printf ("队空")；
        return 0;                 /*队空，出队失败*/
     }
     else
         { p=q ->front ->next;
           q->front ->next=p ->next;
           *x=p ->data;           /*队头元素放x中*/
           free ( p );
           if (q ->front ->next== NULL)  q ->rear=q ->front;
                    /*只有一个元素时，出队后队空，此时还需要修改队尾指针，参考图3.12(c)*/
           return 1;
           }
    }

3.2.3 队列应用举例

【例3.4】 队列管理的模拟算法（队列采用带头结点的链表结构）。

用键盘输入数据来模拟队列操作，采用如下管理模式：

（1）队列初始化为空队列；

（2）键盘输入奇数时，奇数从队尾入队列；

（3）键盘输入偶数时，队头指针指向的奇数出队列；

（4）键盘输入0时，退出算法；

（5）每输入一个整数，显示操作后队列中的值。

void outlinkqueue (LQueue *q)
    {                /*显示队列q中所有元素的值*/
       QNode *p；
       p=q ->front;
       printf("Queue：")；
       while (p!= q->rear)
           { p=p ->next；
            printf ("%d"，p->data);
           }
        printf("＼n")；
      }
   main( )
   { LQueue lq，*p;
       int j ;
       p=&lq；
       Init_ LQueue( p )；
       printf ("Input a integer: ");
       scanf ("%d"，&j)；
       while ( j != 0 )
          { if ( j % 2==1)
             In_ LQueue ( p，j );      /*输入奇数：奇数入队列*/
            else
             j=Out_ LQueue ( p )；     /*输入偶数：队头奇数出队列*/      outlinkqueue ( p )；
             printf("＼n Input a integer: " );
             scanf ("%d"，&j )；
          }
       }
上一章目录下一章