左神算法学习笔记 - 016【入门】双端队列-双链表和固定数组实现

https://www.bilibili.com/video/BV1PM4y1p7N5/?spm_id_from=333.1387.search.video_card.click&vd_source=1e87b7eb823207ca7c9387414a18dfd0

641. 设计循环双端队列

双端队列，就是既可以从头入队，也可以从尾入队，既可以从头出队，也可以从尾出队的结构。

实际上，如果会了之前的循环队列题目的思路，用固定数组实现双端队列已经可以自己实现了。

学习 Java 中双端队列的用法

之前学习过的 Java 中的队列实现之一 LinkedList 实际上也是一个双端队列（Deque 接口的实现）。

这道题目最简单的偷懒做法就是使用语言自带的双端队列，只不过按照题目要求，这个队列是有容量的，因此还需要 size 和 limit 帮助判空和判满：

class MyCircularDeque1 {

		public Deque<Integer> deque = new LinkedList<>();
		public int size;
		public int limit;

		public MyCircularDeque1(int k) {
			size = 0;
			limit = k;
		}

		public boolean insertFront(int value) {
			if (isFull()) {
				return false;
			} else {
				deque.offerFirst(value);
				size++;
				return true;
			}
		}

		public boolean insertLast(int value) {
			if (isFull()) {
				return false;
			} else {
				deque.offerLast(value);
				size++;
				return true;
			}
		}

		public boolean deleteFront() {
			if (isEmpty()) {
				return false;
			} else {
				size--;
				deque.pollFirst();
				return true;
			}
		}

		public boolean deleteLast() {
			if (isEmpty()) {
				return false;
			} else {
				size--;
				deque.pollLast();
				return true;
			}
		}

		public int getFront() {
			if (isEmpty()) {
				return -1;
			} else {
				return deque.peekFirst();
			}
		}

		public int getRear() {
			if (isEmpty()) {
				return -1;
			} else {
				return deque.peekLast();
			}
		}

		public boolean isEmpty() {
			return size == 0;
		}

		public boolean isFull() {
			return size == limit;
		}

	}

用数组实现双端队列

实际上，这道题和之前的循环队列非常像，如果掌握了那道题的写法，用两个下标配合边界调转的规则，一样可以直接写出这里需要的双端队列。

class MyCircularDeque {

    public int[] queue;
    public int l, r, size, limit;

    public MyCircularDeque(int k) {
        queue = new int[k];
        l = r = size = 0;
        limit = k;
    }
    
    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        } else {
            l = (l == 0) ? (limit - 1) : (l - 1);
            queue[l] = value;
            size++;
            return true;
        }
    }
    
    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        } else {
            queue[r] = value;
            r = (r == limit - 1) ? 0 : (r + 1);
            size++;
            return true;
        }
    }
    
    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        } else {
            l = (l == limit - 1) ? 0 : (l + 1);
            size--;
            return true;
        }
    }
    
    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        } else {
            r = (r == 0) ? (limit - 1) : (r - 1);
            size--;
            return true;
        }
    }
    
    public int getFront() {
        if (isEmpty()) {
            return -1;
        } else {
            return queue[l];
        }
    }
    
    public int getRear() {
        if (isEmpty()) {
            return -1;
        } else {
            int last = (r == 0) ? (limit - 1) : (r - 1);
            return queue[last];
        }
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == limit;
    }
}

当然，左神也给了一个版本稍微不同的写法，稍有不同的地方在于边界的处理。在理解的情况下，我只想记一种写法，即 [l, r) 是队列的范围。

下面这种写法只做记录：

class MyCircularDeque2 {

		public int[] deque;
		public int l, r, size, limit;

		public MyCircularDeque2(int k) {
			deque = new int[k];
			l = r = size = 0;
			limit = k;
		}

		public boolean insertFront(int value) {
			if (isFull()) {
				return false;
			} else {
				if (isEmpty()) {
					l = r = 0;
					deque[0] = value;
				} else {
					l = l == 0 ? (limit - 1) : (l - 1);
					deque[l] = value;
				}
				size++;
				return true;
			}
		}

		public boolean insertLast(int value) {
			if (isFull()) {
				return false;
			} else {
				if (isEmpty()) {
					l = r = 0;
					deque[0] = value;
				} else {
					r = r == limit - 1 ? 0 : (r + 1);
					deque[r] = value;
				}
				size++;
				return true;
			}
		}

		public boolean deleteFront() {
			if (isEmpty()) {
				return false;
			} else {
				l = (l == limit - 1) ? 0 : (l + 1);
				size--;
				return true;
			}
		}

		public boolean deleteLast() {
			if (isEmpty()) {
				return false;
			} else {
				r = r == 0 ? (limit - 1) : (r - 1);
				size--;
				return true;
			}
		}

		public int getFront() {
			if (isEmpty()) {
				return -1;
			} else {
				return deque[l];
			}
		}

		public int getRear() {
			if (isEmpty()) {
				return -1;
			} else {
				return deque[r];
			}
		}

		public boolean isEmpty() {
			return size == 0;
		}

		public boolean isFull() {
			return size == limit;
		}

	}