队列

1.队列

简单的理解，队列是只允许在一端进行插入，在另外一端删除的线性表

2.队列的基本操作

InitQueue(&Q)：初始化队列。构造一个队列，分配内存空间。
DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间
EnQueue(&Q,x)：入队，若队列Q未满，则将x加入栈中成为新的队尾
DeQueue(&Q,&x)：出队，若队列Q非空，则将队头元素付给x
GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x

3.队列顺序实现

初始化

#define MaxSize 10
typedef struct
{
    ElemType data[MaxSize];
    int front,rear;      //队头指针和队尾指针
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q)
{
    Q.rear=Q.front=0;
}

入队

bool EnQueue(SqQueue &Q,ElemType x)
{
    if((Q.rear+1)%MaxSize==front)
        return false;
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;   //队尾指针加一取模
    return true;
}

出队

bool DeQueue(SqQueue &Q,ElemType &x)
{
    if(Q.rear==Q.front)
        return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

队列元素个数

(rear+MaxSize-front)%MaxSize

4.队列链式实现

使用链式存储方式实现的队列，实现后插和头删的单链表

typedef struct LinkNode
{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct
{
    LinkNode *front,*rear;
}LinkQueue;

初始化

void InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

入队

void EnQueue(LinkQueue &Q,ElemType x)
{
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

出队

bool DeQueue(LinkQueue &Q,ElemType &x)
{
    if(Q.front==NULL)
        return false;
    LinkNode *p=Q.front;
    x=p->data;
    Q.front=p->next;
    if(Q.rear==p)
    {
        Q.front=NULL;
        Q.rear=NULL;
    }
    free(p);
    return true;
}