队列——链式存储

核心思路：

1、首先定义队列结点，包含数据域和指针域；然后定义链式队列，包含队列节点类型的队头和队尾指针。 2、初始化： 　　　　带头结点：给头结点分配内存，然后队头和队尾指针指向头结点，同时队头指针的next指向NULL。 　　　　不带头结点：队头和队尾指针都指向NULL。 3、入队： 　　　　带头结点：先给入队节点分配内存，然后将新节点插入到队尾指针后面，新节点的下一个节点为NULL,最后将队尾指针指向新结点。 　　　　不带头结点：先给入队节点分配内存 ，如果队列为空 ，队头和队尾结点都指向新节点，否则将新节点插入到队尾指针后面,最后将队尾指针指向新结点。 4、出队： 　　　　带头结点：首先判断队列是否为空，然后定义指针p指向队头指针的下一个结点，如果这是最后一个结点，则front=rear ，最后释放p的内存。 　　　　不带头结点：首先判断队列是否为空， 然后定义指针p指向队头指针指向的结点，如果这是最后一个结点，则front=NULL,rear=NULL ，最后释放p的内存。

代码：

#include<stdio.h>
#include<stdlib.h>

//定义 
typedef struct LinkNode{        //队列结点 
    int data;
    struct LinkNode *next;
}LinkNode;
typedef struct{        //链式队列 
    LinkNode *rear,*front;
}LinkQueue;

//初始化——带头结点 
void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next=NULL; 
} 

//初始化——不带头结点 
void InitQueue_(LinkQueue &Q){
    Q.front=NULL;
    Q.rear=NULL;
} 

//入队——带头结点 
bool EnQueue(LinkQueue &Q,int x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));    //给新节点分配内存 
    s->data=x; 
    s->next=NULL;
    Q.rear->next=s;        //新节点插入到尾指针后面 
    Q.rear=s;     //尾指针指向新插入的结点 
    return true;
} 

//入队——不带头结点 
bool EnQueue_(LinkQueue &Q,int 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;        
        Q.rear=s;
    }
    return true;
} 

//出队——带头结点
bool DeQueue(LinkQueue &Q,int &x){
    if(Q.front==Q.rear)        //首先判断队空 
        return false;
    
    LinkNode *p=Q.front->next;    
    x=p->data;
    Q.front->next=p->next;
    
    if(Q.rear==p){    //这是最后一个结点 
        Q.rear=Q.front; 
    }
    free(p);
    return true; 
} 

//出队——不带头结点
bool DeQueue_(LinkQueue &Q,int &x){
    if(Q.front==NULL)        //首先判断队空 
        return false;
    
    LinkNode *p=Q.front;    //不带头结点时头指针指向队头元素 
    x=p->data;
    Q.front=p->next;
    
    if(Q.rear==p){    //这是最后一个结点 
        Q.rear=NULL;
        Q.front=NULL; 
    }
    free(p);
    return true; 
} 

//队列的链式存储一般不会出现队满的情况，除非内存不足 

int main(){
    
}