Skip to content

Commit daa1066

Browse files
dunwudunwu
committed
update codes
1 parent 7e29ee6 commit daa1066

File tree

8 files changed

+405
-74
lines changed

8 files changed

+405
-74
lines changed

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/queue/CircularQueue.java‎

Lines changed: 0 additions & 47 deletions
This file was deleted.

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/queue/GenericQueue.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package io.github.dunwu.algorithm.queue;
2+
3+
/**
4+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
5+
* @since 2020-06-10
6+
*/
7+
public class GenericQueue<T> {
8+
9+
// 队列的队首和队尾
10+
private Node<T> head = null;
11+
private Node<T> tail = null;
12+
13+
// 入队
14+
public void enqueue(T value) {
15+
if (head == null) {
16+
tail = new Node<T>(value, null);
17+
head = tail;
18+
} else {
19+
tail.next = new Node<T>(value, null);
20+
tail = tail.next;
21+
}
22+
}
23+
24+
// 出队
25+
public T dequeue() {
26+
if (head == null) {
27+
return null;
28+
}
29+
30+
T val = head.data;
31+
head = head.next;
32+
if (head == null) {
33+
tail = null;
34+
}
35+
return val;
36+
}
37+
38+
public void printAll() {
39+
Node<T> p = head;
40+
while (p != null) {
41+
System.out.print(p.data + " ");
42+
p = p.next;
43+
}
44+
System.out.println();
45+
}
46+
47+
private static class Node<T> {
48+
49+
private T data;
50+
private Node<T> next;
51+
52+
public Node(T data, Node<T> next) {
53+
this.data = data;
54+
this.next = next;
55+
}
56+
57+
public T getData() {
58+
return data;
59+
}
60+
61+
}
62+
63+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/queue/MyCircularDeque.java‎

Lines changed: 144 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,144 @@
1+
package io.github.dunwu.algorithm.queue;
2+
3+
/**
4+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
5+
* @see <a href="https://leetcode-cn.com/problems/design-circular-deque/">641. 设计循环双端队列</a>
6+
* @since 2020-06-10
7+
*/
8+
public class MyCircularDeque {
9+
10+
public static void main(String[] args) {
11+
MyCircularDeque queue = new MyCircularDeque(3);
12+
queue.insertFront(1);
13+
queue.insertFront(2);
14+
queue.insertFront(3);
15+
queue.insertFront(4);
16+
queue.printAll();
17+
queue.deleteFront();
18+
queue.printAll();
19+
queue.deleteFront();
20+
queue.printAll();
21+
queue.deleteFront();
22+
queue.printAll();
23+
24+
queue.insertLast(1);
25+
queue.insertLast(2);
26+
queue.insertLast(3);
27+
queue.insertLast(4);
28+
queue.printAll();
29+
queue.deleteLast();
30+
queue.printAll();
31+
// System.out.println("rear: " + queue.Rear());
32+
// System.out.println("full: " + queue.isFull());
33+
// queue.deQueue();
34+
// queue.enQueue(4);
35+
// queue.printAll();
36+
// System.out.println("rear: " + queue.Rear());
37+
}
38+
39+
private int[] data;
40+
private int head;
41+
// head表示队头下标，tail表示队尾下标
42+
private int tail;
43+
private int capacity;
44+
45+
/** Initialize your data structure here. Set the size of the deque to be k. */
46+
public MyCircularDeque(int k) {
47+
this.capacity = k + 1;
48+
this.data = new int[this.capacity];
49+
}
50+
51+
/** Adds an item at the front of Deque. Return true if the operation is successful. */
52+
public boolean insertFront(int value) {
53+
if (isFull()) {
54+
return false;
55+
}
56+
57+
head = (head - 1 + capacity) % capacity;
58+
data[head] = value;
59+
return true;
60+
}
61+
62+
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
63+
public boolean insertLast(int value) {
64+
if (isFull()) {
65+
return false;
66+
}
67+
68+
this.data[tail] = value;
69+
tail = (tail + 1) % capacity;
70+
return true;
71+
}
72+
73+
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
74+
public boolean deleteFront() {
75+
if (isEmpty()) {
76+
return false;
77+
}
78+
79+
head = (head + 1) % capacity;
80+
return true;
81+
}
82+
83+
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
84+
public boolean deleteLast() {
85+
if (isEmpty()) {
86+
return false;
87+
}
88+
89+
tail = (tail - 1 + capacity) % capacity;
90+
return true;
91+
}
92+
93+
/** Get the front item from the deque. */
94+
public int getFront() {
95+
if (isEmpty()) {
96+
return -1;
97+
}
98+
99+
return data[head];
100+
}
101+
102+
/** Get the last item from the deque. */
103+
public int getRear() {
104+
if (isEmpty()) {
105+
return -1;
106+
}
107+
108+
int temp = (tail - 1 + capacity) % capacity;
109+
return data[temp];
110+
}
111+
112+
/** Checks whether the circular deque is empty or not. */
113+
public boolean isEmpty() {
114+
if (head == tail) {
115+
return true;
116+
}
117+
return false;
118+
}
119+
120+
/** Checks whether the circular deque is full or not. */
121+
public boolean isFull() {
122+
if ((tail + 1) % capacity == head) {
123+
return true;
124+
}
125+
return false;
126+
}
127+
128+
public void printAll() {
129+
if (head == tail) {
130+
System.out.println("队列已空");
131+
return;
132+
}
133+
for (int i = head; i != tail; ) {
134+
System.out.print(data[i] + "\t");
135+
if (i == capacity - 1) {
136+
i = 0;
137+
} else {
138+
i++;
139+
}
140+
}
141+
System.out.println();
142+
}
143+
144+
}

codes/algorithm/src/main/java/io/github/dunwu/algorithm/queue/DynamicArrayQueue.java renamed to codes/algorithm/src/main/java/io/github/dunwu/algorithm/queue/动态扩容数组实现的队列.java

Lines changed: 24 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,24 @@
11
package io.github.dunwu.algorithm.queue;
22

3+
import java.util.Arrays;
4+
35
/**
46
* Created by wangzheng on 2018/10/9.
57
*/
6-
public class DynamicArrayQueue {
8+
public class 动态扩容数组实现的队列 {
9+
10+
public static void main(String[] args) {
11+
动态扩容数组实现的队列 queue = new 动态扩容数组实现的队列(3);
12+
queue.enqueue("1");
13+
queue.enqueue("2");
14+
queue.enqueue("3");
15+
queue.enqueue("4");
16+
queue.printAll();
17+
System.out.println("dequeue " + queue.dequeue());
18+
queue.printAll();
19+
System.out.println("dequeue " + queue.dequeue());
20+
queue.printAll();
21+
}
722

823
// 数组：items，数组大小：n
924
private String[] items;
@@ -13,24 +28,17 @@ public class DynamicArrayQueue {
1328
private int tail = 0;
1429

1530
// 申请一个大小为capacity的数组
16-
public DynamicArrayQueue(int capacity) {
31+
public 动态扩容数组实现的队列(int capacity) {
1732
items = new String[capacity];
1833
n = capacity;
1934
}
2035

2136
// 入队操作，将item放入队尾
2237
public boolean enqueue(String item) {
23-
// tail == n表示队列末尾没有空间了
38+
// 队列已满，扩容
2439
if (tail == n) {
25-
// tail ==n && head==0，表示整个队列都占满了
26-
if (head == 0) return false;
27-
// 数据搬移
28-
for (int i = head; i < tail; ++i) {
29-
items[i - head] = items[i];
30-
}
31-
// 搬移完之后重新更新head和tail
32-
tail -= head;
33-
head = 0;
40+
n = n * 2;
41+
items = Arrays.copyOf(items, n);
3442
}
3543

3644
items[tail] = item;
@@ -42,10 +50,10 @@ public boolean enqueue(String item) {
4250
public String dequeue() {
4351
// 如果head == tail 表示队列为空
4452
if (head == tail) return null;
45-
// 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
46-
String ret = items[head];
47-
++head;
48-
return ret;
53+
String val = items[head];
54+
items = Arrays.copyOfRange(items, 1, tail);
55+
tail--;
56+
return val;
4957
}
5058

5159
public void printAll() {

codes/algorithm/src/main/java/io/github/dunwu/algorithm/queue/ArrayQueue.java renamed to codes/algorithm/src/main/java/io/github/dunwu/algorithm/queue/数组实现的队列.java

Lines changed: 16 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,23 @@
11
package io.github.dunwu.algorithm.queue;
22

33
/**
4+
* 用数组实现的队列
45
* Created by wangzheng on 2018/10/9.
56
*/
6-
// 用数组实现的队列
7-
public class ArrayQueue {
7+
public class 数组实现的队列 {
8+
9+
public static void main(String[] args) {
10+
数组实现的队列 queue = new 数组实现的队列(3);
11+
queue.enqueue("1");
12+
queue.enqueue("2");
13+
queue.enqueue("3");
14+
queue.enqueue("4");
15+
queue.printAll();
16+
System.out.println("dequeue " + queue.dequeue());
17+
queue.printAll();
18+
System.out.println("dequeue " + queue.dequeue());
19+
queue.printAll();
20+
}
821

922
// 数组：items，数组大小：n
1023
private String[] items;
@@ -14,7 +27,7 @@ public class ArrayQueue {
1427
private int tail = 0;
1528

1629
// 申请一个大小为capacity的数组
17-
public ArrayQueue(int capacity) {
30+
public 数组实现的队列(int capacity) {
1831
items = new String[capacity];
1932
n = capacity;
2033
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/queue/最近的请求次数.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package io.github.dunwu.algorithm.queue;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
/**
7+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
8+
* @see <a href="https://leetcode-cn.com/problems/number-of-recent-calls/">933. 最近的请求次数</a>
9+
* @since 2020-06-10
10+
*/
11+
public class 最近的请求次数 {
12+
13+
Queue<Integer> queue;
14+
15+
public 最近的请求次数() {
16+
queue = new LinkedList<>();
17+
}
18+
19+
public int ping(int t) {
20+
queue.add(t);
21+
while (queue.peek() < t - 3000) { queue.poll(); }
22+
return queue.size();
23+
}
24+
25+
}

0 commit comments

Comments
 (0)