3 队列

[3] 队列 (Queue)

基本概念

定义

队列（Queue）简称队，是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。

特点

队列是操作受限的线性表，只允许在一端进行插入 (入队)，另一端进行删除 (出队)
操作特性：先进先出 FIFO
队头：允许删除的一端
队尾：允许插入的一端
空队列：不含任何元素的空表

基本操作

“创建&销毁”
- InitQueue(&Q): 初始化队列，构造一个空列表 Q
- DestroyQueue(&Q): 销毁队列，并释放队列 Q 所占用的内存空间
“增&删”
- EnQueue(&Q, x): 入队，若队列 Q 未满，将 x 加入，使之成为新的队尾
- DeQueue(&Q, &x): 出队，若队列 Q 非空，删除队头元素，并用 x 返回
“查&其他”
- GetHead(Q,&x): 读队头元素，若队列 Q 非空，则将队头元素赋值给 x
- QueueEmpty(Q): 判队列空，若队列 Q 为空，则返回

[3-1-1] 顺序队列

特性

队头指针：指向队头元素
队尾指针：指向队尾元素的下一个位置

{0(-1-1)} 结构体定义到外部操作

//队列的顺序存储类型
## define MaxSize 10;     //定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];   //用静态数组存放队列元素
                              //连续的存储空间，大小为——MaxSize*sizeof(ElemType)
    int front, rear;          //队头指针和队尾指针
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    //初始化时，队头、队尾指针指向0
    Q.rear = Q.front = 0;
}

void test{
    SqQueue Q;                //声明一个队列
    InitQueue(Q);
    //...
}

{5-2}

// 判空
bool QueueEmpty(SqQueue 0){
    if(Q.rear == Q.front)    //判空条件后
        return true;
    else
        return false;
}

[3-1-1-2] 循环队列

基本概念

定义：将循环队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。基本操作：

初始：Q.front = Q.rear = 0;
队首指针进 1：Q.front = (Q.front + 1) % MaxSize
队尾指针进 1：Q.rear = (Q.rear + 1) % MaxSize —— 队尾指针后移，当移到最后一个后，下次移动会到第一个位置
队列长度：(Q.rear + MaxSize - Q.front) % MaxSize

{5-2(-1)} 判空/判满

方案一: 牺牲一个单元来区分队空和队满

队尾指针的再下一个位置就是队头，即 (Q.rear+1)%MaxSize == Q.front

循环队列——入队：只能从队尾插入（判满使用方案一）

bool EnQueue(SqQueue &Q, ElemType x){
    if((Q.rear+1)%MaxSize == Q.front)        //队满
        return false;
    Q.data[Q.rear] = x;                      //将x插入队尾
    Q.rear = (Q.rear + 1) % MaxSize;         //队尾指针加1取模

    return true;
}

循环队列——出队：只能让队头元素出队

//出队，删除一个队头元素，用x返回
bool DeQueue(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front)              //队空报错
        return false;

    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize; //队头指针后移动

    return true;
}

循环队列——获得队头元素

bool GetHead(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front)              //队空报错
        return false;

    x = Q.data[Q.front];
    return true;
}

方案二: 不牺牲存储空间，设置 size

定义一个变量 size用于记录队列此时记录了几个数据元素，初始化 size = 0，进队成功 size++，出队成功size--，根据 size 的值判断队满与队空

队满条件：size == MaxSize

队空条件：size == 0

## define MaxSize 10;
typedef struct{
    ElemType data[MaxSize];
    int front, rear;
    int size;               //队列当前长度
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    Q.rear = Q.front = 0;
    size = 0;
}

方案三: 不牺牲存储空间，设置 tag（推荐）

定义一个变量 tag，tag = 0 --最近进行的是删除操作；tag = 1 --最近进行的是插入操作；

每次删除操作成功时，都令tag = 0；只有删除操作，才可能导致队空；

每次插入操作成功时，都令tag = 1；只有插入操作，才可能导致队满；

队满条件：Q.front == Q.rear && tag == 1

队空条件：Q.front == Q.rear && tag == 0

