队列与栈

Array 实现 Queue

和 Java 中的 ArrayDequeue 实现类似,记录队列头部和尾部的索引实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Queue<E> {
private E[] data;
private int N;
private int frontIdx;
private int tailIdx;

public Queue(int capacity) {
data = (E[]) new Object[capacity];
frontIdx = 0;
tailIdx = 0;
N = 0;
}

public boolean isEmpty() {
return N == 0;
}

public int size() {
return N;
}

public void enqueue(E e) {
if (N == data.length)
throw new IllegalArgumentException("LinkedQueue is full.");
data[tailIdx] = e;
tailIdx = (tailIdx + 1) % data.length;
N++;
}

public E dequeue() {
if (isEmpty())
throw new NoSuchElementException("LinkedQueue is empty.");
E oldFront = data[frontIdx];
data[frontIdx] = null;
frontIdx = (frontIdx + 1) % data.length;
N--;
return oldFront;
}

public E peek() {
if (isEmpty())
throw new NoSuchElementException("LinkedQueue is empty.");
return data[frontIdx];
}
}

Array 实现 Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.NoSuchElementException;

public class Stack<E> {
private E[] data;
private int N;

public Stack(int capacity) {
data = (E[]) new Object[capacity];
N = 0;
}

public boolean isEmpty() {
return N == 0;
}

public int size() {
return N;
}

public void push(E e) {
if (N == data.length)
throw new NoSuchElementException("Stack is empty.");
data[N] = e;
N++;
}

public E pop() {
if (isEmpty())
throw new NoSuchElementException("Stack is empty.");
E oldTop = data[N - 1];
data[N - 1] = null;
N--;
return oldTop;
}

public E peek() {
if (isEmpty())
throw new NoSuchElementException("Stack is empty.");
return data[N - 1];
}
}

Stack 实现 Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.NoSuchElementException;
import java.util.Stack;

