队列

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

• 数据插入：入队
• 数据删除：出队

顺环队列

一个n节点的队列有n+1中情况；1 。。。。N和空，在判断顺换队列空和满的的情况都是front = rear,造成空和慢的情况无法区分

解决方法：

• 使用额外的标记，size或者Tag域

插入元素的时候size加1，在删除元素的时候size - 1，最后判断size的值。

tag域在插入的时候tag设为1，删除的时候tag设为0，判断Tag的状态来判断最后一次的操作是插入还是删除。

队列的线性实现

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

// 构成元素
// 一个一维数组，记录队列头节点位置的变量front，记录尾元素位置的变量rear
#define ERROR -1

typedef int Position;
typedef int ElementType;


struct QNode {
    ElementType *Data;   // 存储元素的数组
    Position Front, Rear;  // 栈头和栈尾指针
    int MaxSize;   // 队列的最大容量
};

typedef struct QNode* Queue;

// 创建一个队列
Queue CreateQueue(int MaxSize)
{
    Queue Q = (Queue)malloc(sizeof(struct QNode*));
    Q->Data = (ElementType*)malloc(MaxSize * sizeof(ElementType));
    Q->Front = Q->Rear = 0;
    Q->MaxSize = MaxSize;
    return Q;
}

// 是否满
bool Isfull(Queue Q)
{
    return ((Q->Rear + 1) % Q->MaxSize == Q->Front);
}

// 向队列中增加数据
bool AddQ(Queue Q,ElementType x)
{
    if (Isfull(Q))
    {
        printf("队列已满\n");
        return false;
    }
    else
    {
        // Front和rear 指针的移动 采用“加1取 余”法，体 现了顺序存储的“循环 使用”。 
        Q->Rear = ((Q->Rear + 1) % Q->MaxSize);
        Q->Data[Q->Rear] = x;
        return true;
    }
}

// 队列是否为空
bool IsEmpty(Queue Q)
{
    return (Q->Front == Q->Rear);
}

// 删除队列中的元素
ElementType DeleteQ(Queue Q)
{
    if (IsEmpty(Q))
    {
        printf("队列已空\n");
        return ERROR;
    }
    else
    {
        Q->Front = (Q->Front + 1) % Q->MaxSize;
        return  Q->Data[Q->Front];
    }
}

队列的链式实现

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

/******************************
*                             *
*   队列的链式实现               *
*                             *
*******************************/

typedef struct Node* ptrToNode;
typedef int ElementType;

struct Node {
    ElementType Data;   // 存储元素的数据
    ptrToNode Next;  // 栈头和栈尾指针
};

typedef ptrToNode Position;

struct QNode {
    Position Front, Rear;  // 队列的头尾指针
    int MaxSize;           // 最大容量
};

typedef struct QNode* Queue;

// 队列是否为空
bool IsEmpty(Queue Q)
{
    return (Q->Front == NULL);
}


// 删除队列中的元素
ElementType DeleteQ(Queue Q)
{
    Position frontCell;
    ElementType frontElem;

    if (IsEmpty(Q))
    {
        printf("队列已空\n");
        return ERROR;
    }
    else
    {
        frontCell = Q->Front;
        if (Q->Front == Q->Rear)   // 若队列中只有一个元素
            Q->Front = Q->Rear = NULL;
        else
            Q->Front = Q->Front->Next;
        frontElem = frontCell->Data;
        free(frontCell);
        return frontElem;
    }
}