【数据结构】「队列」（顺序队列、链式队列、双端队列）-EW帮帮网

- 第 112篇 -
Date: 2025 - 07 - 20
Author: 郑龙浩（仟墨）

队列（Queue）

1 基本介绍

1.1 定义

队列（Queue）是一种先进先出（FIFO, First-In-First-Out）的线性数据结构，只允许在队尾插入（入队）、在队头删除（出队）

1.2 栈与队列的区别

栈是只允许一端进行插入或删除的线性表 –> 所以后进先出（在栈顶进行插入删除）
队列是只允许在一端进行插入，在另一端删除的线性表 –> 所以先进先出（在队尾插入，队头删除）
先进先出：FIFO（First In First Out)

1.3 重要术语

队头、队尾、空队尾

队头：允许删除的一端

队尾：允许插入的一端

空队尾：没有任何元素的队列

2 基本操作

初始化：InitQueue(*Q)
清空：ClearQueue(*Q)
销毁：DestroyQueue(*Q)
入队：EnQueue(*Q, ElemType x)
出队：DeQueue(*Q, ElelType* x)
读取队头元素：GetHeadQueue(*Q, ElemType* x)
判断是否为空：IsEmpty(*Q)
判断是否已满：IsFull(Queue *Q)（只有顺序队列有这个）
队列长度：QueueLength(Queue *Q)
打印：PrintQueue(*Q)

3 顺序队列(循环版本)

两种版本

有好几个版本

注意：只有带size或tag参数的队列结构不需要浪费空间，即浪费最后一个存储单元，不带这俩参数的版本，如果不空出最后一个存储单元，就无法通过 rear == fron 判断出来：是满？是空？

当空出一个存储单元的时候就可以判断出是满还是空了

所以如果不带size或tag参数就必然要浪费一个存储单元，但是从整的结构来说，这样反而节省了空间，因为带了size或者tag的参数，每个节点都会多个变量，所以实际上来说，并没节省。

版本1 - 指向指向队尾元素的下一个位置（即队尾后边）

版本1.1 - rear 指向队尾后边且结构中无size或tag参数
- 必须空出最后一个存储单元
- 初始化时，各参数默认为：
  - front = 0
  - rear = 0
- 队空条件：front == rear
- 队满条件：(rar + 1) % MaxSize == front
版本1.2 - raer 指向队尾后边且结构中有size参数
- 不需要空出任何存储单元
- 初始化时，各参数默认为：
  - front = 0
  - rear = 0
  - size = 0
- 可以直接通过size判断队列的状态
- 队空条件：size = 0
- 队满条件：size == MaxSize
版本1.3 - rear 指向队尾后边且结构中有tag参数
- 不需要空出任何存储单元
- 初始化时，各参数默认为：
  - front = 0
  - rear = 0
  - tag= 0（初始化相当于上一次操作出队）
- 通过tag标记出最后一次操作是入队还是出队（0是出队，1是入队）
- 队空条件：front == rear && tag == 0（如果上一次操作是出队tag==0，出现front == rear 就是队空）
- 队满条件：front == rear && tag == 1（如果上一次操作是入队tag==1，出现front == raer 就是队满

版本2 - rear 指向队尾元素

版本2.1 - rear 指向队尾且结构中无size或tag参数
- 必须空出最后一个存储单元
- 初始化时，各参数默认为：
  - front = 0
  - rear = -1
- 队空条件：(rear + 1) % MaxSize == front
- 队满条件：(rear + 2) % MaxSize == front
版本2.2 - rear 指向队尾且结构中有size参数
- 不需要空出存储单元
- 初始化时，各参数默认为：
  - front = 0
  - rear = -1
  - size = 0
- 通过size变量直接判断队列的状态
- 队空条件：size == 0
- 队满条件：size == MaxSize
版本2.3 - rear 指向队尾且结构中有tag参数
- 不需要空出存储单元
- 初始化时，各参数默认为：
  - front = 0
  - rear = -1
  - tag= 0（初始化相当于上一次操作出队）
