LeetCode（Queue)641. Design Circular Deque

客官°小女子只卖身不卖艺 2023-09-25 19:47 50阅读 0赞

# 1.问题 #

Design your implementation of the circular double-ended queue (deque).

Implement the MyCircularDeque class:

MyCircularDeque(int k) Initializes the deque with a maximum size of k.  
boolean insertFront() Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.  
boolean insertLast() Adds an item at the rear of Deque. Returns true if the operation is successful, or false otherwise.  
boolean deleteFront() Deletes an item from the front of Deque. Returns true if the operation is successful, or false otherwise.  
boolean deleteLast() Deletes an item from the rear of Deque. Returns true if the operation is successful, or false otherwise.  
int getFront() Returns the front item from the Deque. Returns -1 if the deque is empty.  
int getRear() Returns the last item from Deque. Returns -1 if the deque is empty.  
boolean isEmpty() Returns true if the deque is empty, or false otherwise.  
boolean isFull() Returns true if the deque is full, or false otherwise.

Example 1:

> Input  
> \[“MyCircularDeque”, “insertLast”, “insertLast”, “insertFront”, “insertFront”, “getRear”, “isFull”, “deleteLast”, “insertFront”, “getFront”\]  
> \[\[3\], \[1\], \[2\], \[3\], \[4\], \[\], \[\], \[\], \[4\], \[\]\]  
> Output  
> \[null, true, true, true, false, 2, true, true, true, 4\]

> Explanation  
> MyCircularDeque myCircularDeque = new MyCircularDeque(3);  
> myCircularDeque.insertLast(1); // return True  
> myCircularDeque.insertLast(2); // return True  
> myCircularDeque.insertFront(3); // return True  
> myCircularDeque.insertFront(4); // return False, the queue is full.  
> myCircularDeque.getRear(); // return 2  
> myCircularDeque.isFull(); // return True  
> myCircularDeque.deleteLast(); // return True  
> myCircularDeque.insertFront(4); // return True  
> myCircularDeque.getFront(); // return 4

Constraints:

\-1 <= k <= 1000  
0 <= value <= 1000  
At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.

# 2. 解题思路 #

## 方法1： ##

> 一个使用双向链表实现循环双端队列的Java代码。其中，队列的头节点和尾节点是双向链表中的节点，分别代表队列的头部和尾部。为了实现循环双端队列，我们需要在插入和删除元素时进行特殊处理。  
> 具体实现思路如下：  
> 1.定义双向链表节点：节点中包含值、前驱节点和后继节点。  
> 2.定义头部和尾部节点，并初始化为空。初始化时需要将队列大小设置为给定的容量。  
> 3.实现队列的基本操作：  
> `插入元素到队头`：如果队列已满，返回 false；否则，创建一个新节点 n，并将 n 添加到队头。如果队列为空，将 n 同时设置为队头和队尾。如果队列非空，将 n 设置为原队头的前驱节点，同时更新队头指针。  
> `插入元素到队尾`：如果队列已满，返回 false；否则，创建一个新节点 n，并将 n 添加到队尾。如果队列为空，将 n 同时设置为队头和队尾。如果队列非空，将 n 设置为原队尾的后继节点，同时更新队尾指针。  
> `删除队头元素`：如果队列为空，返回 false；否则，将队头指针指向原队头的后继节点，同时将原队头的前驱节点从链表中删除。  
> `删除队尾元素`：如果队列为空，返回 false；否则，将队尾指针指向原队尾的前驱节点，同时将原队尾的后继节点从链表中删除。  
> `获取队头元素`：如果队列为空，返回 -1；否则，返回队头节点的值。  
> `获取队尾元素`：如果队列为空，返回 -1；否则，返回队尾节点的值。  
> `判断队列是否为空`：如果队列大小为 0，返回 true；否则，返回 false。  
> `判断队列是否已满`：如果队列大小等于容量，返回 true；否则，返回 false。  
> `时间复杂度`：每个操作的时间复杂度均为 O(1)。  
> `空间复杂度`：使用了双向链表来存储队列元素，因此空间复杂度为 O(N)，其中 N 是队列的容量。

## 方法2： ##

