1. 首页
  2. IT资讯

队列的顺序存储结构

队列的顺序存储结构相对于链式存储结构较为复杂,本文重点介绍队列顺序结构。下面简单的谈两个问题:
1.
由于是顺序队列,很容易想到用数组来存储元素,假如一个队列的长度是10,就是一下可以放入10个元素,当9个元素出队后,又放入3个元素,此时是不是要再增长数组的长度呢?实际中不可能增加数组的长度而任内存空间的浪费,所以我们要构造循环队列,也就是当rear=(队列的长度-1),下一个入队元素的位置是rear=(rear+1)%(队列的长度),同理front也是如此。只要是顺序队列都是循环队列
2.如何判断什么时候队列是空,什么时候队列已经满了呢?这个是实际中不可避免的问题。在顺序队列中,我们通常用front,rear两个”指针”来进行入队和出队的操作,在队列的初始化时,front=rear,此时队列为空,这是队列为空的判断条件;那么什么时候队列满了呢,通常留一个存储空间不存储元素,此时判断队列满的条件就是(rear+1)%(队列的长度) =  front,解决了当rear = front时,不知道是队满还是队空的问题。
简单的介绍了循环队列中的棘手的问题,下面给出简单实现的代码:

点击(此处)折叠或打开

  1. #include<iostream>
  2. #define MAX_SIZE 10
  3. using namespace std;
  4. struct Squeue {
  5.     int data[MAX_SIZE];
  6.     int rear, front;
  7. };

  8. void initSqueue(Squeue *);
  9. void emptySqueue(Squeue *);
  10. void fullSqueue(Squeue *);
  11. void Insqueue(Squeue *, int);
  12. void Outsqueue(Squeue *, int *);
  13. void ergodicSqueue(Squeue *);

  14. void initSqueue(Squeue *q) {
  15.     q>front = 0;
  16.     q>rear = 0;
  17. }
  18. void emptySqueue(Squeue *q) {
  19.     if (q>rear == q>front) {                  //判断队列空的条件
  20.         cout << “队列为空!!!” << endl;
  21.         exit(1);
  22.     }
  23.     else
  24.         return;
  25. }
  26. void fullSqueue(Squeue *q) {
  27.     if ((q>rear + 1) % MAX_SIZE == q>front){   //判断队列已满的条件
  28.     cout << “队列已满!!!” << endl;
  29.     exit(1);
  30.     }
  31.     else
  32.         return;
  33. }
  34. void Insqueue(Squeue *q, int e) {
  35.     fullSqueue(q);                      //入队时判断队列是否已满
  36.     q>data[q>rear] = e;
  37.     q>rear = (q>rear + 1) % MAX_SIZE;
  38. }
  39. void Outsqueue(Squeue *q, int *e) {
  40.     emptySqueue(q);                     //出队时判断队列是否已空
  41.     *e = q>data[q>front];
  42.     q>front = (q>front + 1) % MAX_SIZE;
  43. }
  44. void ergodicSqueue(Squeue *q) {          //对队列进行入队出队操作后,打印在队列中的元素
  45.     int i = 0;
  46.     cout << “在队列中的元素是:”;
  47.     while (q>front != q>rear) {
  48.         cout << q>data[q>front] << “,”;
  49.         q>front = (q>front + 1) % MAX_SIZE;
  50.         i++;
  51.     }
  52.     cout << endl;
  53.     cout << “队列中的元素个数为:” << i << endl; //统计队列中元素的个数
  54. }
  55. int main() {
  56.     Squeue queue;
  57.     int e = 0;
  58.     initSqueue(&queue);
  59.     for (int i = 1; i <= 9; i++) {
  60.         Insqueue(&queue, i);
  61.     }
  62.    
  63.     Outsqueue(&queue, &e);
  64.     cout << “出队的元素是:” << e << endl;
  65.     Outsqueue(&queue, &e);
  66.     cout << “出队的元素是:” << e << endl;
  67.     Insqueue(&queue, 10);
  68.     Outsqueue(&queue, &e);
  69.     cout << “出队的元素是:” << e << endl;
  70.     ergodicSqueue(&queue);
  71. }

执行结果:
队列的顺序存储结构
以上只是粗略的介绍,当然更为详细的是画图分析该过程,由于画图比较繁琐,这里不作展示。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/29876893/viewspace-1847566/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:℅傍ㄖ免沦陷dε鬼,转转请注明出处:http://www.cxybcw.com/191799.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code