2.7 队列的链式存储

2.7.1 链队列的定义

链队列：队列的链存储。

2.7.2 链队列的实现方式

实现方式：不带头结点和带头结点，一般带头结点比不带头结点好

注：这两种方式：类型描述相同，初始化和判空不同

​ 入队，不带头节点要对第一个特殊处理

​ 出队，取队头元素不一样，不带头节点是Q.front，带头结点是Q.front->next，因为链队以链头为队头

2.7.3 不带头结点的链队列上的操作

链队列的类型描述

typedef struct LNode{    //定义单链表结点类型
	ElemType data;            //数据域，可以是别的各种数据类型，本文统一用int类型
	struct LNode *next;  //指针域
}LNode;
typedef struct{
    LNode *front, *rear;
}LinkQueue;

初始化

//初始化一个队列
bool InitQueue(LinkQueue &Q){
    //初始时，front, rear都指向NULL
	Q.front = NULL;
    Q.rear = NULL;
	return true;
}

判空

//判空
bool StackEmpty(LinkQueue S){
    if(Q.front == NULL){  //队列已空
        return true;
    }else{
        return false;
    }
}

入队

//入队
void EnQueue(LinkQueue &Q,Elemtype e){
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;		  //e为队尾元素
    s->next = NULL;
    //对第一个特殊处理
    if(Q.front == NULL){
        Q.front = s;
        Q.rear = s;
    }
    Q.rear->next = s;     //新结点插入到rear后
    Q.rear s;             //队尾指针后移
}

出队

//出队
bool DeQueue(LinkQueue &Q,Elemtype &e){
	if(Q.rear == NULL) return false;
	LNode *p = Q.front;
    e = p->data;          //e为队头元素
    Q.front = p->next;	  //队头指针后移
    if(Q.rear == p){      //最后一个结点出队
        Q.front = NULL;
        Q.rear = NULL;
    }
    free(p);
    return true;
}

获取队头元素

//获取队头元素
bool GetHead(SqQueue &Q,Elemtype &e){
	if(Q.rear == Q.front) return false;
	e = Q.data[Q.front];   //e为队列顶元素
    return true;
}

2.7.4 带头结点的链队列上的操作

链队列的类型描述

typedef struct LNode{    //定义单链表结点类型
	ElemType data;            //数据域，可以是别的各种数据类型，本文统一用int类型
	struct LNode *next;  //指针域
}LNode;
typedef struct{
    LNode *front, *rear;
}LinkQueue;

初始化

//初始化一个队列
bool InitQueue(LinkQueue &Q){
    ////初始时，front, rear都指向头结点
	Q.front = Q.rear = (LNode *)malloc(sizeof(LNode));
	Q.front = Q.rear = NULL;
	return true;
}

判空

//判空
bool StackEmpty(SqStack S){
    if(Q.rear == Q.front){  //队列已空
        return true;
    }else{
        return false;
    }
}
//或
//判空
bool StackEmpty(SqStack S){
    if(Q.front->next == NULL){  //队列已空
        return true;
    }else{
        return false;
    }
}

入队（循环队列）

//入队
void EnQueue(LinkQueue &Q,Elemtype e){
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;		  //e为队尾元素
    s->next = NULL;
    Q->rear->next = s;    //新结点插入到rear后
    Q.rear s;             //队尾指针后移
}

出队

//出队
bool DeQueue(LinkQueue &Q,Elemtype &e){
	if(Q.rear == NULL) return false;
	LNode *p = Q.front->next;
    e = p->data;          //e为队头元素
    Q.front->next = p->next;	  //队头指针后移
    if(Q.rear == p){      //最后一个结点出队
        Q.front = Q.rear;
    }
    free(p);
    return true;
}

2.7.5 队列已满

链队一般不会队满