> 1.初始化：使用数组存储元素，队列的容量为 k+1，其中 k 为实际存储的元素个数。因为队列需要一个空位置作为判断队列是否为空和是否已满的依据。  
> 2.插入元素：分别在队首和队尾插入元素时，需要判断队列是否已满，如果已满则无法插入。插入元素后，需要更新队首和队尾指针的位置，分别使用取模运算和加减运算计算新的位置。  
> 3.删除元素：分别删除队首和队尾元素时，需要判断队列是否为空，如果为空则无法删除。删除元素后，需要更新队首和队尾指针的位置，分别使用取模运算和加减运算计算新的位置。  
> 4.获取元素：获取队首和队尾元素时，需要判断队列是否为空，如果为空则返回 -1。

# 3. 代码 #

## 代码1： ##

class MyCircularDeque {
        
    
        int size = 0; // 队列大小
    
        // 链表节点
        class Node {
        
            int val; // 节点值
            Node next; // 后继节点指针
            Node prev; // 前驱节点指针
            public Node(int v) {
         val = v; } // 构造函数
        }
    
        Node head; // 队头指针
        Node tail; // 队尾指针
        int capacity; // 队列容量
    
        public MyCircularDeque(int k) {
        
            size = k; // 初始化队列大小
        }
    
        // 插入元素到队头
        public boolean insertFront(int value) {
        
            if(isFull()) return false; // 如果队列已满，返回 false
    
            Node n = new Node(value); // 创建新节点
    
            if(isEmpty()) {
         // 如果队列为空
                head = tail = n; // 将新节点同时设置为队头和队尾
            } else {
        
                n.next = head; // 将新节点的后继指针指向原队头
                head.prev = n; // 将原队头的前驱指针指向新节点
                head = n; // 更新队头指针
            }
    
            capacity++; // 队列大小加 1
    
            return true; // 返回插入成功
        }
    
        // 插入元素到队尾
        public boolean insertLast(int value) {
        
            if(isFull()) return false; // 如果队列已满，返回 false
    
            Node n = new Node(value); // 创建新节点
    
            if(isEmpty()) {
         // 如果队列为空
                head = tail = n; // 将新节点同时设置为队头和队尾
            } else {
        
                tail.next = n; // 将原队尾的后继指针指向新节点
                n.prev = tail; // 将新节点的前驱指针指向原队尾
                tail = n; // 更新队尾指针
            }
    
            capacity++; // 队列大小加 1
    
            return true; // 返回插入成功
        }
    
        // 删除队头元素
        public boolean deleteFront() {
        
            if(isEmpty()) return false; // 如果队列为空，返回 false
    
            head = head.next; // 将队头指针指向原队头的后继节点
            capacity--; // 队列大小减 1
    
            return true; // 返回删除成功
        }
    
        // 删除队尾元素
        public boolean deleteLast() {
        
            if(isEmpty()) return false; // 如果队列为空，返回 false
    
            tail = tail.prev; // 将队尾指针指向原队尾的前驱节点
            capacity--; // 队列大小减 1
    
            return true; // 返回删除成功
        }
    
        // 获取队头元素
        public int getFront() {
        
            return isEmpty() ? -1 : head.val; // 如果队列为空，返回 -1；否则返回队头节点的值
        }
    
        // 获取队尾元素
        public int getRear() {
        
            return isEmpty() ? -1 : tail.val; 
        }
        public boolean isEmpty() {
        
            return capacity == 0;
        }
        
        public boolean isFull() {
        
            return capacity == size;
        }
    }

> 双向链表

class MyCircularDeque {
        
        private int maxSize, currSize; // 队列最大容量和当前元素数量
        private Node head, tail; // 队列头和尾节点
    
        public MyCircularDeque(int k) {
         // 构造函数，传入队列最大容量
            this.maxSize = k;
            this.currSize = 0;
            head = tail = new Node(-1); // 初始化头尾节点
            head.next = tail;
            tail.prev = head;
        }
        
        public boolean insertFront(int value) {
         // 在队头插入元素，传入要插入的值
            if (currSize == maxSize) {
         // 如果队列已满，无法插入
                return false;
            }
    
            Node newNode = new Node(value); // 创建一个新节点
            newNode.next = head.next; // 新节点的下一个节点为当前队头节点
            head.next = newNode; // 头节点的下一个节点指向新节点
            newNode.prev = head; // 新节点的上一个节点为头节点
            newNode.next.prev = newNode; // 新节点的下一个节点的上一个节点为新节点
            currSize++; // 当前元素数量+1
            return true; // 插入成功
        }
        
