• 中文
    • English
  • 注册
  • 查看作者
  • 队列相关知识整理

    一.  队列简介

    • 队列也是一种特殊的线性表
    • 队列只允许在表的一段插入,另一端删除,而栈只允许在表的末端入和删除
    • 队列中允许插入的一端称为队尾(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
  • 3.6k
  • 请登录之后再进行评论

    登录

    赞助本站

    • 支付宝
    • 微信
    • QQ

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

    单栏布局 侧栏位置: