队列的顺序存储结构

时间:2022-07-17 17:38:02
队列的顺序存储结构相对于链式存储结构较为复杂,本文重点介绍队列顺序结构。下面简单的谈两个问题:
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. void Insqueue(Squeue *q, int e) {
  34.     fullSqueue(q);                      //入队时判断队列是否已满
  35.     q->data[q->rear] = e;
  36.     q->rear = (q->rear + 1) % MAX_SIZE;
  37. }
  38. void Outsqueue(Squeue *q, int *e) {
  39.     emptySqueue(q);                     //出队时判断队列是否已空
  40.     *= q->data[q->front];
  41.     q->front = (q->front + 1) % MAX_SIZE;
  42. }
  43. void ergodicSqueue(Squeue *q) {          //对队列进行入队出队操作后,打印在队列中的元素
  44.     int i = 0;
  45.     cout << "在队列中的元素是:";
  46.     while (q->front != q->rear) {
  47.         cout << q->data[q->front] << ",";
  48.         q->front = (q->front + 1) % MAX_SIZE;
  49.         i++;
  50.     }
  51.     cout << endl;
  52.     cout << "队列中的元素个数为:" << i << endl; //统计队列中元素的个数
  53. }
  54. int main() {

  55.     Squeue queue;
  56.     int e = 0;
  57.     initSqueue(&queue);
  58.     for (int i = 1; i <= 9; i++) {
  59.         Insqueue(&queue, i);
  60.     }
  61.    
  62.     Outsqueue(&queue, &e);
  63.     cout << "出队的元素是:" << e << endl;
  64.     Outsqueue(&queue, &e);
  65.     cout << "出队的元素是:" << e << endl;

  66.     Insqueue(&queue, 10);
  67.     Outsqueue(&queue, &e);
  68.     cout << "出队的元素是:" << e << endl;
  69.     ergodicSqueue(&queue);
  70. }
执行结果:
队列的顺序存储结构
以上只是粗略的介绍,当然更为详细的是画图分析该过程,由于画图比较繁琐,这里不作展示。