class MyQueue {
private Stack<Integer> in = new Stack<>();
// peek element always is first put element when pop or peek operation
private Stack<Integer> out = new Stack<>();

public void push(int x) {
in.push(x);
}

public int pop() {
if (empty()) {
throw new NoSuchElementException();
}

in2out();
return out.pop();
}

public int peek() {
if (empty()) {
throw new NoSuchElementException();
}

in2out();
return out.peek();
}

public boolean empty() {
return in.isEmpty() && out.isEmpty();
}

private void in2out() {
// maintain out first pop is first input
if (out.isEmpty()) {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
}
}

Queue 实现 Stack

两个队列实现, 在弹出时进行结构调整 peek, poll O(N) push O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;

class MyStack {
private Queue<Integer> data = new LinkedList<>();
private Queue<Integer> help = new LinkedList<>();

public void push(int x) {
data.offer(x);
}

public int pop() {
if (empty())
throw new NoSuchElementException();
while (data.size() > 1)
help.offer(data.poll());
int oldTop = data.poll();
swap();
return oldTop;
}

public int top() {
if (empty())
throw new NoSuchElementException();
while (data.size() > 1)
help.offer(data.poll());
int top = data.poll();
help.offer(top);
swap();
return top;
}

public boolean empty() {
return data.isEmpty();
}

private void swap() {
Queue<Integer> t = data;
data = help;
help = t;
}
}

方式二: 一个队列实现

同一个队列实现, 将队尾元素重新插入到队首元素实现逆序 push O(N) pop O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;

class MyStack2 {
private Queue<Integer> queue = new LinkedList<>();

public void push(int x) {
queue.offer(x);
int cnt = queue.size();
// reverse queue element, offer(poll())
while (cnt-- > 1) {
queue.offer(queue.poll());
}
}

public int pop() {
if (empty())
throw new NoSuchElementException();
return queue.poll();
}

public int top() {
if (empty())
throw new NoSuchElementException();
return queue.peek();
}

public boolean empty() {
return queue.isEmpty();
}
}

猫狗队列

实现一种狗猫队列的结构,要求如下: 用户可以调用

1
2
3
4
5
6
7
add        方法,将cat类或dog类的实例放入队列中; 用户可以调用
pollAll 方法,将队列中所有的实例按照进队列的先后顺序依次弹出; 用户可以调用
pollDog 方法,将队列中dog类的实例按照进队列的先后顺序依次弹出; 用户可以调用
pollCat 方法,将队列中cat类的实例按照进队列的先后顺序依次弹出; 用户可以调用
isEmpty 方法,检查队列中是否还有dog或cat的实例; 用户可以调用
isDogEmpty 方法,检查队列中是否有dog类的实例; 用户可以调用
isCatEmpty 方法,检查队列中是否有cat类的实例。

每个 Pet 加入时通过 index 标识次序, 用于弹出时比较. 分开存储, Cat、Dog 分别存放到一个队列中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
public class Pet {
private String type;

public Pet(String type) {
this.type = type;
}

public String getPetType() {
return this.type;
}
}
public class Cat extends Pet {
public Cat() {
super("cat");
}
}

public class Dog extends Pet {
public Dog() {
super("dog");
}
}
import java.util.LinkedList;
import java.util.Queue;

public class CatDogQueue {
private Queue<WrappedPet> dogs = new LinkedList<>();
private Queue<WrappedPet> cats = new LinkedList<>();
private int sequence; // as index to keep order

public boolean isEmpty() {
return dogs.isEmpty() && cats.isEmpty();
}

public boolean isCatEmpty() {
return cats.isEmpty();
}

public boolean isDogEmpty() {
return dogs.isEmpty();
}

public void offer(Pet pet) {
// add pet to different queue by pet type
if (pet instanceof Dog) {
dogs.add(new WrappedPet(pet, sequence++));
} else if (pet instanceof Cat) {
cats.add(new WrappedPet(pet, sequence++));
} else {
throw new IllegalArgumentException("not a dog or cat");
}
}

public Pet poll() {
if (isEmpty()) {
throw new IllegalArgumentException("queue is empty");
}

// one queue is empty
if (dogs.isEmpty()) {
return cats.poll().getPet();
}
if (cats.isEmpty()) {
return dogs.poll().getPet();
}

// compare sequence number
return dogs.peek().getCount() < cats.peek().getCount() ?
dogs.poll().getPet() :
cats.poll().getPet();
}

public Cat pollCat() {
if (cats.isEmpty()) {
throw new IllegalArgumentException("have no cat");
}

return (Cat) cats.poll().getPet();
}

public Dog pollDog() {
if (dogs.isEmpty()) {
throw new IllegalArgumentException("have no dog");
}

return (Dog) dogs.poll().getPet();
}

static class WrappedPet {
private Pet pet;
private int count;

public WrappedPet(Pet pet, int count) {
this.pet = pet;
this.count = count;
}

public Pet getPet() {
return pet;
}

public int getCount() {
return count;
}
}
}

带有最小值的栈

min 栈与 data 栈存放元素个数不一致

min 栈只存放小元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.NoSuchElementException;
import java.util.Stack;

class MinStack {
private Stack<Integer> data = new Stack<>();
private Stack<Integer> min = new Stack<>();

public void push(int x) {
if (data.isEmpty() || x <= min.peek()) {
min.push(x);
}
data.push(x);
}

public void pop() {
if (data.isEmpty())
throw new NoSuchElementException();
if (data.peek().equals(min.peek()))
min.pop();
data.pop();
}

public int top() {
if (data.isEmpty())
throw new NoSuchElementException();
return data.peek();
}

public int getMin() {
if (data.isEmpty())
throw new NoSuchElementException();
return min.peek();
}
}

其他

LRU 实现

leetcode

1
2
3
4
5
6
7
8
9
10
LRUCache cache = new LRUCache( 2 );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

使用构建一个双向链表来维护 LRU 的关系,一个 Map 对应 element value → Node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.HashMap;

class LRUCache {
private HashMap<Integer, Node> cache;
private int capacity;
private Node head;
private Node tail;

private class Node {
Node prev;
Node next;
Integer key;
Integer val;

public Node(Integer k, Integer v) {
this.key = k;
this.val = v;
}
}

public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>(capacity * 4 / 3);
}

public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
Node node = cache.get(key);
remove(node);
setHead(node);
return node.val;
}

