## 链队列—— Linked Queue

### 一、链队列的定义

`链队列`：队列的`链存储`。

### 二、链队列的实现方式

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

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

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

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

### 三、不带头结点的链队列上的操作

#### 链队列的类型描述

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

#### 初始化

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

#### 判空

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

#### 入队

```c
//入队
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;             //队尾指针后移
}
```

#### 出队

```c
//出队
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;
}
```

#### 获取队头元素

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

### 四、带头结点的链队列上的操作

#### 链队列的类型描述

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

#### 初始化

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

#### 判空

```c
//判空
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;
    }
}
```

#### 入队（循环队列）

```c
//入队
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;             //队尾指针后移
}
```

#### 出队

```c
//出队
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;
}
```

### 五、队列已满

链队一般不会队满