- 通过tag标记出最后一次操作是出队还是入队（0是出队，1是入队）
- 队空条件：front == (rear + 1) % MaxSize && tag == 0
- 队满条件：front == (rear + 1) % MaxSize && tag == 1

两种版本区别

版本1：rear 指向队尾的下一个位置

front 指向队头元素，rear 指向下一个可插入的位置。队列长度计算为 (rear - front + MaxSize) % MaxSize，队空条件是 front == rear，队满条件是 (rear + 1) % MaxSize == front。此版本逻辑清晰，计算简单，是最常用的实现方式。

版本2：rear 指向队尾元素

front 指向队头元素，rear 直接指向队尾元素。队列长度计算为 (rear - front + 1 + MaxSize) % MaxSize，队空条件是 (rear + 1) % MaxSize == front，队满条件是 (rear + 2) % MaxSize == front。此版本需要额外调整计算，容易出错，一般不建议使用。

版本1.1 - rear指向队尾后边且无 size 或 tag

先进先出 -> 队尾进，队头出

队头指针：front 指向队头元素

队尾指针：rear 指向队尾元素的后一个位置
必须知道：即使是顺序队列，队头指针也不可能一直指向data[0]

初始化后，如果一直入队操作，队头指针肯定是一直指向0的，但是如果执行了出队操作，那么队头指针会指向1，再执行出队操作，会指向2… –> 现在的front指向2，队头元素是data[2]

假设此时队尾指针指向的是MaxSize-1，然后进行入队操作，执行完入队以后，队尾指针不会指向MaxSize而是0，

也就是要将线性的结构转换为一个环形的、循环的结构，方法如下：
Q->rear = (Q->rear + 1) % MaxSize
也就是当rear指向线性结构的末尾的时候要从头开始

因为现在的data[0]和data[1]都是空的并且访问data[MaxSize]会越界（因为数组索引是0~MaxSize），所以rear要指向0，如果再入队操作，在data[0]的位置会存储一个值，然后rear指向1，此时仅有一个data[1]还未存储数据

注意了！！！！

那么这个位置是否可以存储数据呢？

答案是否定的，我们必须牺牲一个元素在队列的末尾，原因如下：
因为判断队列是否为空以及初始化的时候都是front == rear

如果真的在执行一次入队操作，队尾元素会是data[1]，而rear指向了2，

那么此时的front和rear都同时指向2，那么我到底是将这种情况归为满队，还是空队呢，所以为了避免这种情况的发生，统一约定：
队列的最后一个位置要空出来（牺牲一个存储单元）
队列已满的条件：rear下一个位置是front，即
(Q->rear + 1) % MaxSize == Q->front
队列为空的条件：
Q->front == Q->rear
使用模运算将线状的存储空间在逻辑上变成了环状

SeqQueue.h

#pragma once
#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"
#define MaxSize 10
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize]; // 静态数组存放元素
	int front, rear; // 队头指针 队尾指针
}SeqQueue;

// 初始化
void InitQueue(SeqQueue* Q);

// 销毁队列
void DestroyQueue(SeqQueue* Q);

// 清空队列
void ClearQueue(SeqQueue* Q);

// 判断队列是否为空
bool IsEmpty(SeqQueue* Q);

// 入队
bool EnQueue(SeqQueue* Q, ElemType x);

// 出队
bool DeQueue(SeqQueue* Q, ElemType* x);

// 读取队头元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x);

// 判断队列是否已满
bool IsFull(SeqQueue* Q);

// 队列长度
int QueueLength(SeqQueue* Q);

// 打印
void PrintQueue(SeqQueue* Q);

SeqQueue.c

#include "sequence_queue.h"
#include "stdio.h"
#include "stdlib.h"

// 初始化
void InitQueue(SeqQueue* Q) {
	// 队头 == 队尾 且都 指向0
	Q->rear = Q->front = 0;
}

// 销毁队列
void DestroyQueue(SeqQueue* Q) {
	Q->front = Q->rear = 0;
}