## define MaxSize 10;
typedef struct{
    ElemType data[MaxSize];
    int front, rear;
    int tag;               //最近进行的是删除or插入
}SqQueue;

{5-1} 求循环队列的长度：

图片链接：https://img-blog.csdnimg.cn/5d6a097df3694d178fccdb510bf6558b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rGg6bG85LmL5q6D,size_18,color_FFFFFF,t_70,g_se,x_16

[3-2-1-1] 链队列

定义：队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。链队列：用链表表示的队列，是限制仅在表头删除和表尾插入的单链表。

{0}

typedef struct LinkNode{      //链式队列结点
    ElemType data;
    struct LinkNode *next;
}

typedef struct{               //链式队列
    LinkNode *front, *rear;   //队列的队头和队尾指针
}LinkQueue;

{0-1}

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

{1-3-2} 入队列(队尾)

//新元素入队 (表尾进行)
void EnQueue(LinkQueue &Q, ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //申请一个新结点
    s->data = x;
    s->next = NULL;     //s作为最后一个结点，指针域指向NULL
    Q.rear->next = s;   //新结点插入到当前的rear之后
    Q.rear = s;         //表尾指针指向新的表尾
}

{2-3-1} 出队列(队首)

//队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
    if(Q.front == Q.rear)
        return false;                    //空队

    LinkNode *p = Q.front->next;         //p指针指向即将删除的结点 (头结点所指向的结点)
    x = p->data;
    Q.front->next = p->next;             //修改头结点的next指针
    if(Q.rear == p)                      //此次是最后一个结点出队
        Q.rear = Q.front;                //修改rear指针
    free(p);                             //释放结点空间

    return true;
}

{5-2}

//判断队列是否为空
bool IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear)     //也可用 Q.front -> next == NULL
        return true;
    else
        return false;
}

队列满的条件

顺序存储：预分配存储空间

链式存储：一般不会队满，除非内存不足

计算链队长度 (遍历链队) 设置一个int length 记录链式队列长度
初始化 & 判空
入队操作

// 新元素入队 (表尾进行)
void EnQueue(LinkQueue &Q, ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //申请一个新结点
    s->data = x;
    s->next = NULL;

    // 第一个元素入队时需要特别处理
    if(Q.front = NULL){            // 在空队列中插入第一个元素
        Q.front = s;               // 修改队头队尾指针
        Q.rear = s;
    }else{
        Q.rear->next = s;           // 新结点插入到rear结点之后
        Q.rear = s;                 // 修改rear指针指向新的表尾结点
    }
}

[3-?] 双端队列

1.定义：双端队列是指允许两端都可以进行入队和出队操作的队列

双端队列允许从两端插入、两端删除的线性表；
如果只使用其中一端的插入、删除操作，则等同于栈；
输入受限的双端队列：允许一端插入，两端删除的线性表；
输出受限的双端队列：允许两端插入，一端删除的线性表；

AP>特殊矩阵的压缩存储

矩阵定义：一个由 m*n 个元素排成的 m 行(横向)n 列(纵向)的表。矩阵的常规存储：将矩阵描述为一个二维数组。

数组的存储结构

一维数组

Elemtype a[10];

各数组元素大小相同，物理上连续存放；

起始地址：LOC

数组下标：默认从 0 开始！

数组元素 a[i] 的存放地址 = LOC + i × sizeof(ElemType)

二维数组

Elemtype b[2][4]; //2行4列的二维数组

行优先/列优先存储优点：实现随机存储

起始地址：LOC

M 行 N 列的二维数组 b[M][N]中，b[i][j]的存储地址：

行优先存储: LOC + (i×N + j) × sizeof(ElemType) 列优先存储：LOC + (j×M + i) × sizeof(ElemType)

普通矩阵的存储

二维数组存储：

描述矩阵元素时，行、列号通常从 1 开始；
描述数组时，通常下标从 0 开始；

特殊矩阵的存储

特殊矩阵——压缩存储空间（只存有用的数据）

矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。

对称矩阵(方阵)

在一个 n 阶方阵 A 中，若元素满足下述性值：

图片链接：https://img-blog.csdnimg.cn/c61d1300038640499d795e38a847e253.png

则称 A 为对称矩阵。

图片链接：https://img-blog.csdnimg.cn/9e3ccc92ad774eafa502d6fa0a190457.png

三角矩阵(方阵) 以主对角线划分，三角矩阵有上（下）三角两种。上（下）三角矩阵的下（上）三角（不含主对角线）中的元素均为常数。在大多数情况下，三角矩阵常数为零。

图片链接：https://img-blog.csdnimg.cn/c4fb6f687a7d4cbbad293293ca327ac4.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rGg6bG85LmL5q6D,size_15,color_FFFFFF,t_70,g_se,x_16

三对角矩阵(方阵)

图片链接：https://img-blog.csdnimg.cn/4ac20db9d84e48ff8ee59d77f8071ca9.png

对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一维数组中，且也能找到每个非零元素和向量下标的对应关系。

稀疏矩阵设在 mn 的矩阵中有 t 个非零元素，令 c=t/(mn),当 c<=0.05 时称为稀疏矩阵。压缩存储原则：存各非零元的值、行列位置和矩阵的行列数。

顺序存储——三元组

图片链接：https://img-blog.csdnimg.cn/c4880de88567468fa4660323ab25aab7.png

链式存储——十字链表法优点：它能够灵活得插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的运算。十字链表中结点的结构示意图：
right:用于链接同一行中的下一个非零元素； down:用于链接同一列中的下一个非零元素。

Get Started

储存器管理

3 队列

[3] 队列 (Queue)

基本概念

定义

特点

基本操作

[3-1-1] 顺序队列

特性

{0(-1-1)} 结构体定义到外部操作

{5-2}

[3-1-1-2] 循环队列

基本概念

{5-2(-1)} 判空/判满

方案一: 牺牲一个单元来区分队空和队满

方案二: 不牺牲存储空间，设置 size

方案三: 不牺牲存储空间，设置 tag（推荐）

{5-1} 求循环队列的长度：

[3-2-1-1] 链队列

{0}

{0-1}

{1-3-2} 入队列(队尾)

{2-3-1} 出队列(队首)

{5-2}

队列满的条件

[3-?] 双端队列

AP>特殊矩阵的压缩存储

数组的存储结构

普通矩阵的存储

特殊矩阵的存储

3 队列 ​

[3] 队列 (Queue) ​

基本概念 ​

定义 ​

特点 ​

基本操作 ​

[3-1-1] 顺序队列 ​

特性 ​

{0(-1-1)} 结构体定义到外部操作 ​

{5-2} ​

[3-1-1-2] 循环队列 ​

基本概念 ​

{5-2(-1)} 判空/判满 ​

方案一: 牺牲一个单元来区分队空和队满 ​

方案二: 不牺牲存储空间，设置 size ​

方案三: 不牺牲存储空间，设置 tag（推荐） ​

{5-1} 求循环队列的长度： ​

[3-2-1-1] 链队列 ​

{0} ​

{0-1} ​

{1-3-2} 入队列(队尾) ​

{2-3-1} 出队列(队首) ​

{5-2} ​

队列满的条件 ​

[3-?] 双端队列 ​

AP>特殊矩阵的压缩存储 ​

数组的存储结构 ​

普通矩阵的存储 ​

特殊矩阵的存储 ​

3 队列

[3] 队列 (Queue)

基本概念

定义

特点

基本操作

[3-1-1] 顺序队列

特性

{0(-1-1)} 结构体定义到外部操作

{5-2}

[3-1-1-2] 循环队列

基本概念

{5-2(-1)} 判空/判满

方案一: 牺牲一个单元来区分队空和队满

方案二: 不牺牲存储空间，设置 size

方案三: 不牺牲存储空间，设置 tag（推荐）

{5-1} 求循环队列的长度：

[3-2-1-1] 链队列

{0}

{0-1}

{1-3-2} 入队列(队尾)

{2-3-1} 出队列(队首)

{5-2}

队列满的条件

[3-?] 双端队列

AP>特殊矩阵的压缩存储

数组的存储结构

普通矩阵的存储

特殊矩阵的存储