public void put(int key, int value) {
if (cache.containsKey(key)) {
Node oldNode = cache.get(key);
oldNode.val = value;
remove(oldNode);
setHead(oldNode);
} else {
Node newNode = new Node(key, value);
if (cache.size() >= capacity) {
System.out.println("Cache is FULL! Removing " + tail.val + " from cache...");
cache.remove(tail.key);
remove(tail);
}
setHead(newNode);
cache.put(key, newNode);
}
}

// remove from list node, note head tail edge
private void remove(Node node) {
if (node.prev != null) {
node.prev.next = node.next;
} else {
head = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
} else {
tail = node.prev;
}
}

// make node(newNode or accessed node) to head
private void setHead(Node node) {
node.next = head;
node.prev = null;

// init or remove no element
if (head != null) {
head.prev = node;
}
head = node;

// init or remove no element
if (tail == null) {
tail = head;
}
}
}

LFU 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
headList
1 <-> 3 <-> 4 <-> 7
F G H I
^ ^ ^ ^
| | | |
v v v v
A D
^
|
v
C
^
|
v
E

数据流中的中位数

nowcoder

思路: 原始拆分存储在不同的容器中 通过维护左右两个堆实现, 左边的为最大堆, 右边的为最小堆 插入元素时, 若当前容器大小为偶数, 通过先放入右边的最大堆, 之后弹出左边最大堆的堆顶元素放入右边的最小堆实现有序性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.NoSuchElementException;
import java.util.PriorityQueue;

public class Solution {
// max heap
private PriorityQueue<Integer> leftSmall = new PriorityQueue<>((o1, o2) -> o2 - o1);
// min heap
private PriorityQueue<Integer> rightBig = new PriorityQueue<>();
private int N;

public void Insert(Integer num) {
if (N % 2 == 0) { // even, put rightBig AND ordered
leftSmall.offer(num);
rightBig.offer(leftSmall.poll());
} else { // odd, right N/2+1
rightBig.offer(num);
leftSmall.offer(rightBig.poll());
}
N++;
}

public Double GetMedian() {
if (isEmpty())
throw new NoSuchElementException();
if (N % 2 == 0)
return (leftSmall.peek() + rightBig.peek()) / 2.0;
else
return (double) rightBig.peek();
}

public boolean isEmpty() {
return leftSmall.isEmpty() && rightBig.isEmpty();
}
}

BiMap

一对一的映射

一个 Map 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.HashMap;
import java.util.Map;

class OneToOneMap<K, V> {
private Map<K, V> map = new HashMap<>();

public V get(K key) {
return map.get(key);
}

public boolean put(K key, V val) {
if (map.containsKey(key)) {
if (!map.get(key).equals(val))
return false;
} else {
// O(n)
if (map.containsValue(val))
return false;
map.put(key, val);
}
return true;
}
}

两个 Map 实现

分别保存 key 和 val,使用一个 sequence 来唯一确定是否相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

class OneToOneMap2<K, V> {
private Map<K, Integer> map1 = new HashMap<>();
private Map<V, Integer> map2 = new HashMap<>();
private int sequence;

// O(1)
public boolean put(K key, V val) {
Integer keyReplace = map1.put(key, sequence);
Integer valReplace = map2.put(val, sequence);
if (Objects.equals(keyReplace, valReplace) == false) {
return false;
}
sequence++;
return true;
}
}

带有最大值的滑动窗口

leetcode-sliding-window-maximum

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

方式一: 单调的双向队列实现

offer, poll O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.Deque;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;