// 清空队列
void ClearQueue(SeqQueue* Q) {
	Q->front = Q->rear = 0;
}

// 判断队列是否为空
bool IsEmpty(SeqQueue* Q) {
	return Q->front == Q->rear;
}

// 入队
bool EnQueue(SeqQueue* Q, ElemType x) {
	if (IsFull(Q)) return false; // 队列已满，不能入队
	Q->data[Q->rear] = x;
	Q->rear = (Q->rear + 1) % MaxSize; // 队尾指针要一直保持在 0 ~ MaxSize-1之间
	return true; // 入队成功
}

// 出队
bool DeQueue(SeqQueue* Q, ElemType* x) {
	if (IsEmpty(Q)) return false; // 空队列不能删除
	*x = Q->data[Q->front];
	Q->front = (Q->front + 1) % MaxSize;
	return true;
}

// 读取队头元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x) {
	if (IsEmpty(Q)) return false;
	*x = Q->data[Q->front];
	return true;
}

// 判断队列是否已满
bool IsFull(SeqQueue* Q) {
	return (Q->rear + 1) % MaxSize == Q->front;
}

// 队列长度
int QueueLength(SeqQueue* Q) {
	return (Q->rear - Q->front + MaxSize) % MaxSize;
}

// 打印
void PrintQueue(SeqQueue* Q) {
	if (IsEmpty(Q)) {
		printf("队列为空\n");
		return;
	}
	printf("队头 --> ");
	int cur = Q->front; // 遍历下标
	while (cur != Q->rear) {
		printf("%d -> ", Q->data[cur]);
		cur = (cur + 1) % MaxSize;
	}
	printf("队尾\n");
}

版本1.2 - rear指向队尾后边且有 size

SeqQueue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MaxSize 10
typedef int ElemType;

typedef struct {
    ElemType data[MaxSize]; // 静态数组存放元素
    int front, rear;        // 队头指针和队尾指针
    int size;               // 队列当前长度
} SeqQueue;

// 初始化队列
void InitQueue(SeqQueue* Q);

// 销毁队列
void DestroyQueue(SeqQueue* Q);

// 清空队列
void ClearQueue(SeqQueue* Q);

// 判断队列是否为空
bool IsEmpty(SeqQueue* Q);

// 判断队列是否已满
bool IsFull(SeqQueue* Q);

// 入队
bool EnQueue(SeqQueue* Q, ElemType x);

// 出队
bool DeQueue(SeqQueue* Q, ElemType* x);

// 读取队头元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x);

// 获取队列长度
int QueueLength(SeqQueue* Q);

// 打印队列
void PrintQueue(SeqQueue* Q);

SeqQueue.c

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MaxSize 10
typedef int ElemType;

typedef struct {
    ElemType data[MaxSize]; // 静态数组存放元素
    int front, rear;        // 队头指针和队尾指针
    int size;               // 队列当前长度
} SeqQueue;

// 初始化队列
void InitQueue(SeqQueue* Q) {
    Q->front = Q->rear = 0;
    Q->size = 0;
}

// 销毁队列
void DestroyQueue(SeqQueue* Q) {
    Q->front = Q->rear = 0;
    Q->size = 0;
}

// 清空队列
void ClearQueue(SeqQueue* Q) {
    Q->front = Q->rear = 0;
    Q->size = 0;
}

// 判断队列是否为空
bool IsEmpty(SeqQueue* Q) {
    return Q->size == 0;
}

// 判断队列是否已满
bool IsFull(SeqQueue* Q) {
    return Q->size == MaxSize;
}

// 入队
bool EnQueue(SeqQueue* Q, ElemType x) {
    if (IsFull(Q)) return false;
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MaxSize;
    Q->size++;
    return true;
}

// 出队
bool DeQueue(SeqQueue* Q, ElemType* x) {
    if (IsEmpty(Q)) return false;
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MaxSize;
    Q->size--;
    return true;
}

// 读取队头元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x) {
    if (IsEmpty(Q)) return false;
    *x = Q->data[Q->front];
    return true;
}

// 获取队列长度
int QueueLength(SeqQueue* Q) {
    return Q->size;
}

// 打印队列
void PrintQueue(SeqQueue* Q) {
    if (IsEmpty(Q)) {
        printf("队列为空\n");
        return;
    }
    printf("队头 --> ");
    int cur = Q->front;
    for (int i = 0; i < Q->size; i++) {
        printf("%d -> ", Q->data[cur]);
        cur = (cur + 1) % MaxSize;
    }
    printf("队尾\n");
}

版本1.3 - rear指向队尾后边且有 tag

SeqQueue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MaxSize 10
typedef int ElemType;

typedef struct {
    ElemType data[MaxSize]; // 静态数组存放元素
    int front, rear;        // 队头指针和队尾指针
    bool tag;               // 最近操作标记: true为入队, false为出队
} SeqQueue;

// 初始化队列
void InitQueue(SeqQueue* Q);

// 销毁队列
void DestroyQueue(SeqQueue* Q);

// 清空队列
void ClearQueue(SeqQueue* Q);

// 判断队列是否为空
bool IsEmpty(SeqQueue* Q);

// 判断队列是否已满
bool IsFull(SeqQueue* Q);

// 入队
bool EnQueue(SeqQueue* Q, ElemType x);

// 出队
bool DeQueue(SeqQueue* Q, ElemType* x);

// 读取队头元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x);

// 获取队列长度
int QueueLength(SeqQueue* Q);

// 打印队列
void PrintQueue(SeqQueue* Q);

SeqQueue.c

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MaxSize 10
typedef int ElemType;

typedef struct {
    ElemType data[MaxSize]; // 静态数组存放元素
    int front, rear;        // 队头指针和队尾指针
    bool tag;               // 最近操作标记: true为入队, false为出队
} SeqQueue;

// 初始化队列
void InitQueue(SeqQueue* Q) {
    Q->front = Q->rear = 0;
    Q->tag = false;
}

// 销毁队列
void DestroyQueue(SeqQueue* Q) {
    Q->front = Q->rear = 0;
    Q->tag = false;
}

// 清空队列
void ClearQueue(SeqQueue* Q) {
    Q->front = Q->rear = 0;
    Q->tag = false;
}

// 判断队列是否为空
bool IsEmpty(SeqQueue* Q) {
    return Q->front == Q->rear && Q->tag == false;
}

// 判断队列是否已满
bool IsFull(SeqQueue* Q) {
    return Q->front == Q->rear && Q->tag == true;
}

// 入队
bool EnQueue(SeqQueue* Q, ElemType x) {
    if (IsFull(Q)) return false;
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MaxSize;
    Q->tag = true;
    return true;
}

// 出队
bool DeQueue(SeqQueue* Q, ElemType* x) {
    if (IsEmpty(Q)) return false;
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MaxSize;
    Q->tag = false;
    return true;
}

// 读取队头元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x) {
    if (IsEmpty(Q)) return false;
    *x = Q->data[Q->front];
    return true;
}

// 获取队列长度
int QueueLength(SeqQueue* Q) {
    if (IsFull(Q)) return MaxSize;
    return (Q->rear - Q->front + MaxSize) % MaxSize;
}

// 打印队列
void PrintQueue(SeqQueue* Q) {
    if (IsEmpty(Q)) {
        printf("队列为空\n");
        return;
    }
    printf("队头 --> ");
    int cur = Q->front;
    int count = QueueLength(Q);
    for (int i = 0; i < count; i++) {
        printf("%d -> ", Q->data[cur]);
        cur = (cur + 1) % MaxSize;
    }
    printf("队尾\n");
}

4 链式队列

4.1 两种版本区别

函数/操作	带头结点版本	不带头结点版本
初始化队列	创建头结点，`front/rear`指向头结点	`front/rear`初始化为`NULL`
入队操作	直接插入到`rear->next`	需先判断是否为空队列再插入
出队操作	删除`front->next`结点	直接删除`front`结点
判断队列空	检查`front == rear`	检查`front == NULL`
获取队头元素	访问`front->next->data`	访问`front->data`
清空队列	释放所有数据结点，保留头结点	释放所有结点
销毁队列	释放头结点和队列结构体	直接释放队列结构体
队列长度	从`front->next`开始计数	从`front`开始计数
打印队列	从`front->next`开始打印	从`front`开始打印
内存方面	多占用1个头结点空间	不多占用

