当前位置:   article > 正文

队列的顺序存储结构

队列的顺序存储结构

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

●描述队列

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

        •当前队首front

        •当前队尾 rear

定义队列的数据结构

  1. typedef struct
  2. {
  3. ElemType data[MaxSize];
  4. int front,rear;//队首和队尾指针
  5. }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 值.

  1. //传入要构造的队列
  2. void InitQueue(SqQueue *&q)
  3. {
  4. q = (SqQueue *)malloc(sizeof(SqQueue));
  5. q -> front = q -> rear = -1;
  6. }

这里把首尾指针道法都指向负一的妙处是: 我们一会儿插入元素时, 加一即可指向新元素

销毁队列 DestroyQueue(q)

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


  1. //传入要销毁的队列
  2. void DestroyQueue(SqQueue *&q)
  3. {
  4. free(q);
  5. }

因为我们用数组来承接数据 ,结构单一 ,直接释放队列即可

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

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


  1. //传入要判断是否为空的队列
  2. bool QueueEmpty(SqQueue *q)
  3. {
  4. return(q->front == q->rear);
  5. }

•当初始的时候 , 队列内无元素 ,队首和队尾指针都指向 -1 , 当插入新元素的时候 , 尾指针指向新元素 ; 当我们删除元素的时候  , 队首指针指向要删除的元素 ;

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

进队列enQueue(q,e)

        ●条件

                •队列不满时

        ●操作

                •先将队尾指针 rear 增1 ,

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



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

出队列 deQueue(q,e)

     ●条件

                •队列 q 不为空

     ● 操作

                •将队首指针 front 循环增 1

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



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

上述顺序队列的基本操作已经完成 , 我们会注意到顺序队列的一个问题 ,当队首指针和队尾指针指向数组的最后一个元素时 , 队列表示队空, 但是,我们之前的元素还每利用



所以我们 , 现在遇到的问题就是, 我们增加元素,删除元素 ,此操作不能循环执行 

那怎么办呢? 我们既然 进行操作的时候 ,首尾指针到达了数组尾部 不能继续执行 ,我们就把数组的首尾链接起来, 形成循环队列,详见下节

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/正经夜光杯/article/detail/918118
推荐阅读
相关标签
  

闽ICP备14008679号