当前位置:   article > 正文

数据结构— —循环队列_循环队列入队

循环队列入队

在队列的顺序存储中,采用出队方式 2, 删除 front 所指的元素,然后加 1 并返回被删元素。这样可以避免元素移动,但是也带来了一个新的问题“假溢出”。

 能否利用前面的空间继续存储入队呢?采用循环队列

 循环队列入队, 队尾循环后移: SQ->rear =(SQ->rear+1)%Maxsize;

 循环队列出队, 队首循环后移: SQ->front =(SQ->front+1)%Maxsize;

队空:SQ.front=SQ.rear; // SQ.rear 和 SQ.front 指向同一个位置

队满: (SQ.rear+1) %Maxsize=SQ.front; // SQ.rear 向后移一位正好是 SQ.front

 计算元素个数: 可以分两种情况判断:

如果 SQ.rear>= SQ.front:元素个数为 SQ.rear-SQ.front;

 如果 SQ.rear<SQ.front:元素个数为 SQ.rear-SQ.front+ Maxsize;

采用取模的方法把两种情况统一为:(SQ.rear-SQ.front+Maxsize)% Maxsize

完整代码实现

  1. #include <stdio.h>
  2. #include <assert.h>
  3. #include <Windows.h>
  4. #include <iostream>
  5. #include <iomanip>
  6. using namespace std;
  7. #define MaxSize 5 //循环队列的最大容量
  8. typedef int DataType; //循环队列中元素类型
  9. typedef struct Queue
  10. {
  11. DataType queue[MaxSize];
  12. int front; //循环队头指针
  13. int rear; //循环队尾指针
  14. }SeqQueue;
  15. //队列初始化,将循环队列初始化为空队列
  16. void InitQueue(SeqQueue *SQ)
  17. {
  18. if(!SQ) return ;
  19. SQ->front = SQ->rear = 0; //把对头和队尾指针同时置0
  20. }
  21. //判断队列为空
  22. int IsEmpty(SeqQueue *SQ)
  23. {
  24. if(!SQ) return 0;
  25. if (SQ->front == SQ->rear)
  26. {
  27. return 1;
  28. }
  29. return 0;
  30. }
  31. //判断循环队列是否为满
  32. int IsFull(SeqQueue *SQ)
  33. {
  34. if(!SQ) return 0;
  35. if ((SQ->rear+1)%MaxSize == SQ->front)
  36. {
  37. return 1;
  38. }
  39. return 0;
  40. }
  41. //入队,将元素data插入到循环队列SQ中
  42. int EnterQueue( SeqQueue *SQ,DataType data)
  43. {
  44. if(!SQ) return 0;
  45. if(IsFull(SQ))
  46. {
  47. cout<<"无法插入元素 "<<data<<", 队列已满!"<<endl;
  48. return 0;
  49. }
  50. SQ->queue[SQ->rear] = data; //在队尾插入元素data
  51. SQ->rear=(SQ->rear+1)%MaxSize; //队尾指针循环后移一位
  52. return 1;
  53. }
  54. //出队,将队列中队头的元素data出队,出队后队头指针front后移一位
  55. int DeleteQueue(SeqQueue* SQ,DataType* data)
  56. {
  57. if (!SQ || IsEmpty(SQ))
  58. {
  59. cout<<"循环队列为空!"<<endl;
  60. return 0;
  61. }
  62. *data = SQ->queue[SQ->front]; //出队元素值
  63. SQ->front = (SQ->front+1)% MaxSize; //队首指针后移一位
  64. return 1;
  65. }
  66. //打印队列中的各元素
  67. void PrintQueue(SeqQueue* SQ)
  68. {
  69. if(!SQ) return ;
  70. int i = SQ->front;
  71. while(i!=SQ->rear)
  72. {
  73. cout<<setw(4)<<SQ->queue[i];
  74. i=(i+1)%MaxSize;
  75. }
  76. cout<<endl;
  77. }
  78. //获取队首元素,不出队
  79. int GetHead(SeqQueue* SQ,DataType* data)
  80. {
  81. if (!SQ || IsEmpty(SQ))
  82. {
  83. cout<<"队列为空!"<<endl;
  84. }
  85. return *data = SQ->queue[SQ->front];
  86. }
  87. //清空队列
  88. void ClearQueue(SeqQueue* SQ)
  89. {
  90. if(!SQ) return ;
  91. SQ->front = SQ->rear = 0;
  92. }
  93. //获取队列中元素的个数
  94. int getLength(SeqQueue* SQ)
  95. {
  96. if(!SQ) return 0;
  97. return (SQ->rear-SQ->front+MaxSize) % MaxSize;
  98. }
  99. int main()
  100. {
  101. SeqQueue *SQ = new SeqQueue;
  102. DataType data = -1;
  103. //初始化队列
  104. InitQueue(SQ);
  105. //入队
  106. for(int i=0; i<7; i++)
  107. {
  108. EnterQueue(SQ, i);
  109. }
  110. //打印队列中的元素
  111. printf("队列中的元素(总共%d 个):", getLength(SQ));
  112. PrintQueue(SQ);
  113. cout<<endl;
  114. //出队
  115. for(int i=0; i<5; i++)
  116. {
  117. if(DeleteQueue(SQ, &data))
  118. {
  119. cout<<"出队的元素是:"<<data<<endl;
  120. }
  121. else
  122. {
  123. cout<<"出队失败!"<<endl;
  124. }
  125. }
  126. //打印队列中的元素
  127. printf("出队五个元素后,队列中剩下的元素个数为 %d 个:", getLength(SQ));
  128. PrintQueue(SQ); cout<<endl;
  129. //入队4个
  130. for(int i=0; i<4; i++)
  131. {
  132. EnterQueue(SQ, i+10);
  133. }
  134. printf("\n入队四个元素后,队列中剩下的元素个数为 %d 个:", getLength(SQ));
  135. PrintQueue(SQ);
  136. system("pause");
  137. return 0;
  138. }

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

闽ICP备14008679号