双端队列--java--黑马
双端队列
概述
双端队列、队列、栈对比
| 定义 | 特点 | |
|---|---|---|
| 队列 | 一端删除(头)，另一端添加(尾) | First In First Out |
| 栈 | 一端删除和添加 | First In Last Out |
| 双端队列 | 两端都可以添加和删除 |
双端队列实现
双端队列接口
public interface Deque<E> {
boolean offerFirst(E e);
boolean offerLast(E e);
public E pollFirst();
public E pollLast();
public E peekFirst();
public E peekLast();
boolean isEmpty();
boolean isFull();
}
使用双向链表实现双端队列
public class LinkedListDeque<E> implements Deque<E>, Iterable<E> {
static class Node{
Node<E> pre;
E value;
Node<E> next;
pubilc Node(Node<E> pre, E value, Node<E> next) {
this.pre = pre;
this.value = value;
this.next = next;
}
}
int capacity;
int size;
Node<E> sentinel = new Node<>(null, null, null);
public LinkedListDeque (int capacity) {
this.capacity = capacity;
sentinel.next = sentinel;
sentinel.pre = sentinel;
}
@Override
public boolean offerFirst(E value) {
if (isFull()) {
return false;
}
Node<E> a = sentinel;
Node<E> b = sentinel.next;
Node<E> added = new Node<>(a, value, b);
a.next = added;
b.pre = added;
size++;
return true;
}
@Override
public boolean offerLast(E value) {
if (isFull()) {
return false;
}
Node<E> a = sentinel.pre;
Node<E> b = sentinel;
Node<E> added = new Node<>(a, value, b);
a.next = added;
b.pre = added;
size++;
return true;
}
@Override
public E pollFirst() {
if (isEmpty()) {
return null;
}
Node<E> a = sentinel;
Node<E> removed = a.next;
Node<E> b = removed.next;
a.next = b;
b.pre = a;
size--;
return removed.value;
}
@Override
public E pollLast() {
if (isEmpty()) {
return null;
}
Node<E> b = sentinel;
Node<E> removed = b.pre;
Node<E> a = b.pre;
a.next = b;
b.pre = a;
size--;
return removed.value;
}
@Override
public E peekFirst() {
if (isEmpty()) {
return null;
}
return sentinel.next.value;
}
@Override
public E peekFirst() {
if (isEmpty()) {
return null;
}
return sentinel.pre.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;
}
}
}
}
使用数组实现
public class ArrayDeque<E> implements Deque<E>, Iterable<E> {
static int inc(int i, int length) {
if(i + 1 > length) {
return 0;
}
return i + 1;
}
static int des(int i, int length) {
if (i - 1 < 0) {
return length - 1;
}
return i - 1;
}
E[] array;
int head;
int tail;
public ArrayDeque(int capacity) {
this.array = (E[]) new Object[capacity + 1];
}
@Override
public boolean offerFirst(E value) {
if (isFull()) {
return false;
}
head = des(head, array.length);
array[head] = value;
return true;
}
@Override
public boolean offerLast(E value) {
if (isFull()) {
return false;
}
array[tail] = value;
tail = inc(tail, array.length);
return true;
}
@Override
public E pollFirst() {
if (isEmpty()) {
return null;
}
E value = array[head];
array[head] = null;
head = inc(head, array.length);
return value;
}
@Override
public E pollLast() {
if (isEmpty()) {
return null;
}
tail = des(tail, array.length);
E value = array[tail];
array[tail] = null;
return value;
}
@Override
public E peekFirst() {
if (isEmpty()) {
return null;
}
return array[head];
}
@Override
public E peekFirst() {
if (isEmpty()) {
return null;
}
tail = des(tail, array.length);
return array[tail];
}
@Override
public boolean isEmpty() {
return head == tail;
}
@Override
public boolean isFull() {
if (head < tail) {
return tail - head = array.length - 1;
} else if (head > tail) {
return head - tail == 1;
} else {
return false;
}
}
@Override
public Iterator<E> iterator() {
int p = head;
return new iterator() {
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public E next() {
E value = array[p];
p = inc(p, array.length);
return value;
}
}
}
}
Leetcode102
public class Leetcode102 {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int c1 = 1;
while (!queue.isEmpty()) {
int c2 = 0;
List<Integer> list = new ArrayList<>();
for(int i = 0; i < c1; i++) {
TreeNode n = queue.poll();
list.add(n.val);
if (n.left != null) {
queue.offer(n.left);
c2++;
}
if (n.right != null) {
queue.offer(n.right);
c2++;
}
}
res.add(list);
c1 = c2;
}
return res;
}
}
Leetcode103
pubic class Leetcode103{
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int c1 = 1;
boolean odd = true;
while (!queue.isEmpty()) {
int c2 = 0;
LinkedList<Integer> list = new LinkedList<>();
for(int i = 0; i < c1; i++) {
TreeNode n = queue.poll();
if (odd) {
list.offerLast(n.val);
} else {
list.offerFirst(n.val);
}
if (n.left != null) {
queue.offer(n.left);
c2++;
}
if (n.right != null) {
queue.offer(n.right);
c2++;
}
}
res.add(list);
c1 = c2;
odd = !odd;
}
return res;
}
}