上海市建设咨询协会网站,asp网站源码,编辑app用什么软件,手机网站不收录目录 2.6 双端队列1) 概述2) 链表实现3) 数组实现习题E01. 二叉树 Z 字层序遍历-Leetcode 103 2.6 双端队列
1) 概述
双端队列、队列、栈对比
定义特点队列一端删除#xff08;头#xff09;另一端添加#xff08;尾#xff09;First In First Out栈一端删除和添加… 目录 2.6 双端队列1) 概述2) 链表实现3) 数组实现习题E01. 二叉树 Z 字层序遍历-Leetcode 103 2.6 双端队列
1) 概述
双端队列、队列、栈对比
定义特点队列一端删除头另一端添加尾First In First Out栈一端删除和添加顶Last In First Out双端队列两端都可以删除、添加优先级队列优先级高者先出队延时队列根据延时时间确定优先级并发非阻塞队列队列空或满时不阻塞并发阻塞队列队列空时删除阻塞、队列满时添加阻塞 注1 Java 中 LinkedList 即为典型双端队列实现不过它同时实现了 Queue 接口也提供了栈的 push pop 等方法 注2 不同语言操作双端队列的方法命名有所不同参见下表 操作JavaJavaScriptCleetCode 641尾部插入offerLastpushpush_backinsertLast头部插入offerFirstunshiftpush_frontinsertFront尾部移除pollLastpoppop_backdeleteLast头部移除pollFirstshiftpop_frontdeleteFront尾部获取peekLastat(-1)backgetRear头部获取peekFirstat(0)frontgetFront 吐槽一下 leetCode 命名比较 low 常见的单词还有 enqueue 入队、dequeue 出队 接口定义
public interface DequeE {boolean offerFirst(E e);boolean offerLast(E e);E pollFirst();E pollLast();E peekFirst();E peekLast();boolean isEmpty();boolean isFull();
}2) 链表实现
/*** 基于环形链表的双端队列* param E 元素类型*/
public class LinkedListDequeE implements DequeE, IterableE {Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}size;NodeE a sentinel;NodeE b sentinel.next;NodeE offered new Node(a, e, b);a.next offered;b.prev offered;return true;}Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}size;NodeE a sentinel.prev;NodeE b sentinel;NodeE offered new Node(a, e, b);a.next offered;b.prev offered;return true;}Overridepublic E pollFirst() {if (isEmpty()) {return null;}NodeE a sentinel;NodeE polled sentinel.next;NodeE b polled.next;a.next b;b.prev a;size--;return polled.value;}Overridepublic E pollLast() {if (isEmpty()) {return null;}NodeE polled sentinel.prev;NodeE a polled.prev;NodeE b sentinel;a.next b;b.prev a;size--;return polled.value;}Overridepublic E peekFirst() {if (isEmpty()) {return null;}return sentinel.next.value;}Overridepublic E peekLast() {if (isEmpty()) {return null;}return sentinel.prev.value;}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size capacity;}Overridepublic IteratorE iterator() {return new IteratorE() {NodeE p sentinel.next;Overridepublic boolean hasNext() {return p ! sentinel;}Overridepublic E next() {E value p.value;p p.next;return value;}};}static class NodeE {NodeE prev;E value;NodeE next;public Node(NodeE prev, E value, NodeE next) {this.prev prev;this.value value;this.next next;}}NodeE sentinel new Node(null, null, null);int capacity;int size;public LinkedListDeque(int capacity) {sentinel.next sentinel;sentinel.prev sentinel;this.capacity capacity;}
}3) 数组实现
/*** 基于循环数组实现, 特点* ul* litail 停下来的位置不存储, 会浪费一个位置/li* /ul* param E*/
public class ArrayDeque1E implements DequeE, IterableE {/*ht0 1 2 3b a*/Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}head dec(head, array.length);array[head] e;return true;}Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}array[tail] e;tail inc(tail, array.length);return true;}Overridepublic E pollFirst() {if (isEmpty()) {return null;}E e array[head];array[head] null;head inc(head, array.length);return e;}Overridepublic E pollLast() {if (isEmpty()) {return null;}tail dec(tail, array.length);E e array[tail];array[tail] null;return e;}Overridepublic E peekFirst() {if (isEmpty()) {return null;}return array[head];}Overridepublic E peekLast() {if (isEmpty()) {return null;}return array[dec(tail, array.length)];}Overridepublic boolean isEmpty() {return head tail;}Overridepublic boolean isFull() {if (tail head) {return tail - head array.length - 1;} else if (tail head) {return head - tail 1;} else {return false;}}Overridepublic IteratorE iterator() {return new IteratorE() {int p head;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic E next() {E e array[p];p inc(p, array.length);return e;}};}E[] array;int head;int tail;SuppressWarnings(unchecked)public ArrayDeque1(int capacity) {array (E[]) new Object[capacity 1];}static int inc(int i, int length) {if (i 1 length) {return 0;}return i 1;}static int dec(int i, int length) {if (i - 1 0) {return length - 1;}return i - 1;}
}数组实现中如果存储的是基本类型那么无需考虑内存释放例如 但如果存储的是引用类型应当设置该位置的引用为 null以便内存及时释放 习题
E01. 二叉树 Z 字层序遍历-Leetcode 103
public class E01Leetcode103 {public ListListInteger zigzagLevelOrder(TreeNode root) {ListListInteger result new ArrayList();if (root null) {return result;}LinkedListTreeNode queue new LinkedList();queue.offer(root);boolean leftToRight true;int c1 1;while (!queue.isEmpty()) {int c2 0;LinkedListInteger deque new LinkedList();for (int i 0; i c1; i) {TreeNode n queue.poll();if (leftToRight) {deque.offerLast(n.val);} else {deque.offerFirst(n.val);}if (n.left ! null) {queue.offer(n.left);c2;}if (n.right ! null) {queue.offer(n.right);c2;}}c1 c2;leftToRight !leftToRight;result.add(deque);}return result;}public static void main(String[] args) {TreeNode root new TreeNode(new TreeNode(new TreeNode(4),2,new TreeNode(5)),1,new TreeNode(new TreeNode(6),3,new TreeNode(7)));ListListInteger lists new E01Leetcode103().zigzagLevelOrder(root);for (ListInteger list : lists) {System.out.println(list);}}
}
