队列的链式存储

队列的链式存储

1.初始化

#include<stdio.h>
typedef struct LinkNode{
    
    ElemType data;
    struct LinkNode *next;
}LinkNode;

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

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

}

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

2.是否为空

bool isEmpty(LinkQueue Q){
    
    if(Q.rear==Q.front)
        return true;
    else
        return false;

}

3.不带头结点初始化队列

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

}

4.不带头结点判空

bool isEmpty(LinkQueue Q){
    
    if(Q.front==NULL)
        return true;
    else
        return false;

}

5.入队操作（带头结点） 类似于尾插法

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;        //修改表尾指针
    

}

6.入队不带头结点 （可能里面有元素 可能空元素插入 ）

//新元素入队 不带头结点
void EnQueue(LinkQueue &Q,ElemType x){
    
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));  //开辟空间存放新元素
    s->data=x;                                         //插入的值放进新开辟的空间
    s->next=NULL;                                      //新开辟空间指向NULL
    if(Q.front==NULL){
     //说明没有元素 也没有头结点 只有Q.front 和Q.rear 指针
        Q.front=s;
        Q.rear=s;
    }
    else{
    
        Q.rear->next=s;
        Q.rear=s;
    }
        
}

7.出队操作（带头结点）

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

8.不带头结点的出队操作

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;
        Q.rear=NULL;
    }
    free(p);
    
    return true;
}

链式存储不考虑队满的情况