【数据结构与算法】(7)基础数据结构之双端队列的链表实现、环形数组实现示例讲解
目录
- 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：
不同语言，操作双端队列的方法命名有所不同，参见下表
操作 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 吐槽一下 leetCode 命名比较 low
常见的单词还有 enqueue 入队、dequeue 出队
接口定义
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> {
@Override
public 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;
}
@Override
public 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;
}
@Override
public 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;
}
@Override
public 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;
}
@Override
public E peekFirst() {
if (isEmpty()) {
return null;
}
return sentinel.next.value;
}
@Override
public E peekLast() {
if (isEmpty()) {
return null;
}
return sentinel.prev.value;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == capacity;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
Node<E> p = sentinel.next;
@Override
public boolean hasNext() {
return p != sentinel;
}
@Override
public 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> {
/*
h
t
0 1 2 3
b a
*/
@Override
public boolean offerFirst(E e) {
if (isFull()) {
return false;
}
head = dec(head, array.length);
array[head] = e;
return true;
}
@Override
public boolean offerLast(E e) {
if (isFull()) {
return false;
}
array[tail] = e;
tail = inc(tail, array.length);
return true;
}
@Override
public E pollFirst() {
if (isEmpty()) {
return null;
}
E e = array[head];
array[head] = null;
head = inc(head, array.length);
return e;
}
@Override
public E pollLast() {
if (isEmpty()) {
return null;
}
tail = dec(tail, array.length);
E e = array[tail];
array[tail] = null;
return e;
}
@Override
public E peekFirst() {
if (isEmpty()) {
return null;
}
return array[head];
}
@Override
public E peekLast() {
if (isEmpty()) {
return null;
}
return array[dec(tail, array.length)];
}
@Override
public boolean isEmpty() {
return head == tail;
}
@Override
public boolean isFull() {
if (tail > head) {
return tail - head == array.length - 1;
} else if (tail < head) {
return head - tail == 1;
} else {
return false;
}
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p = head;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public 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 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);
}
}
}