数据结构-循环队列和循环双端队列的多角度实现

文章目录

- - 1. 循环队列的数组形式实现
  - 2. 循环队列的链表实现
  - 3. 循环双端队列的数组形式实现
  - 4. 循环双端队列的链表实现

在力扣的题面如下

1. 循环队列的数组形式实现

其实循环队列的数组形式只有下面要注意的点,只要掌握了下面的这几点,代码层面上就没有什么问题了

用数组模拟的思路跟循环单向队列是完全一致的,要记住下面的几个点

1 . first 指向的是头元素的下标 , last 指向的是尾元素的下一个位置的下标
2 . 在申请数组空间的时候要多申请一个空间的目的是,讲判断空与判断满的条件区分开

判断空就是 first == last 判断满就是 "first的下一个" == last;

3 . 在循环队列里面,如何++,如何–?

++ : (first + 1) % len  ;  (last + 1) % len;

-- : (first - 1 + len) % len  ;  (last - 1 + len) % len

4 . 元素的个数 size == (last - fist + len) % len;

下面是数组形式的实现代码

java">class MyCircularQueue {int[] elementData;int first;int last;public MyCircularQueue(int k) {elementData = new int[k + 1];}public boolean enQueue(int value) {if(isFull()){return false;}elementData[last] = value;last = (last + 1)%  elementData.length;return true;}public boolean deQueue() {if(isEmpty()){return false;}first = (first + 1)%elementData.length;return true;}public int Front() {if(isEmpty()){return -1;}return elementData[first];}public int Rear() {if(isEmpty()){return  -1;}int index = last == 0 ? elementData.length - 1 : last -1;return elementData[index];}public boolean isEmpty() {return last == first;}public boolean isFull() {return first == (last + 1)  % elementData.length;}
}/*** Your MyCircularQueue object will be instantiated and called as such:* MyCircularQueue obj = new MyCircularQueue(k);* boolean param_1 = obj.enQueue(value);* boolean param_2 = obj.deQueue();* int param_3 = obj.Front();* int param_4 = obj.Rear();* boolean param_5 = obj.isEmpty();* boolean param_6 = obj.isFull();*/

2. 循环队列的链表实现

鉴于单链表的尾巴节点每次都要寻找,所以为了简便,我们采用双向链表进行模拟,注意,这里我们对于链表节点的定义就是我们LinkedList中的源码形式,有空可以去看看我们LinkedList的底层源码,这里其实就是多了个size来标记我们的链表节点数量
代码实现如下

java">
/*** 尝试用双向链表来模拟循环队列*/
public class CircleQueue {/*** 下面是根据原代码模拟的定义的节点类* @param <T>*/static class Node<T> {public T item;public Node<T> prev;public Node<T> next;public Node (Node<T> prev,T item,Node<T> next) {this.prev = prev;this.item = item;this.next = next;}}/*** 下面是所需要的基本结构*/private Node first;private Node last;private int size;private int capacity;public CircleQueue(int k) {this.size = 0;first = last = null;capacity = k;}public boolean enQueue(int value) {if(isFull()){return false;}Node<Integer> node = new Node<>(null,value,null);if(first == null && last == null){first = node;last = node;}else{last.next = node;node.prev = last;last = node;}this.size++;return true;}public boolean deQueue() {if(isEmpty()){return false;}if(last == first){last = first = null;}else{first = first.next;first.prev.next = null;first.prev.item = null;}this.size--;return true;}public int Front() {if(isEmpty()){return -1;}return (int)first.item;}public int Rear() {if(isEmpty()){return -1;}return (int)last.item;}public boolean isEmpty() {return first == null && last == null;}public boolean isFull() {return this.size == this.capacity;}
}

3. 循环双端队列的数组形式实现

用数组实现队列源码层面是我们的ArrayDeque这个类完成的,这里不再多说了,和我们的1.用数组实现循环队列是一致的

java">/*** 首先尝试是数组来模拟循环双端队列* 其次我们再用双向链表来尝试模拟一下循环双端队列* 用数组模拟的思路跟循环单向队列是完全一致的,要记住下面的几个点* 1 . first 指向的是头元素的下标 , last 指向的是尾元素的下一个位置的下标* 2 . 在申请数组空间的时候要多申请一个空间的目的是,讲判断空与判断满的条件区分开*     判断空就是 first == last 判断满就是 "first的下一个" == last;* 3 . 在循环队列里面,如何++,如何--?*     ++ : (first + 1) % len  ;  (last + 1) % len;*     -- : (first - 1 + len) % len  ;  (last - 1 + len) % len* 4 . size == (last - fist + len) % len;*/
class MyCircularDeque {int[] elementData;int first;int last;public MyCircularDeque(int k) {elementData = new int[k + 1];first = last = 0;}public boolean insertFront(int value) {if(isFull()){return false;}first = (first - 1 + elementData.length) % elementData.length;elementData[first] = value;return true;}public boolean insertLast(int value) {if(isFull()){return false;}elementData[last] = value;last = (last + 1) % elementData.length;return true;}public boolean deleteFront() {if(isEmpty()){return false;}first = (first + 1) % elementData.length;return true;}public boolean deleteLast() {if(isEmpty()){return false;}last = (last - 1 + elementData.length) % elementData.length;return true;}public int getFront() {if(isEmpty()){return -1;}return elementData[first];}public int getRear() {if(isEmpty()){return -1;}return elementData[(last - 1 + elementData.length) % elementData.length];}public boolean isEmpty() {return first == last;}public boolean isFull() {return (last + 1) % elementData.length == first;}
}

4. 循环双端队列的链表实现

其实就是比2.多了一个addFirst,和 removeLast
代码实现如下

java">
/*** 下面我们尝试使用双向链表来模拟我们的循环双端队列*/
class MyCircularDequeUseLinkedList {static class Node<T> {Node<T> prev;T item;Node<T> next;public Node(Node<T> prev,T item,Node<T> next){this.prev = prev;this.item = item;this.next = next;}}private int size;private int capacity;private Node first;private Node last;public MyCircularDequeUseLinkedList(int k) {this.size = 0;last = first = null;this.capacity = k;}public boolean insertFront(int value) {if(isFull()){return false;}Node<Integer> node = new Node<>(null,value,null);if(isEmpty()){first = last = node;}else{node.next = first;first.prev = node;first = node;}size++;return true;}public boolean insertLast(int value) {if(isFull()){return false;}Node<Integer> node = new Node<>(null,value,null);if(isEmpty()){first = last = node;}else{last.next = node;node.prev = last;last = node;}size++;return true;}public boolean deleteFront() {if(isEmpty()){return false;}if(first == last){last = first = null;}else{first = first.next;first.prev.next = null;first.prev.item = null;first.prev = null;}size--;return true;}public boolean deleteLast() {if(isEmpty()){return false;}if(last == first){first = last = null;}else{last = last.prev;last.next.prev = null;last.next.item = null;last.next = null;}size--;return true;}public int getFront() {if(isEmpty()){return -1;}return (int)first.item;}public int getRear() {if(isEmpty()){return -1;}return (int)last.item;}public boolean isEmpty() {return first == null && last == null;}public boolean isFull() {return this.size == this.capacity;}
}