线性结构笔记（三）

（三）队列（先入先出，后入后出）

1.队列的顺序存储

定义（定义一个结构体，里面有个可以指向数组的指针）

typedef int Position;
typedef struct QNode * PtrToQNode;
struct QNode
{
    ElementType * Data;
    /*int 类型指针可以指向 int 数组*/
    Position Front, Rear;
    int MaxSize;
    /*MaxSize 是数组元素的个数*/
};
typedef PtrToQNode 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);
    //为什么 Q->Front 不用对 Q->MaxSize 取整？
    //因为 Q->Front 肯定是小于 Q->MaxSize 的，而 Q->Rear+1 可能是大于 Q->MaxSize 的。 
}

加入队列

bool AddQ(Queue Q, ElementType X)
{
    if(IsFull)
    {
        printf("队列已满\n");
        return false;
    }
    else
    {
        Q->Rear = (Q->Rear+1) % Q->MaxSize;
        //如果到了末尾并且数组没满就加到数组的头部
        //对 Q->MaxSize 取余可以使 Q->Rear+1 等于 Q->MaxSize 时，Q->Rear 变成0。
        //就是可以从尾巴跑到开头
        Q->Data[Q->Rear] = X;
        return true;
    }
}

判断队列是否为空（一开始 Front 和 Rear 都等于0，队列为空；删除元素 Rear-1，最后也会导致 Front 等于 Rear；但是不会因为添加元素导致两者相等，以为当 Rear 在 Front 前一个的时候，就认为队列满了，就不能添加元素了，所以 Front==Rear 时队列肯定为空）
1
2
3
4
bool IsEmpty(Queue Q)
{
return (Q->Front == Q->Rear);
}

删除队列头（对 Front（队列头）而不是 Rear（队列尾）操作）

ElementType DeleteQ(Queue Q)
{
    if(IsEmpty)
    {
        printf("队列为空\n");
        return ERROR;
    }
    else
    {
        Q->Front = (Q->Front+1) % Q->MaxSize;
        return Q->Data[Q->Front];
    }
}

总结：队列是在头删除，在尾添加，而堆栈的删除和添加都是在尾部进行的。因为在头部删除，所以可能Rear到了尾部而前面还有空间，这种情况下利用循环队列可以更好的利用数组空间。循环数组的关键就是利用了取余操作。

2.队列的链式存储

定义

typedef struct Node * PtrToNode;
struct Node
{
    /*队列中的结点*/
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode Position;
typedef struct QNode * PtrToQNode;
struct QNode
{
    Position Front, Rear;
    int MaxSize;
};
typedef PtrToQNode Queue;

判断队列是否为空

bool IsEmpty(Queue Q)
{
    return (Q->Front==NULL);
}

入队

Queue AddQ(Queue Q, ElementType X)
{
    Position temp;
    temp = (PtrToQNode)malloc(sizeof(struct Node));
    temp->Data = X;
    temp->Next = NULL;
    if(IsEmpty)
    /*如果添加的是第一个结点，需要将 Front 和 Rear 都指向该结点；否则对 Rear 操作即可。*/
    {
        Q->Front = temp;
        Q->Rear = temp;
    }
    else
    {
        Q->Rear->Next = temp;
        Q->Rear = temp;
    }
    return Q;
}

出队

ElementType DeleteQ(Queue Q)
{
    Position temp;
    ElementType data;
    if(IsEmpty)
    {
        printf("队列为空\n");
        return ERROR;
    }
    else
    {
        temp = Q->Front;
        /*如果只有一个结点，那么删除之后 Front 和 Rear 都要变成 NULL；否则 Front 指向第二个结点，释放第一个结点，返回第一个结点的数据*/
        if(Q->Front == Q->Rear)
            Q->Front = Q->Rear = NULL;
        else
            Q->Front = temp->Next;
        data = temp->Data;
        free(temp);
        return data;
    }
}

总结：队列的链式存储需要两种结构体，一种是队列的结构体，一种是结点的结构体。添加在尾部进行，删除在头部进行。

（三）队列（先入先出，后入后出）

1.队列的顺序存储

2.队列的链式存储