        public boolean insertLast(int value) {
         // 在队尾插入元素，传入要插入的值
            if (currSize == maxSize) {
         // 如果队列已满，无法插入
                return false;
            }
    
            Node newNode = new Node(value); // 创建一个新节点
            tail.prev.next = newNode; // 尾节点的上一个节点的下一个节点为新节点
            newNode.next = tail; // 新节点的下一个节点为尾节点
            newNode.prev = tail.prev; // 新节点的上一个节点为尾节点的上一个节点
            tail.prev = newNode; // 尾节点的上一个节点指向新节点
            currSize++; // 当前元素数量+1
            return true; // 插入成功
        }
        
        public boolean deleteFront() {
         // 删除队头元素
            if (currSize == 0) {
         // 如果队列为空，无法删除
                return false;
            }
    
            Node node = head.next; // 找到要删除的节点
            head.next = node.next; // 头节点的下一个节点指向要删除节点的下一个节点
            node.next.prev = node.prev; // 要删除节点的下一个节点的上一个节点指向要删除节点的上一个节点
            currSize--; // 当前元素数量-1
            return true; // 删除成功
        }
        
        public boolean deleteLast() {
         // 删除队尾元素
            if (currSize == 0) {
         // 如果队列为空，无法删除
                return false;
            }
    
            Node node = tail.prev; // 找到要删除的节点
            tail.prev = node.prev; // 尾节点的上一个节点指向要删除节点的上一个节点
            node.prev.next = node.next; // 要删除节点的上一个节点的下一个节点指向要删除节点的下一个节点
            currSize--; // 当前元素数量-1
            return true;// 删除成功
        }
        
        // 获取队列头部元素，若队列为空则返回 -1
        public int getFront() {
        
            return isEmpty()? -1 : head.next.value;
        }
        
        // 获取队列尾部元素，若队列为空则返回 -1
        public int getRear() {
        
            return isEmpty()? -1 : tail.prev.value;
        }
        
        // 判断队列是否为空
        public boolean isEmpty() {
        
            return currSize == 0;
        }
        
        // 判断队列是否已满
        public boolean isFull() {
        
            return currSize == maxSize;
        }
    
        // 定义节点类
        private class Node {
        
            int value;
            Node next, prev;
            Node(int value) {
        
                this.value = value;
            }
        }
    }

## 代码2： ##

class MyCircularDeque {
        
    
        int[] arr;      // 数组用来存储队列中的元素
        int front = 0, rear = -1, len = 0, size;   // front 和 rear 分别表示队头和队尾的位置，len 表示队列长度，size 表示队列最大长度
        /** Initialize your data structure here. Set the size of the deque to be k. */
        public MyCircularDeque(int k) {
        
            arr = new int[k];
            size = k;   // 初始化数组和队列最大长度
        }
       
        public boolean insertFront(int value) {
        
            if(isFull()){
           // 队列已满，无法插入元素
                return false;
            }else{
        
                front = (front - 1) % size;     // 更新队头位置，实现循环队列
                if(front < 0){
              // 如果更新后的队头位置小于 0，需要加上数组长度，实现循环
                    front += size;
                }
                arr[front] = value;     // 插入元素到队头位置
                len++;      // 更新队列长度
                //  Corner case： add Front -> get Rear
                //  这种情况也可以在 add rear 时处理
                if(len == 1){
           // 如果队列为空，更新队尾位置
                    rear = front;
                }
                return true;
            }
        }
        
        public boolean insertLast(int value) {
        
            if(isFull()){
           // 队列已满，无法插入元素
                return false;
            }else{
        
                rear = (rear + 1) % size;   // 更新队尾位置，实现循环队列
                arr[rear] = value;      // 插入元素到队尾位置
                len++;      // 更新队列长度
                return true;
            }
        }
        
    
        public boolean deleteFront() {
        
            if(isEmpty()){
              // 队列为空，无法删除元素
                return false;
            }else{
        
                front = (front + 1) % size;   // 更新队头位置，实现循环队列
                len--;      // 更新队列长度
                return true;
            }
        }
     
        public boolean deleteLast() {
        
            if(isEmpty()){
              // 队列为空，无法删除元素
                return false;
            }else{
        
                rear = (rear - 1) % size;       // 更新队尾位置，实现循环队列
                if(rear < 0){
               // 如果更新后的队尾位置小于 0，需要加上数组长度，实现循环
                    rear += size;
                }
                len--;      // 更新队列长度
                return true;
            }
        }
        
