• 中文
    • English
  • 注册
  • 赞助本站

    • 支付宝
    • 微信
    • QQ

    感谢一直支持本站的所有人!

    • 查看作者
    • 队列相关知识整理

      一.  队列简介

      • 队列也是一种特殊的线性表
      • 队列只允许在表的一段插入,另一端删除,而栈只允许在表的末端入和删除
      • 队列中允许插入的一端称为队尾(rear),允许删除的一端称为队头(front)
      • 队列是先进先出,而栈是先进后出
      • 队列的表示也有两种方法:基于数组的存储表示和基于链表的存储表示(常用)

      二.  基于数组的存储表示

      2.1  实现步骤

      为了充分利用数组的存储空间,避免假溢出的等现象的发生。这里采用循环数列,所谓循环数列,就是把数组的前端和后端连接起来,形成一个环形的表。虽然用if和else也可以实现循环队列,但是我们用取余的方法能更好的实现:

      出队的时候,队头指针进1(也是队顶):

      front = (front + 1) % maxSize;//maxSize 为数组的最大长度

      入队的时候,队尾指针进1(也是队底):

      real = (real + 1) % maxSize;

      队列初始化:

      front = real = 0;

      判断队列是否为空的条件:

      front == real;

      判断队列是否为满的条件:

      注意,因为是循环数列,所以如果第n + 1个元素入队的时候,front和rear的值是相同的,但是上面我们front == real 是用来判断队列是否为空的条件,两者就会产生矛盾,为了避免这种情况的发生,我们让rear指到front的前一个位置就人为队已经满了,这样虽然数组中有一个空间是浪费的,但是能区别于对空的条件

      (real + 1) % maxSize == front;

      2.2 完整代码:

      #include<iostream>
      using namespace std;
      class Queue
      {
      private:
          int *e;//创建一个指针,用于指向数组
          int size;//数组的最大长度
          int front,rear;
      public:
          Queue(int sz = 10)
          {
              e = new int [10];
              size = sz;
              front = rear = 0;
          }
          ~Queue()
          {
              delete[] e;
          }
          bool enQueue(int x);//入队
          bool deQueue(int &x);//出队
          bool isEmpty()//判断队列是否为空
          {
              return front == rear;
          }
          bool isFull()//判断队列是否为满
          {
              return (rear + 1) % size == front;
          }
          bool getTop(int &x);//获取队顶的元素
      };
      
      bool Queue :: getTop(int &x)
      {
          if(isEmpty()) return false;
          x = e[(front + 1) % size];
          return true;
      }
      
      bool Queue :: enQueue(int x)
      {
          if(isFull()) return false;
          rear = (rear + 1) % size;
          e[rear] = x;
      //注意上面入队的方法,rear先加1,再入队,有的书中是先入队再加1,本质上是一样的
      //因为循环数列需要空出一个位置,先加1再入队,空的是第0个位置,先入队再加1,空的是最后一个位置
      //下面的出队的方法同理
          return true;
      }
      
      bool Queue :: deQueue(int &x)
      {
          if(isEmpty()) return false;
          front = (front + 1) % size;
          x = e[front];
          return true;
      }
      
      int main()
      {
          Queue q;
          q.enQueue(1);
          q.enQueue(2);
          q.enQueue(3);
          int x;
          while(! q.isEmpty())
          {
              q.deQueue(x);
              cout << x;
          }
      
          return 0;
      }

      三.  基于链表的存储表示(常用)

      队列的队头指针指向单链表的第一个结点,队尾指针指向单链表的最后一个结点

      单链表实现队列的时候,rear用于插入,front 用于删除

      四.  优先级队列

      优先级队列每次从队列中取出的应是具有最高优先级的元素

      优先级高,先执行,优先级形同,顺序执行

       

    • 0
    • 0
    • 0
    • 2.5k
    • 请登录之后再进行评论

      登录
    • 做任务
    • 实时动态
    • 偏好设置
    • 返回顶部
    • 单栏布局 侧栏位置: