devbox
2023面试高手
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构与算法 －循环队列_循环队列上溢和下溢

作者：2023面试高手 | 2024-04-21 06:22:02

赞

踩

循环队列上溢和下溢

循环队列用数组的形式为队列分配一块存储空间，并将这一块存储空间看成头尾相连接的。

头指针front：顺时针方向落后于实际队头元素一个位置，该位置为空，主要是为了判断首尾指针是否相遇了。

尾指针rear：指向实际队尾元素。

下溢条件：CQ.front==CQ.rear。

上溢条件：(CQ.rear+1)%maxsize==CQ.front，因为头指针指向的是一个空的元素，所以队满时实际队列容量为maxsize-1。

类型定义：

  1. typedef struct CycQueue{
  2.  
  3.     DataType data[maxsize];
  4.  
  5.     int front,rear;
  6.     
  7. }CycQue;
  8.  
  9. CycQue CQ;

基本运算：

1. 初始化；

  1. void InitQueue(CycQue CQ){
  2.  
  3.     CQ.front=0;
  4.  
  5.     CQ.rear=0;
  6. }

2. 判断队列为空；

  1. int EmptyQueue(CycQue CQ){
  2.  
  3.     if (CQ.rear==CQ.front) {
  4.  
  5.         return 1;
  6.  
  7.     }else{
  8.         
  9.         return 0;
  10.     } 
  11. }

3.入队列； 

  1. int EnQueue(CycQue CQ,DataType x){
  2.  
  3.     if ((CQ.rear+1)%maxsize==CQ.front){
  4.  
  5.         error("队列满");
  6.  
  7.         return 0;
  8.     }else {
  9.         // 必须先把尾指针加1
  10.         CQ.rear=(CQ.rear+1)%maxsize;
  11.  
  12.         CQ.data[CQ.rear]=x;
  13.         
  14.         return 1;
  15.     }
  16. }

4. 出队列；

  1. int OutQueue(CycQue CQ){
  2.  
  3.     if (EmptyQueue(CQ)){
  4.  
  5.         error("队列空");
  6.  
  7.         return 0;
  8.  
  9.     }else {
  10.         // 头指针加1
  11.         CQ.front=(CQ.front+1)%maxsize;
  12.  
  13.         return 1;
  14.     }
  15. }

5. 取队列首元素；

  1. DataType GetHead(CycQue CQ){
  2.  
  3.     if (EmptyQueue(CQ)){
  4.  
  5.         return NULLData
  6.  
  7.     }else{
  8.  
  9.         return CQ.data[(CQ.front+1)%maxsize];
  10.     }
  11.  
  12. }

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号