    	public int getFront() {
        
            if(isEmpty()){
        
                return -1;
            }else{
        
                return arr[front];
            }
        }
        
        /** Get the last item from the deque. */
        public int getRear() {
        
            if(isEmpty()){
        
                return -1;
            }else{
        
                return arr[rear];
            }
        }
        
        /** Checks whether the circular deque is empty or not. */
        public boolean isEmpty() {
        
            return len == 0;
        }
        
        /** Checks whether the circular deque is full or not. */
        public boolean isFull() {
        
            return len == size;
        }

class MyCircularDeque {
        
        int[] q;
        int head, tail, size, count, cap;
        /** Initialize your data structure here. Set the size of the deque to be k. */
        public MyCircularDeque(int k) {
        
            this.q = new int[k+1];
            this.head = this.count = 0;
            this.tail = 1;
            this.cap = k;
            this.size = k+1;
        }
        
        /** Adds an item at the front of Deque. Return true if the operation is successful. */
        public boolean insertFront(int value) {
        
            if (isFull()) return false;
            this.q[this.head] = value;
            this.count++;
            this.head = (this.head - 1 + this.size) % this.size;
            return true;
        }
        
        /** Adds an item at the rear of Deque. Return true if the operation is successful. */
        public boolean insertLast(int value) {
        
            if (isFull()) return false;
            this.q[this.tail] = value;
            this.count++;
            this.tail = (this.tail + 1) % this.size;
            return true;
        }
        
        /** Deletes an item from the front of Deque. Return true if the operation is successful. */
        public boolean deleteFront() {
        
            if (isEmpty()) return false;
            this.head = (this.head + 1) % this.size;
            this.count--;
            return true;
        }
        
        /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
        public boolean deleteLast() {
        
            if (isEmpty()) return false;
            this.tail = (this.tail - 1 + this.size) % this.size;
            this.count--;
            return true;
        }
        
        /** Get the front item from the deque. */
        public int getFront() {
        
            if (isEmpty()) return -1;
            int id = (this.head + 1) % this.size;
            return this.q[id];
        }
        
        /** Get the last item from the deque. */
        public int getRear() {
        
            if (isEmpty()) return -1;
            int id = (this.tail - 1 + this.size) % this.size;
            return this.q[id];
        }
        
        /** Checks whether the circular deque is empty or not. */
        public boolean isEmpty() {
        
            return this.count == 0;
        }
        
        /** Checks whether the circular deque is full or not. */
        public boolean isFull() {
        
            return this.count == this.cap;
        }
    }

class MyCircularDeque {
        
        int[] queue;    // 数组用于存储双端队列中的元素
        int front;      // 队首指针，指向队首元素
        int rear;       // 队尾指针，指向队尾元素的下一个位置
        int capacity;   // 队列容量
    
        public MyCircularDeque(int k) {
        
            capacity = k + 1;   // 实际存储 k 个元素时，队列已满，所以需要扩容 1 个位置
            queue = new int[capacity];
            front = 0;
            rear = 0;
        }
        
        public boolean insertFront(int value) {
        
            if (isFull()) {
        
                return false;
            }
            front = (front - 1 + capacity) % capacity;    // 计算新的队首位置
            queue[front] = value;   // 插入元素
            return true;
        }
        
        public boolean insertLast(int value) {
        
            if (isFull()) {
        
                return false;
            }
            queue[rear] = value;    // 插入元素
            rear = (rear + 1) % capacity;   // 计算新的队尾位置
            return true;
        }
        
        public boolean deleteFront() {
        
            if (isEmpty()) {
        
                return false;
            }
            front = (front + 1) % capacity; // 计算新的队首位置
            return true;
        }
        
        public boolean deleteLast() {
        
            if (isEmpty()) {
        
                return false;
            }
            rear = (rear - 1 + capacity) % capacity;    // 计算新的队尾位置
            return true;
        }
        
        public int getFront() {
        
            if (isEmpty()) {
        
                return -1;
            }
            return queue[front];
        }
        
        public int getRear() {
        
            if (isEmpty()) {
        
                return -1;
            }
            return queue[(rear - 1 + capacity) % capacity];
        }
        
        public boolean isEmpty() {
        
            return front == rear;
        }
        
        public boolean isFull() {
        
            return (rear + 1) % capacity == front;
        }
    }