循环队列

循环队列工作原理图

从上图我们可以总结出循环队列工作的要点

  1. 队列空的条件:head == tail
  2. 队列满的条件:(tail + 1) % maxlen == head
  3. 约定数组最多存放maxlen - 1个元素
  4. 当队列为空时,head和tail都置为-1,重新从0开始存放元素

C++实现循环队列

class MyCircularQueue {
private:
    vector<int> myqueue;
    int maxlen;
    int head;
    int tail;
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k) {
        myqueue.resize(k+1);
        maxlen = k;
        head = -1;   // head和tail都初始化为-1当元素入队时再从0开始
        tail = -1;
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if(!isFull()){
            if(isEmpty())
                head = 0;
            tail = (tail + 1) % maxlen;
            myqueue[tail] = value;
            return true;
        }
        return false;   
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if(isEmpty())
            return false;
        else{
            if(head == tail){
                head = -1;    // 当队列为空时,head和tail都置为-1,再有元素入队重新从0开始
                tail = -1;
                return true;
            }
            head = (head + 1) % maxlen;
            return true;
        }
    }

    /** Get the front item from the queue. */
    int Front() {
       if(!isEmpty())
            return myqueue[head];
       else
            return -1;
    }

    /** Get the last item from the queue. */
    int Rear() {
        if(!isEmpty()){
            return myqueue[tail];
        }
        return -1;   
    }  
    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        if(head == -1)
            return true;
        else
            return false;
    }

    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        if((tail+1) % maxlen == head)
            return true;
        else
            return false;
    }
};
Last modification:June 28th, 2020 at 11:39 am
如果觉得我的文章对你有用,请随意赞赏