4.2 链式队列_带头结点

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

typedef int ElemType;
// 结点结构
typedef struct LinkNode {
    ElemType data;
    struct LinkNode* next;
}LinkNode;

// 链式队列结构
typedef struct LinkQueue {
    LinkNode *front, *rear;
}LinkQueue;


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

typedef int ElemType;

// 结点结构
typedef struct LinkNode {
    ElemType data;
    struct LinkNode* next;
} LinkNode;

// 链式队列结构
typedef struct LinkQueue {
    LinkNode *front, *rear;
} LinkQueue;

// 函数声明
// 初始化
void InitQueue(LinkQueue* Q);
// 清空
void ClearQueue(LinkQueue* Q);
// 销毁
void DestroyQueue(LinkQueue** Q);
// 入队
bool EnQueue(LinkQueue* Q, ElemType x);
// 出队
bool DeQueue(LinkQueue* Q, ElemType* x);
// 判断队空
bool IsEmpty(LinkQueue* Q);
// 读取队头元素
bool GetHead(LinkQueue* Q, ElemType* x);
// 队列长度
int QueueLength(LinkQueue* Q);
// 打印
void PrintQueue(LinkQueue* Q);


// 函数实现
// 初始化（带头结点）
void InitQueue(LinkQueue* Q) {
    Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q->front->next = NULL; // Q->fornt 是头结点 再加->next是第一个结点
}

// 清空（带头结点）
void ClearQueue(LinkQueue* Q) {
    LinkNode* cur = Q->front->next;
    // 释放所有结点
    while (cur != NULL) {
        LinkNode* temp = cur;
        cur=cur->next;
        free(temp);
    }
    Q->rear = Q->front = NULL; // 将头指针和尾指针指向头结点并且置空
}

// 销毁（带头结点）销毁要用二级指针
void DestroyQueue(LinkQueue** Q) {
    ClearQueue(*Q);
    // 释放头结点
    free((*Q)->front);// 此时头尾指针指向头结点，释放谁都一样
    // 释放队列结构
    free(*Q);
    Q = NULL;
}

// 入队（带头结点） 
bool EnQueue(LinkQueue* Q, ElemType x) {
    LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));
    if (!NewNode) return false; // 申请内存失败返回false
    NewNode->data = x; // 新结点存储值
    NewNode->next = NULL; // 新结点（最后一个结点）的后驱是NULL
    Q->rear->next = NewNode; // 新结点插入到rear后边
    Q->rear = NewNode; // rear指向刚刚插入的元素
    return true;
}

// 出队（带头结点）
bool DeQueue(LinkQueue* Q, ElemType* x) {
    if (IsEmpty(Q)) return false; // 空队列无法出队
    LinkNode* first = Q->front->next; // 将队列第一个存储单元（要删除的单元）位置保存下来，以防将头结点的后继连接到第二个存储单元后，第一个存储单元的位置丢失
    *x = first->data; // 将队列第一个数据读取出来
    Q->front->next = first->next; // 将头结点后继连接到第二个存储单元--> 这样第一个存储单元地址就不会保存在队列当中了，也就相当于删除了，或者出队
    // 如果只有一个存储结点的话，那么rear队尾指针指向的就是第一个存储单元，当把这最后一个存储单元删除的时候rear就不该指向这个“已经删除的结点”了，而应该指向“头结点”，相当于初始化了
    if (Q->rear == first) Q->rear = Q->front;
    free(first);
    return true;
}

// 判断队空（带头结点）
bool IsEmpty(LinkQueue* Q) {
    return Q->front == Q->rear;
}

