数据结构-线性结构之队列

什么是队列

• 队列(Queue)：具有一定操作约束的线性表
• 插入和删除操作：只能在一端插入，而在另一端删除。

数据插入：入队列（AddQ）
数据删除： 出队列（DeleteQ）
先来先服务
先进先出

队列的抽象数据类型描述

类型名称：队列(Queue)
数据对象集：一个有0个或多个元素的有穷线性表。
操作集：长度为MaxSize的队列Q  Queue，队列元素item  ElementType
1、Queue CreatQueue( int MaxSize )：生成长度为MaxSize的空队列；
2、int IsFullQ( Queue Q, int MaxSize )：判断队列Q是否已满；
3、void AddQ( Queue Q, ElementType item )： 将数据元素item插入队列Q中；
4、int IsEmptyQ( Queue Q )： 判断队列Q是否为空；
5、ElementType DeleteQ( Queue Q )：将队头数据元素从队列中删除并返回。

队列的顺序存储实现（数组）

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。

#define MaxSize <储存数据元素的最大个数>
struct QNode {
          ElementType Data[ MaxSize ];
          int rear;
          int front;
};
typedef struct QNode *Queue;

1. 入队列

Front和rear指针的移动采用“加1取余”法，体现了顺序存储的“循环使用”。

void AddQ( Queue PtrQ, ElementType item)
{
    if ( (PtrQ->rear+1) % MaxSize == PtrQ->front ) 
    {
        printf(“队列满”);
        return;
    }
    PtrQ->rear = (PtrQ->rear+1)% MaxSize;
    PtrQ->Data[PtrQ->rear] = item;
}

2. 出队列

ElementType DeleteQ ( Queue PtrQ )
{
     if ( PtrQ->front == PtrQ->rear ) 
     {
         printf(“队列空”);
         return ERROR;
     } 
     else 
     {
          PtrQ->front = (PtrQ->front+1)% MaxSize;
          return PtrQ->Data[PtrQ->front];
     }
} 

队列的链式存储实现

队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行；

struct Node{
       ElementType Data;
       struct Node *Next;
};
struct QNode{ /* 链队列结构 */
      struct Node *rear; /* 指向队尾结点 */
      struct Node *front; /* 指向队头结点 */
};
typedef struct QNode *Queue;
Queue PtrQ;

- 出队（不带头结点的链式队列）

ElementType DeleteQ ( Queue PtrQ )
{ 
     struct Node *FrontCell;
     ElementType FrontElem;
     if ( PtrQ->front == NULL) 
     {
         printf(“队列空”); return ERROR;
     }
     FrontCell = PtrQ->front;
     if ( PtrQ->front == PtrQ->rear) /* 若队列只有一个元素 */
         PtrQ->front = PtrQ->rear = NULL; /* 删除后队列置为空 */
     else
         PtrQ->front = PtrQ->front->Next;
     FrontElem = FrontCell->Data;
     free( FrontCell ); /* 释放被删除结点空间 */
     return FrontElem;
}