leetcode641设计循环双端队列

迷南。 2022-10-05 04:00 199阅读 0赞

链接: [link][].  
这个里面是循环单向队列，由于实现的时候使用的是数组，所以单双向没差，拿单向的改一下就行了。

使用的还是**空闲单元法**，所以注意点还是一样

front : 指向队列中第一个元素
    rear : 指向队列中最后一个元素的下一个位置，这个地方注意！！！

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
所有减都要有+length  
所有加都要有%length  
思路：

1.  队空条件：`front == rear;`
2.  队满条件：`front == (rear+1)%length;`
3.  队列长度：`queue_l = (rear - front +length)%length;`
4.  队头元素：`queue[front];`
5.  队尾元素：`queue[(rear-1+length)%length];`
6.  队尾插入元素：`queue[rear]=value; rear = (rear+1)%length;`
7.  队尾删除元素：`rear = (rear -1 +length)%length;`
8.  队首删除元素：`front = (front+1)%length;`
9.  队首插入元素：`front = (front -1 +lengtj)%length; queue[front] = value;`

代码

class MyCircularDeque { 
    private:
       int *queue = nullptr;
       int front = 0;
       int rear = 0;
       int length = 0;
    public:
       /** Initialize your data structure here. Set the size of the deque to be k. */
       MyCircularDeque(int k) { 
           queue = (int*)malloc((k+1)*sizeof(int));
           front = 0;
           rear = 0;
           length = k+1;
       }
       
       /** Adds an item at the front of Deque. Return true if the operation is successful. */
       bool insertFront(int value) { 
           if(isFull())
               return false;
           front = (front - 1 +length)%length;
           queue[front] = value;
           return true;
       }
       
       /** Adds an item at the rear of Deque. Return true if the operation is successful. */
       bool insertLast(int value) { 
           if(isFull())
               return false;
           queue[rear] = value;
           rear = (rear+1)%length;
           return true;
    
       }
       
       /** Deletes an item from the front of Deque. Return true if the operation is successful. */
       bool deleteFront() { 
           if(isEmpty())
               return false;
           front = (front+1)%length;
           return true;
       }
       
       /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
       bool deleteLast() { 
           if(isEmpty())
               return false;
           rear = (rear-1+length)%length;
           return true;
    
       }
       
       /** Get the front item from the deque. */
       int getFront() { 
           if(isEmpty())
               return -1;
           return queue[front];
       }
       
       /** Get the last item from the deque. */
       int getRear() { 
           if(isEmpty())
               return -1;
           return queue[(rear-1+length)%length];
       }
       
       /** Checks whether the circular deque is empty or not. */
       bool isEmpty() { 
           if(front == rear)
               return true;
           return false;
       }
       
       /** Checks whether the circular deque is full or not. */
       bool isFull() { 
           if(front == (rear+1)%length)
               return true;
           return false;
       }
    };

[link]: https://blog.csdn.net/weixin_41672404/article/details/117622382
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20221005/0c612da1beae4c198c71a4b70d474f35.png