// 读取队头元素
bool GetHead(LinkQueue* Q, ElemType* x) {
    if (IsEmpty(Q)) return false; // 空队
    *x = Q->front->next->data;
    return true;
}

// 队列长度（带头结点）
int QueueLength(LinkQueue* Q) {
    if (IsEmpty(Q)) return 0;
    LinkNode* cur = Q->front->next; // 从第一个存储结点开始
    int len = 0;
    while (cur != NULL) {
        len++;
        cur = cur->next;
    }
    return len;
}

// 打印（带头结点）
void PrintQueue(LinkQueue* Q) {
    LinkNode* cur = Q->front->next; // 从第一个存储结点开始
    printf("队头 -> ");
    while (cur != NULL) {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("队尾\n");
}
int main(void) {
    return 0;
}

4.3 链式队列_无头结点

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

typedef int ElemType;
// 结点结构
typedef struct LinkNode {
    ElemType data;
    struct LinkNode* next;
}LinkNode;

// 链式队列结构
typedef struct LinkQueue {
    LinkNode *front, *rear;
}LinkQueue;


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

typedef int ElemType;

// 结点结构
typedef struct LinkNode {
    ElemType data;
    struct LinkNode* next;
} LinkNode;

// 链式队列结构
typedef struct LinkQueue {
    LinkNode *front, *rear;
} LinkQueue;

// 函数声明
// 初始化
void InitQueue(LinkQueue* Q);
// 清空
void ClearQueue(LinkQueue* Q);
// 销毁
void DestroyQueue(LinkQueue** Q);
// 入队
bool EnQueue(LinkQueue* Q, ElemType x);
// 出队
bool DeQueue(LinkQueue* Q, ElemType* x);
// 判断队空
bool IsEmpty(LinkQueue* Q);
// 读取队头元素
bool GetHead(LinkQueue* Q, ElemType* x);
// 队列长度
int QueueLength(LinkQueue* Q);
// 打印
void PrintQueue(LinkQueue* Q);


// 函数实现
// 初始化（无头结点）
void InitQueue(LinkQueue* Q) {
   // 初始化时，头尾都指向NULL
   Q->front = Q->rear = NULL;
}

// 清空（无头结点）
void ClearQueue(LinkQueue* Q) {
    LinkNode* cur = Q->front;
    // 释放所有结点
    while (cur != NULL) {
        LinkNode* temp = cur;
        cur=cur->next;
        free(temp);
    }
    Q->rear = Q->front = NULL; // 将头指针和尾指针指向NULL
}

// 销毁（无头结点）应使用二级指针-->因为销毁后要将Q置空
void DestroyQueue(LinkQueue** Q) {
    ClearQueue(*Q); // 清空
    // 释放队列结构
    free(*Q);
    Q = NULL; // 给Q置空
}

// 入队（无头结点） 
bool EnQueue(LinkQueue* Q, ElemType x) {
    // 有头节点的时候入队不需要额外判断是否为空队，因为头尾指针此时都是指向的头结点，操作相同的
    LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));
    if (!NewNode) return false; // 申请内存失败返回false
    NewNode->data = x; // 新结点存储值
    NewNode->next = NULL; // 新结点（最后一个结点）的后驱是NULL

    // 一句：空队修改队尾队头，不是空队列只修改尾指针
    if (IsEmpty(Q)) {
        // 更新队头队尾指针
        Q->front = NewNode; // 如果是空队列，因为没有头结点的存在，所以要将这个新的结点放到第一个结点的位置，而Q->front就是指的第一个结点（如果有头结点的话，指的是头结点，而Q->front->next指的是第一个结点）
        Q->rear = NewNode; // 更新尾指针：rear指向刚刚插入的元素
        
    } else { // 当不是空队的时候-
        Q->rear->next = NewNode; // 新结点插入到rear后边
        Q->rear = NewNode; // 更新尾指针：rear指向刚刚插入的元素
    }
    
    return true;
}

