队列的顺序和链式存储实现

队列（Queue）：具有一定操作约束的线性表

1. 插入和删除操作：只能在一端插入，而在另一端删除。

 

类型名称：队列（Queue）

数据对象集：一个有0个或多个元素的有穷线性表

操作集：长度为MaxSize的队列Q € Queue，队列元素item € ElementType

1. Queue CreateQueue(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;


//入队列
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;
}



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

 队列的链式存储实现：

　　　　　　队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行：队列指针fron指向尾、trear指向头

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;   
}