public class MaxQueue {
// keep original enqueue order
private Queue<Tuple> queue = new LinkedList<>();
// Monotone decreasing, last element is max
private Deque<Tuple> qmax = new LinkedList<>();
// increasing sequence
private int sequencer = 0;

public void offer(int val) {
// poll not meet to main monotonicity
while (!qmax.isEmpty() && val >= qmax.peekLast().val) {
qmax.pollLast();
}

Tuple tuple = new Tuple(val, sequencer++);
queue.offer(tuple);
qmax.offerLast(tuple);
}

public int poll() {
if (queue.isEmpty()) {
throw new NoSuchElementException();
}
Tuple oldFront = queue.poll();
// remove relate max value
if (qmax.peekFirst().idx == oldFront.idx) {
qmax.pollFirst();
}
return oldFront.val;
}

public int max() {
if (queue.isEmpty()) {
throw new NoSuchElementException();
}
return qmax.peekFirst().val;
}

// wrapped value with idx to record original put order
static class Tuple {
int val;
int idx;

Tuple(int val, int idx) {
this.val = val;
this.idx = idx;
}
}
}

方式二: 使用堆实现

offer, poll O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;

public class MaxQueue2 {
Queue<Integer> queue = new LinkedList<>();
PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);

public void offer(int e) {
queue.offer(e);
heap.offer(e);
}

public int poll() {
if (isEmpty())
throw new NoSuchElementException();
int oldFront = queue.poll();
if (oldFront == heap.peek())
heap.poll(); // time: O(nlogn)
return oldFront;
}

public int peek() {
if (isEmpty())
throw new NoSuchElementException();
return queue.peek();
}

// O(1) 获取队列中的最大值
public int max() {
if (isEmpty())
throw new NoSuchElementException();
return heap.peek();
}

public boolean isEmpty() {
return queue.isEmpty();
}

public int size() {
return queue.size();
}
}

方式三: 使用 MaxStack 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.NoSuchElementException;
import java.util.Stack;

public class MaxQueue3 {

static class MaxStack {
private Stack<Integer> data = new Stack<>();
private Stack<Integer> max = new Stack<>();

public void push(int e) {
if (max.isEmpty()) {
max.push(e);
} else if (e >= max.peek()) {
max.push(e);
}
data.push(e);
}

public int pop() {
if (data.isEmpty())
throw new NoSuchElementException();
Integer oldTop = data.pop();
if (max.peek() == oldTop)
max.pop();
return oldTop;
}

public int peek() {
if (data.isEmpty())
throw new NoSuchElementException();
return data.peek();
}

public int max() {
if (max.isEmpty())
throw new NoSuchElementException();
return max.peek();
}

public boolean isEmpty() {
return data.isEmpty();
}

public int size() {
return data.size();
}
}

private MaxStack in = new MaxStack();
private MaxStack out = new MaxStack();

public void offer(int e) {
in.push(e);
}

public int poll() {
if (isEmpty())
throw new NoSuchElementException();
if (out.isEmpty()) {
while (!in.isEmpty())
out.push(in.pop());
}
return out.pop();
}

public int peek() {
if (isEmpty())
throw new NoSuchElementException();
if (out.isEmpty())
while (!in.isEmpty())
out.push(in.pop());
return out.peek();
}

// O(1) 获取队列中的最大值
public int max() {
if (isEmpty())
throw new NoSuchElementException();
return Math.max(in.isEmpty() ? Integer.MIN_VALUE : in.max(),
out.isEmpty() ? Integer.MIN_VALUE : out.max());
}

public boolean isEmpty() {
return in.isEmpty() && out.isEmpty();
}

public int size() {
return in.size() + out.size();
}
}

数据流中第一个重复元素

nowcoder

通过 Map 记录当前所有字节流中的词频, loopArrQueue 保留原始的字节流插入顺序,同时保证 loopArrQueue 的队首元素词频为 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Solution {
private Map<Character, Integer> freqs = new HashMap<>();
// record original sequence
private Queue<Character> queue = new LinkedList<>();

public void Insert(char ch) {
freqs.put(ch, freqs.getOrDefault(ch, 0) + 1);
queue.offer(ch);
while (!queue.isEmpty() && freqs.get(queue.peek()) > 1) {
queue.poll(); // pop head of queue and keep head freq is 1
}
}

public char FirstAppearingOnce() {
if (queue.isEmpty()) {
return '#';
}
return queue.peek();
}
}