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

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

文章目录

  • 队列（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 定义

队列（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) {// 队头 == 队尾 且都 指向0Q->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; // 申请内存失败返回falseNewNode->data = x; // 新结点存储值NewNode->next = NULL; // 新结点（最后一个结点）的后驱是NULLQ->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) {// 初始化时，头尾都指向NULLQ->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; // 申请内存失败返回falseNewNode->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; // 将队列第一个数据读取出来// 注意：如果是只有一个结点，执行出队的话，要改变队尾队头指针指向，因为当是空队的时候队头队尾指针都要指向NULLif (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 双端队列

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

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

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/pingmian/89640.shtml
繁体地址，请注明出处：http://hk.pswp.cn/pingmian/89640.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Java行为型模式---解释器模式

Java行为型模式---解释器模式

解释器模式基础概念解释器模式&#xff08;Interpreter Pattern&#xff09;是一种行为型设计模式&#xff0c;其核心思想是定义一个语言的文法表示&#xff0c;并定义一个解释器&#xff0c;使用该解释器来解释语言中的句子。这种模式将语法解释的责任分开&#xff0c;使得语法…
阅读更多...
[spring6: PointcutAdvisor MethodInterceptor]-简单介绍

[spring6: PointcutAdvisor MethodInterceptor]-简单介绍

Advice Advice 是 AOP 联盟中所有增强&#xff08;通知&#xff09;类型的标记接口&#xff0c;表示可以被织入目标对象的横切逻辑&#xff0c;例如前置通知、后置通知、异常通知、拦截器等。 package org.aopalliance.aop;public interface Advice {}BeforeAdvice 前置通知的标…
阅读更多...
地图定位与导航

地图定位与导航

定位 1.先申请地址权限(大致位置精准位置) module.json5文件 "requestPermissions": [{"name": "ohos.permission.INTERNET" },{"name": "ohos.permission.LOCATION","reason": "$string:app_name",&qu…
阅读更多...
【数据结构】揭秘二叉树与堆--用C语言实现堆

【数据结构】揭秘二叉树与堆--用C语言实现堆

文章目录1.树1.1.树的概念1.2.树的结构1.3.树的相关术语2.二叉树2.1.二叉树的概念2.2.特殊的二叉树2.2.1.满二叉树2.2.2.完全二叉树2.3.二叉树的特性2.4.二叉树的存储结构2.4.1.顺序结构2.4.2.链式结构3.堆3.1.堆的概念3.2.堆的实现3.2.1.堆结构的定义3.2.2.堆的初始化3.2.3.堆…
阅读更多...
区间树：多维数据的高效查询

区间树：多维数据的高效查询

区间树&#xff1a;多维数据的高效查询 大家好&#xff0c;今天我们来探讨一个在计算机科学中非常有趣且实用的数据结构——区间树。想象一下&#xff0c;你是一位城市规划师&#xff0c;需要快速找出某个区域内所有的医院、学校或商场。或者你是一位游戏开发者&#xff0c;需要…
阅读更多...
SQL 魔法：LEFT JOIN 与 MAX 的奇妙组合

SQL 魔法：LEFT JOIN 与 MAX 的奇妙组合

一、引言 在数据库操作的领域中&#xff0c;数据的关联与聚合处理是核心任务之一。LEFT JOIN作为一种常用的连接方式&#xff0c;能够将左表中的所有记录与右表中满足连接条件的记录进行关联&#xff0c;即便右表中没有匹配的记录&#xff0c;左表的记录也会被保留&#xff0c;…
阅读更多...
手写tomcat

手写tomcat

package com.qcby.annotation;import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;Target(ElementType.TYPE)// 表示该注解只能用于类上 Retention(Retentio…
阅读更多...
Android平台下openssl动态库编译

Android平台下openssl动态库编译

1. 下载Linux平台下的NDK软件包 NDK 下载 | Android NDK | Android Developers 下载完成后执行解压命令 # unzip android-ndk-r27d-linux.zip 2. 下载openssl-1.1.1w源码包&#xff0c;并解压 # tar -xzvf openssl-1.1.1w.tar.gz 3. 进入解压后的openssl-1.1.1w目录 …
阅读更多...
【C++基础】面试高频考点解析：extern “C“ 的链接陷阱与真题实战

【C++基础】面试高频考点解析：extern “C“ 的链接陷阱与真题实战

名称修饰&#xff08;Name Mangling&#xff09;是C为支持重载付出的代价&#xff0c;而extern "C"则是跨越语言边界的桥梁——但桥上的陷阱比桥本身更值得警惕 一、extern "C" 的核心概念与高频考点1.1 链接规范与名字改编机制C 为支持函数重载&#xff0…
阅读更多...
OpenCV 官翻 4 - 相机标定与三维重建

OpenCV 官翻 4 - 相机标定与三维重建

文章目录相机标定目标基础原理代码配置校准去畸变1、使用 cv.undistort()2、使用**重映射**方法重投影误差练习姿态估计目标基础渲染立方体极线几何目标基础概念代码练习从立体图像生成深度图目标基础概念代码附加资源练习相机标定 https://docs.opencv.org/4.x/dc/dbb/tutori…
阅读更多...
Python类中方法种类与修饰符详解：从基础到实战

Python类中方法种类与修饰符详解：从基础到实战

文章目录Python类中方法种类与修饰符详解&#xff1a;从基础到实战一、方法类型总览二、各类方法详解1. 实例方法 (Instance Method)2. 类方法 (Class Method)3. 静态方法 (Static Method)4. 抽象方法 (Abstract Method)5. 魔术方法 (Magic Method)三、方法修饰符对比表四、综合…
阅读更多...
VSCode使用Jupyter完整指南配置机器学习环境

VSCode使用Jupyter完整指南配置机器学习环境

接下来开始机器学习部分 第一步配置环境&#xff1a; VSCode使用Jupyter完整指南 1. 安装必要的扩展 打开VSCode&#xff0c;按 CtrlShiftX 打开扩展市场&#xff0c;搜索并安装以下扩展&#xff1a; 必装扩展&#xff1a; Python (Microsoft官方) - Python语言支持Jupyter (Mi…
阅读更多...
数据结构与算法之美：拓扑排序

数据结构与算法之美：拓扑排序

Hello大家好&#xff01;很高兴我们又见面啦&#xff01;给生活添点passion&#xff0c;开始今天的编程之路&#xff01; 我的博客&#xff1a;<但凡. 我的专栏&#xff1a;《编程之路》、《数据结构与算法之美》、《C修炼之路》、《Linux修炼&#xff1a;终端之内 洞悉真理…
阅读更多...
Ubuntu18.04 系统重装记录

Ubuntu18.04 系统重装记录

Ubuntu18.04 系统重装记录 1 安装google拼音 https://blog.csdn.net/weixin_44647619/article/details/144720947 你好&#xff01; 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章&#xff0c;了解一下Markdo…
阅读更多...
Maven常用知识总结

Maven常用知识总结

Maven常用知识总结Maven 安装与配置windows mvn安装与配置IntelliJ IDEA 配置IntelliJ IDEA 配置系统mavenIntellij IDEA Maven使用IntelliJ IDEA 不能运行项目常见问题pom.xml 常用标签讲解parentgroupId artifactId versiondependencypropertiespluginpackagingdependencyMan…
阅读更多...
PHP框架在大规模分布式系统的适用性如何？

PHP框架在大规模分布式系统的适用性如何？

曾几何时&#xff0c;PHP被贴上“只适合小网站”的标签。但在技术飞速发展的今天&#xff0c;PHP框架&#xff08;如Laravel、Symfony、Hyperf、Swoft等&#xff09; 早已脱胎换骨&#xff0c;勇敢地闯入了大规模分布式系统的疆域。今天&#xff0c;我们就来聊聊它的真实战斗力…
阅读更多...
DC-DC降压转换5.5V/3A高效率低静态同步降压转换具有自适应关断功能

DC-DC降压转换5.5V/3A高效率低静态同步降压转换具有自适应关断功能

概述&#xff1a;PC1032是一款高效且体积小巧的同步降压转换器&#xff0c;适用于低输入电压应用。它是紧凑设计的理想解决方案。其2.5V至5.5V的输入电压范围适用于几乎所有电池供电的应用。在中等至重负载范围内&#xff0c;它以1.5MHz&#xff08;典型值&#xff09;的PWM模式…
阅读更多...
min_25筛学习笔记+牛客多校02E

min_25筛学习笔记+牛客多校02E

本来没有学习这种较难的算法的想法的&#xff0c;因为比赛也做不到这种难度的题&#xff0c; 但是最近打牛客多校02&#xff0c;有一题要求 [1,n][1,n][1,n] 中素数的个数&#xff0c;我以为是像莫反一样容斥&#xff0c;但是后面感觉不行。赛后知道是用 min_25 筛来求&#xf…
阅读更多...
FunASR Paraformer-zh：高效中文端到端语音识别方案全解

FunASR Paraformer-zh：高效中文端到端语音识别方案全解

项目简介 FunASR 是阿里巴巴达摩院开源的端到端语音识别工具箱，集成了多种语音识别、语音活动检测（VAD）、说话人识别等模块。其中 paraformer-zh 和 paraformer-zh-streaming 是针对中文语音识别任务优化的端到端模型，分别适用于离线和流式场景。Paraformer 采用并行 Tran…
阅读更多...
数据结构自学Day9: 二叉树的遍历

数据结构自学Day9: 二叉树的遍历

一、二叉树的遍历“遍历”就是按某种规则 依次访问树中的每个节点&#xff0c;确保 每个节点都被访问一次且只访问一次遍历&#xff1a;前序 中序 后序&#xff08;深度优先&#xff09;&#xff0c;层序&#xff08;广度优先&#xff09;类型遍历方法特点深度优先遍历前序、中…
阅读更多...
最新文章

Copyright @ 2022~2023