队列链式实现

链式存储实现的队列：链队列

typedef struct LinkNode{             //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;


typedef struct{                     //链式队列
    LinkNode *front,*rear;//队列的队头和队尾指针
}LinkQueue;

带头结点：

不带头结点：

一、初始化：

1.初始化（带头结点）：

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


//初始化队列(带头结点)
void InitQueue(LinkQueue &Q){
    //初始时front、rear都指向头结点
    Q.front=Q.rear=( LinkNode*)malloc(sizeof(LinkNode) ) ;
    Q.front->next=NULL;
}

void testLinkQueue( ){
    LinkQueue Q;       //声明一个队列
    InitQueue(Q);       //初始化队列
//...后续操作...
}

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

//判断队列是否为空
bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear)
       return true;
    else
       return false;
}

2.初始化（不带头结点）：

//初始化队列(不带头结点)
void InitQueue(LinkQueue &Q){
    //初始时front、rear都指向NULL
    Q.front=NULL;
    Q.rear=NULL;
}

//判断队列是否为空(不带头结点)
bool IsEmpty(LinkQueue Q){
    if(Q.front==NULL)
       return true;
    else
       return false;
}

二、入队操作：

1.入队（带头结点）：

//新元素入队（带头结点)
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof( LinkNode) ) ;
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;        //新结点插入到rear之后
    Q.rear=s;              //修改表尾指针
}

step1:

step2:

step3:  

step4:  

step5:  

2.入队（不带头结点）：

//新元素入队(不带头结点)
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=( LinkNode *)malloc(sizeof ( LinkNode) ) ;s->data=x;
    s->next=NULL;
    if (Q.front == NULL){         //在空队列中插入第一个元素
       Q.front = s;               //修改队头、队尾指针
       Q.rear=s;
}else {
       Q.rear->next=s;           //新结点插入到rear结点之后
       Q.rear=s;                 //修改rear指针
    }
}

三、出队操作：

1.出队（带头结点）：

//队头元素出队(不带头结点)
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear)
       return false;        //空队
    LinkNode *p=Q.front->next;
    x=p->data;             //用变量x返回队头元素
    Q.front->next=p->next;       //修改头结点的next指针
    if(Q.rear==p)                //此次时最后一个结点出队
       Q.rear=Q.front;          //修改real指针
    free(p);                    //释放结点空间
    return true;
}

tips：若p是最后一个结点还需要修改表为指针，让它指向头结点。

如图：

 2.出队（不带头结点）：

//队头元素出队(不带头结点)
bool DeQueue(LinkQueue &Q,ElemType&x){
    if(Q.front==NULL)
       return false;                //空队
    LinkNode *p=Q.front;            //p指向此次出队的结点
    x=p->data;                      //用变量x返回队头元素
    Q.front=p->next;               //修改front指针
    if(Q.rear==p){                 //此次是最后一个结点出队
       Q.front = NULL;             //front指向NULL
       Q.rear = NULL;              //rear指向NULL
}
free(p);                          //释放结点空间
return true;
}

四、队列满的情况：

顺序存储———预分配的空间耗尽时队满
链式存储———一般不会队满，除非内存不足