数据结构与算法基础-学习-12-线性表之顺序队

一、个人理解

1. 队列是线性表的衍生之一，具有先进先出的特性，在队尾进行插入操作，在队头进行删除操作。

2. 队列的存储结构分为两个大类，一种是顺序队，就是用数组实现。另一种就是链队，使用链表实现。

3. 顺序队存在真上溢和假上溢两种情况，真上溢指的是数据真的满了。假上溢举例的话就是队头索引由于出队（删除数据）而上移例如变为1，0号索引位会空出来，而队尾索引已到达数组最大长度，这时就会出现空间浪费的情况，所以引入了循环顺序队的概念。

二、顺序队图解

三、循环顺序队图解

当循环顺序队长度不满时，0、1、2号索引位没有数据（或者说有可以抹除的数据），不能浪费，如图队最大长度6，队尾索引是5，队头索引是3，（5+1）%6=0，又回到了0，可以继续插入数据，避免了空间的浪费。

四、结构体

1、ElemType

（1）说明

存放自定义数据。

（2）源码

typedef struct ElemType
{char StudentNum[StudentNumLen];char StudentName[StudentNameLen];int  StudentScore;
}ElemType;

2、SqQueue

（1）说明

Data：数据。

FrontIndex：队头索引。

RearIndex：队尾索引。

SqQueueLen：队的长度。

（2）源码

typedef struct SqQueue
{ElemType*    Data;QueueLenType FrontIndex;  //队头，出队时用。QueueLenType RearIndex;   //队尾，入队时用。QueueLenType SqQueueLen;
}SqQueue;

五、自定义数据类型

typedef int Status;typedef unsigned long long int QueueLenType;

六、函数

1、InitSqQueue

（1）用途

初始化顺序队。

（2）源码

Status InitSqQueue(SqQueue* SQ)
{JudgeAllNullPointer(SQ);SQ->Data = (ElemType*)MyMalloc(sizeof(ElemType) * SQ_QUEUE_MAX_SIZE);SQ->FrontIndex = 0;SQ->RearIndex  = 0;SQ->SqQueueLen = 0;Log("Init SqQueue    : OK\n",Info);return SuccessFlag;
}

（3）参数

参数名	说明
SQ	需要初始化的SqQueue*类型顺序队。

2、GetSqQueueLen

（1）用途

获取顺序队长度。

（2）源码

QueueLenType GetSqQueueLen(SqQueue* SQ)
{JudgeAllNullPointer(SQ);return SQ->SqQueueLen;
}

（3）参数

参数名	说明
SQ	SqQueue*类型顺序队。

3、EnterSqQueue

（1）用途

入队，将ElemType类型的数据插入到循环顺序队的队尾。

（2）源码

Status EnterSqQueue(SqQueue* SQ, ElemType E)
{JudgeAllNullPointer(SQ);if(GetSqQueueLen(SQ) == SQ_QUEUE_MAX_SIZE){Log("SqQueue is full, Data cannot be entered\n",Warning);return FailFlag;}SQ->SqQueueLen++;SQ->Data[SQ->RearIndex] = E;SQ->RearIndex = (SQ->RearIndex + 1) % SQ_QUEUE_MAX_SIZE;Log("Enter SqQueue   : OK\n",Info);return SuccessFlag;
}

（3）参数

参数名	说明
SQ	SqQueue*类型顺序队。
E	需要插入ElemType类型的数据。

4、LeaveSqQueue

（1）用途

出队，将出队元素赋予ElemType* E，作为输出参数。

（2）源码

Status LeaveSqQueue(SqQueue* SQ, ElemType* E)
{JudgeAllNullPointer(SQ);JudgeAllNullPointer(E);if(GetSqQueueLen(SQ) == 0){Log("SqQueue is Empty, Data cannot be left\n",Warning);return FailFlag;}SQ->SqQueueLen--;*E = SQ->Data[SQ->FrontIndex];SQ->FrontIndex = (SQ->FrontIndex + 1) % SQ_QUEUE_MAX_SIZE;Log("Leave SqQueue   : OK\n",Info);return SuccessFlag;
}

（3）参数

参数名	说明
SQ	SqQueue*类型顺序队。
E	输出参数，给一个ElemType* 类型指针即可。

5、GetSqQueueTop

（1）用途

获取顺序队队头数据，如果队是空队，返回ElemType的类型数据{"","",0}。

（2）源码

ElemType GetSqQueueTop(SqQueue* SQ)
{JudgeAllNullPointer(SQ);if(GetSqQueueLen(SQ) == 0){Log("SqQueue is Empty, can't get SqQueueTop\n",Warning);ElemType res = {"","",0};return res;}return SQ->Data[SQ->FrontIndex];
}

（3）参数

参数名	说明
SQ	SqQueue*类型顺序队。

七、虚机测试

[gbase@czg2 LinearTable_SqQueue]$ make
gcc -Wall -g ../Log/Log.c SqQueue.c main.c -o TestSqQueue -I ../Log/[gbase@czg2 LinearTable_SqQueue]$ ./TestSqQueue 
2023-2--Info--Init SqQueue    : OK
2023-2--Info--Enter SqQueue   : OK
2023-2--Info--Enter SqQueue   : OK
2023-2--Info--Enter SqQueue   : OK
2023-2--Info--Enter SqQueue   : OK
2023-2--Info--Enter SqQueue   : OK
2023-2--Info--Enter SqQueue   : OK
2023-2--Warning--SqQueue is full, Data cannot be entered
2023-2--Warning--SqQueue is full, Data cannot be entered
2023-2--Debug--SqQueue Data   :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 100
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 101
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 102
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 103
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 104
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 105
+++++++++++++++
FrontIndex     : 0
RearIndex      : 0
SqQueueLen     : 6
2023-2--Info--Leave SqQueue   : OK
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 100
2023-2--Info--Leave SqQueue   : OK
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 101
2023-2--Info--Leave SqQueue   : OK
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 102
2023-2--Info--Leave SqQueue   : OK
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 103
2023-2--Debug--SqQueue Data   :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 104
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 105
+++++++++++++++
FrontIndex     : 4
RearIndex      : 0
SqQueueLen     : 2
2023-2--Info--Enter SqQueue   : OK
2023-2--Info--Enter SqQueue   : OK
2023-2--Info--Enter SqQueue   : OK
2023-2--Info--Enter SqQueue   : OK
2023-2--Debug--SqQueue Data   :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 104
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 105
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 100
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 101
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 102
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 103
+++++++++++++++
FrontIndex     : 4
RearIndex      : 4
SqQueueLen     : 6
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 104