本文主要是介绍数据结构与算法-08_双端队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 1.概述
- 2.链表实现
- 3.数组实现
- 4.习题
- E01. 二叉树 Z 字层序遍历-Leetcode 103
1.概述
定义 | 特点 | |
---|---|---|
队列 | 一端删除(头)另一端添加(尾) | First In First Out |
栈 | 一端删除和添加(顶) | Last In First Out |
双端队列 | 两端都可以删除、添加 | |
优先级队列 | 优先级高者先出队 | |
延时队列 | 根据延时时间确定优先级 | |
并发非阻塞队列 | 队列空或满时不阻塞 | |
并发阻塞队列 | 队列空时删除阻塞、队列满时添加阻塞 |
注1:
- Java 中 LinkedList 即为典型双端队列实现,不过它同时实现了 Queue 接口,也提供了栈的 push pop 等方法
注2:
不同语言,操作双端队列的方法命名有所不同,参见下表
操作 Java JavaScript C++ leetCode 641 尾部插入 offerLast push push_back insertLast 头部插入 offerFirst unshift push_front insertFront 尾部移除 pollLast pop pop_back deleteLast 头部移除 pollFirst shift pop_front deleteFront 尾部获取 peekLast at(-1) back getRear 头部获取 peekFirst at(0) front getFront
接口定义
public interface Deque<E> {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 LinkedListDeque<E> implements Deque<E>, Iterable<E> {@Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}size++;Node<E> a = sentinel;Node<E> b = sentinel.next;Node<E> offered = new Node<>(a, e, b);a.next = offered;b.prev = offered;return true;}@Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}size++;Node<E> a = sentinel.prev;Node<E> b = sentinel;Node<E> offered = new Node<>(a, e, b);a.next = offered;b.prev = offered;return true;}@Overridepublic E pollFirst() {if (isEmpty()) {return null;}Node<E> a = sentinel;Node<E> polled = sentinel.next;Node<E> b = polled.next;a.next = b;b.prev = a;size--;return polled.value;}@Overridepublic E pollLast() {if (isEmpty()) {return null;}Node<E> polled = sentinel.prev;Node<E> a = polled.prev;Node<E> 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 Iterator<E> iterator() {return new Iterator<E>() {Node<E> p = sentinel.next;@Overridepublic boolean hasNext() {return p != sentinel;}@Overridepublic E next() {E value = p.value;p = p.next;return value;}};}static class Node<E> {Node<E> prev;E value;Node<E> next;public Node(Node<E> prev, E value, Node<E> next) {this.prev = prev;this.value = value;this.next = next;}}Node<E> 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>* <li>tail 停下来的位置不存储, 会浪费一个位置</li>* </ul>* @param <E>*/
public class ArrayDeque1<E> implements Deque<E>, Iterable<E> {/*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 Iterator<E> iterator() {return new Iterator<E>() {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,以便内存及时释放
4.习题
E01. 二叉树 Z 字层序遍历-Leetcode 103
public class E01Leetcode103 {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}LinkedList<TreeNode> queue = new LinkedList<>();queue.offer(root);boolean leftToRight = true;int c1 = 1;while (!queue.isEmpty()) {int c2 = 0;LinkedList<Integer> 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)));List<List<Integer>> lists = new E01Leetcode103().zigzagLevelOrder(root);for (List<Integer> list : lists) {System.out.println(list);}}
}
这篇关于数据结构与算法-08_双端队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!