美文网首页
622.实现一个循环队列

622.实现一个循环队列

作者: HamletSunS | 来源:发表于2019-08-10 13:11 被阅读0次

    借鉴别人的思路:
    思路主旨:不牺牲任何1个存储空间
    不浪费1个空间,但这样需要对队列状态的判断进行额外的处理。
    首先明确定义:
    head和tail的定义,head指向出队元素,tail指向即将入队元素的前一个位置
    出队 先出队,再head+1 (若先head+1,再出队,那么必然会造成一个空间的浪费)
    入队 先tail+1,再入队

    在以上前提下,再去考虑设计队列状态的判断。
    队满:tail+1后 发现tail==head,即(tail+1)%size==head,队满
    队 空:??
    出现了问题,发现队空的状态无法判断,假设head==tail,根据定义,tail指向下一个入队元素的前一个位置,head指向即将出队的元素,那么这种情况说明队列出有1个元素。
    那么如何判断队列为空?
    解决方案是给队列为空设置一个特殊的初始状态,即令head=tail=-1.这样设计的好处是1特征明显,好判断2.元素入队的时候好操作,tail+1自动指向了正确的0索引,只需要对head作下操作即可。

    有了队空状态的解决方案后,那么整体设计方案也就出来了
    定义:head,tail同上
    初始化:head=tail=-1,size
    入队:判队满,看是否失败;然后判对空,若为空队,需要队head指针单独进行处理(head=0)。最后执行入队逻辑。
    出队:判队空,看是否失败;判是否仅有一个元素(head==tail),是的话执行出队操作后,令head=tail=-1;
    队满:(tail+1)%size==head
    队空:head==-1;

    自己思路的关键点:
    取余法实现循环
    牺牲了一个存储空间来区分队列是空还是满
    判空 head==tail
    判满 (tail+1)%size==head
    入队 先判断是否队满,然后tail后移,存入
    出对 先判断是否队空,然后head后移,出队

    class MyCircularQueue {
    private:
        vector<int> data;
        int head,tail,size;
    public:
        /** Initialize your data structure here. Set the size of the queue to be k. */
        MyCircularQueue(int k) {
            size=k+1;
            data=vector<int>(k+1,0);
            tail=head=0;
        }
        
        /** Insert an element into the circular queue. Return true if the operation is successful. */
        bool enQueue(int value) {
            if(isFull())
                return false;
            tail=(tail+1)%size; 
            data[tail]=value;               
            return true;
        }
        
        /** Delete an element from the circular queue. Return true if the operation is successful. */
        bool deQueue() {
            if(isEmpty())
                return false;
            head=(head+1)%size;
            return true;
            
        }
        
        /** Get the front item from the queue. */
        int Front() {
            if(isEmpty())
                return -1;
            int n=(head+1)%size;
            return data[n];
        }
        
        /** Get the last item from the queue. */
        int Rear() {
            if(isEmpty())
                return -1;
            return data[tail];
        }
        
        /** Checks whether the circular queue is empty or not. */
        bool isEmpty() {
            return head==tail;
        }
        
        /** Checks whether the circular queue is full or not. */
        bool isFull() {
            return (tail+1)%size==head;
        }
    };
    
    

    相关文章

      网友评论

          本文标题:622.实现一个循环队列

          本文链接:https://www.haomeiwen.com/subject/btcrjctx.html