3 队列

目录

• [3] 队列 (Queue)
  • 基本概念
• [3-1-1] 顺序队列
  • 特性
  • {0(-1-1)} 结构体定义到外部操作
  • {5-2}
• [3-1-1-2] 循环队列
  • 基本概念
  • {5-2(-1)} 判空/判满
  • {5-1} 求循环队列的长度：
• [3-2-1-1] 链队列
  • {0}
  • {0-1}
  • {1-3-2} 入队列(队尾)
  • {2-3-1} 出队列(队首)
  • {5-2}
  • 队列满的条件
• [3-?] 双端队列
• AP>特殊矩阵的压缩存储
  • 数组的存储结构
  • 普通矩阵的存储
  • 特殊矩阵的存储

[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} 求循环队列的长度：

[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 列(纵向)的表。 矩阵的常规存储：将矩阵描述为一个二维数组。

数组的存储结构

1. 一维数组

Elemtype a[10];

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

起始地址：LOC

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

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

2. 二维数组

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 开始；

特殊矩阵的存储

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

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

1. 对称矩阵(方阵)

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

则称 A 为对称矩阵。

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

1. 三对角矩阵(方阵)

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

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

• 顺序存储——三元组

• 链式存储——十字链表法 优点：它能够灵活得插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的运算。 十字链表中结点的结构示意图：

  

  right:用于链接同一行中的下一个非零元素； down:用于链接同一列中的下一个非零元素。