// 出队（无头结点）
bool DeQueue(LinkQueue* Q, ElemType* x) {
    if (IsEmpty(Q)) return false; // 空队列无法出队
    LinkNode* First = Q->front; // 将队列第一个存储单元（要删除的单元）位置保存下来，以防第二个结点变为第一个结点地址后，第一个结点地址无法释放
    *x = First->data; // 将队列第一个数据读取出来
    

    // 注意：如果是只有一个结点，执行出队的话，要改变队尾队头指针指向，因为当是空队的时候队头队尾指针都要指向NULL
    if (Q->rear == First) {
        Q->front = NULL;
        Q->rear = NULL;
    } else { // 当有多个结点的时候，只需要改变队头指向即可
        Q->front = First->next; // 将第一个结点改为原第二个结点
    }
    // 别忘了：释放原来第一个结点
    free(First); // 释放原第一个结点
    return true;
}

// 判断队空
bool IsEmpty(LinkQueue* Q) {
    return Q->front == NULL; // 当是空队列的时候头指针指向NULL
}

// 读取队头元素（无头结点）
bool GetHead(LinkQueue* Q, ElemType* x) {
    if (IsEmpty(Q)) return false; // 空队
    *x = Q->front->data;
    return true;
}

// 队列长度（无头结点）
int QueueLength(LinkQueue* Q) {
    if (IsEmpty(Q)) return 0;
    LinkNode* cur = Q->front; // 从第一个结点开始
    int len = 0;
    while (cur != NULL) {
        len++;
        cur = cur->next;
    }
    return len;
}

// 打印（无头结点）
void PrintQueue(LinkQueue* Q) {
    LinkNode* cur = Q->front; // 从第一个结点开始
    printf("队头 -> ");
    while (cur != NULL) {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("队尾\n");
}
int main(void) {
    return 0;
}

5 双端队列

除了顺序队列和链式队列以外，还有一种队列叫做双端队列

首先，先来将栈、普通队列与双端队列比较一下，都为线性表

栈：只允许从一端插入删除
普通队列：只允许从一端插入，只允许从另一端删除
双端队列：只允许从两端插入或删除 –> 队头队尾都可以插入和删除
- 输入受限的双端队列：允许一端插入删除；另一端只能允许插入 –> 队头只能删除，队尾既可以插入和删除
- 输出受限的双端队列：允许一端插入删除；另一端只能允许删除 –> 队头可以插入和删除，队尾只能插入

【数据结构】「队列」（顺序队列、链式队列、双端队列）

文章目录

队列（Queue）

1 基本介绍

1.1 定义

1.2 栈与队列的区别

1.3 重要术语

2 基本操作

3 顺序队列(循环版本)

两种版本

两种版本区别

版本1.1 - rear指向队尾后边且无 size 或 tag

SeqQueue.h

SeqQueue.c

版本1.2 - rear指向队尾后边且有 size

SeqQueue.h

SeqQueue.c

版本1.3 - rear指向队尾后边且有 tag

SeqQueue.h

SeqQueue.c

4 链式队列

4.1 两种版本区别

4.2 链式队列_带头结点

4.3 链式队列_无头结点

5 双端队列

网站公告

今日签到

热门文章

最新发布

【数据结构】「队列」（顺序队列、链式队列、双端队列）

文章目录

队列（Queue）

1 基本介绍

1.1 定义

1.2 栈 与 队列的区别

1.3 重要术语

2 基本操作

3 顺序队列(循环版本)

两种版本

两种版本区别

版本1.1 - rear指向队尾后边 且 无 size 或 tag

SeqQueue.h

SeqQueue.c

版本1.2 - rear指向队尾后边 且 有 size

SeqQueue.h

SeqQueue.c

版本1.3 - rear指向队尾后边 且 有 tag

SeqQueue.h

SeqQueue.c

4 链式队列

4.1 两种版本区别

4.2 链式队列_带头结点

4.3 链式队列_无头结点

5 双端队列

网站公告

今日签到

热门文章

最新发布

1.2 栈与队列的区别

版本1.1 - rear指向队尾后边且无 size 或 tag

版本1.2 - rear指向队尾后边且有 size

版本1.3 - rear指向队尾后边且有 tag