队列的顺序存储结构

news/2024/5/18 13:40:45/文章来源:https://blog.csdn.net/qq_57484399/article/details/127334106

说白了,就是一个数组 ,然后在两端进行操作 ,两端用首队指针和尾指针分别指向 ,然后进行相关的删除,插入操作, 目的还是模拟现实对数据的处理

●描述队列

•数据元素data , 元素具有同一类型ElemType ,最多为MaxSize(数组容量)

•当前队首front

•当前队尾 rear

定义队列的数据结构
typedef struct
{ElemType data[MaxSize];int front,rear;//队首和队尾指针
}SqQueue;
以上是我们的队列的存储结构, 队列中有存储数据的数组 ElemType data[MaxSize];

还有对数组进行操作的指针 front ,rear

我们现在演示顺序队的操作:

初始的时候 , 是空队列 ,队首和队尾指针都指向空

当元素入队的时候 , rear 后移,然后我们对其位置赋值元素 ,rear指向新元素

当出队的时候 ,front 是指向出队的元素的 ,当没有元素出队的时候 ,指向空 ,当出队的时候 ,front上移到数组位序为 0的位置 ,并对其进行出队, 队首指针的下一个元素变成队首元素

下面我们分析 ,顺序队的四要素

● 队空条件 : front = rear

当队首指针和尾指针重合的时候 ,我们就把最后一个新元素,进行了删除了 ,

所以队空条件 , 就是两者重合

● 队满条件 : rear = MaxSize - 1

因为我们数组坐标是从 0 开始算的 , 所以当队尾指针指向数组最后一个位序时 , 队满

●元素 e 进队 : rear++ ; data[rear] = e;

我们队尾指针指向的是队列一个元素 , 所以当我们要插入元素的时候 ,如果队列不满, 我们就把指针所指的位序加一 ,然后把新元素进队就可以了

● 元素 e 出队: front ++ ; e = data[front];

我们这里队首指针指向的是 , 队列第一个元素的前一个位置 , 所以当我们要进行出队操作的时候 , 我们才把 front 加一 ,然后指向第一个元素 ,符合常识

(删除前,要判断是非是空队, 空队则无需删除)

初始化队列 InitQueue(q)

● 构造一个空队列 q ,然后将 front 和 rear 指针均设置成初始状态 ,即 -1 值.

//传入要构造的队列
void InitQueue(SqQueue *&q)
{q = (SqQueue *)malloc(sizeof(SqQueue));q -> front = q -> rear = -1;
}
这里把首尾指针道法都指向负一的妙处是: 我们一会儿插入元素时, 加一即可指向新元素

销毁队列 DestroyQueue(q)

● 释放队列 q 占用的存储空间

//传入要销毁的队列
void DestroyQueue(SqQueue *&q)
{free(q);
}
因为我们用数组来承接数据 ,结构单一 ,直接释放队列即可

判断队列是否为空 QueueEmpty(q)

●若队列 q 满足 q->front = q->rear 条件 , 则返回 true ; 否则返回 false.

//传入要判断是否为空的队列
bool QueueEmpty(SqQueue *q)
{return(q->front == q->rear);
}
•当初始的时候 , 队列内无元素 ,队首和队尾指针都指向 -1 , 当插入新元素的时候 , 尾指针指向新元素 ; 当我们删除元素的时候 , 队首指针指向要删除的元素 ;

所以当队首指针删除到队尾时候 , 栈为空

进队列enQueue(q,e)

●条件

•队列不满时

●操作

•先将队尾指针 rear 增1 ,

• 然后将新元素添加到该位置

//进队列 enQueue(q,e)
//传入要插入队列, 和新元素的值
bool enQueue(SqQueue *&q, ElemType e)
{//条件,队列不满if(q->rear = MaxSize-1){return false;}//不满,则可以插入新元素,队尾指针自增,指向新元素位置q->rear++;//数组承接 ,所以更改位序即可q->data[q->rear] = e;//插入成功,返回truereturn true;}

出队列 deQueue(q,e)

●条件

•队列 q 不为空

● 操作

•将队首指针 front 循环增 1

•将该位置的元素赋值给 e

// 出队列 deQueue(q,e)
//传入要出队的队列地址指针,记录出队元素的地址
bool deQueue(SqQueue *&q,ElemType &e)
{//先判断是否队空,空则返回错误if(q -> front == q->rear){return false;}//不空,则删除第一个队列元素,因为我们队首指针//初始指向的是第一个元素的前一个位置,所以,队首指针自增1,传出元素即可q -> front++;e = q->data[q->front];//传出成功,则返回truereturn true;
}