Skip to content

Commit 7e29ee6

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

File tree

5 files changed

+230
-7
lines changed

5 files changed

+230
-7
lines changed

‎README.md‎

Lines changed: 14 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,6 @@
4646

4747
### 数组
4848

49-
- [ArrayDemo.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/ArrayDemo.java)
5049
- [三数之和.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/三数之和.java)
5150
- [两数之和.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/两数之和.java)
5251
- [二维数组.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/二维数组.java)
@@ -76,11 +75,6 @@
7675

7776
### 链表
7877

79-
- [LRUBaseLinkedList.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/LRUBaseLinkedList.java)
80-
- [LRUBasedArray.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/LRUBasedArray.java)
81-
- [ListNode.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/ListNode.java)
82-
- [ListUtil.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/ListUtil.java)
83-
- [SinglyLinkedList.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/SinglyLinkedList.java)
8478
- [两数相加.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/两数相加.java)
8579
- [二进制链表转整数.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/二进制链表转整数.java)
8680
- [删除排序链表中的重复元素.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/删除排序链表中的重复元素.java)
@@ -99,14 +93,27 @@
9993
- [返回倒数第 k 个节点.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/返回倒数第k个节点.java)
10094
- [链表的中间结点.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/链表的中间结点.java)
10195

96+
### 栈
97+
98+
- [三合一.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/stack/三合一.java)
99+
- [基本计算器.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/stack/基本计算器.java)
100+
- [最小栈.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/stack/最小栈.java)
101+
- [最小栈 2.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/stack/最小栈2.java)
102+
- [有效的括号.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/stack/有效的括号.java)
103+
- [栈排序.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/stack/栈排序.java)
104+
- [棒球比赛.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/stack/棒球比赛.java)
105+
- [比较含退格的字符串.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/stack/比较含退格的字符串.java)
106+
- [用栈实现队列.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/stack/用栈实现队列.java)
107+
- [用队列实现栈.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/stack/用队列实现栈.java)
108+
102109
### 字符串
103110

104111
- [二进制求和](https://github.com/dunwu/algorithm/blob/master/codes/data-structure/src/main/java/io/github/dunwu/ds/str/AddBinary.java)
105112
- [实现 strStr()](https://github.com/dunwu/algorithm/blob/master/codes/data-structure/src/main/java/io/github/dunwu/ds/str/ImplementStrstr.java)
106113
- [最长公共前缀](https://github.com/dunwu/algorithm/blob/master/codes/data-structure/src/main/java/io/github/dunwu/ds/str/LongestCommonPrefix.java)
107114
- [反转字符串](https://github.com/dunwu/algorithm/blob/master/codes/data-structure/src/main/java/io/github/dunwu/ds/str/ReverseString.java)
108115
- [反转字符串中的单词](https://github.com/dunwu/algorithm/blob/master/codes/data-structure/src/main/java/io/github/dunwu/ds/str/ReverseWordsInAString.java)
109-
- [反转字符串中的单词 III ](https://github.com/dunwu/algorithm/blob/master/codes/data-structure/src/main/java/io/github/dunwu/ds/str/ReverseWordsInAString3.java)
116+
- [反转字符串中的单词 III](https://github.com/dunwu/algorithm/blob/master/codes/data-structure/src/main/java/io/github/dunwu/ds/str/ReverseWordsInAString3.java)
110117

111118
## 📚 资料
112119

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

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package io.github.dunwu.algorithm.queue;
2+
3+
/**
4+
* Created by wangzheng on 2018/10/9.
5+
*/
6+
// 用数组实现的队列
7+
public class ArrayQueue {
8+
9+
// 数组：items，数组大小：n
10+
private String[] items;
11+
private int n = 0;
12+
// head表示队头下标，tail表示队尾下标
13+
private int head = 0;
14+
private int tail = 0;
15+
16+
// 申请一个大小为capacity的数组
17+
public ArrayQueue(int capacity) {
18+
items = new String[capacity];
19+
n = capacity;
20+
}
21+
22+
// 入队
23+
public boolean enqueue(String item) {
24+
// 如果tail == n 表示队列已经满了
25+
if (tail == n) return false;
26+
items[tail] = item;
27+
++tail;
28+
return true;
29+
}
30+
31+
// 出队
32+
public String dequeue() {
33+
// 如果head == tail 表示队列为空
34+
if (head == tail) return null;
35+
// 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
36+
String ret = items[head];
37+
++head;
38+
return ret;
39+
}
40+
41+
public void printAll() {
42+
for (int i = head; i < tail; ++i) {
43+
System.out.print(items[i] + " ");
44+
}
45+
System.out.println();
46+
}
47+
48+
}

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

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package io.github.dunwu.algorithm.queue;
2+
3+
/**
4+
* Created by wangzheng on 2018/10/9.
5+
*/
6+
public class CircularQueue {
7+
8+
// 数组：items，数组大小：n
9+
private String[] items;
10+
private int n = 0;
11+
// head表示队头下标，tail表示队尾下标
12+
private int head = 0;
13+
private int tail = 0;
14+
15+
// 申请一个大小为capacity的数组
16+
public CircularQueue(int capacity) {
17+
items = new String[capacity];
18+
n = capacity;
19+
}
20+
21+
// 入队
22+
public boolean enqueue(String item) {
23+
// 队列满了
24+
if ((tail + 1) % n == head) return false;
25+
items[tail] = item;
26+
tail = (tail + 1) % n;
27+
return true;
28+
}
29+
30+
// 出队
31+
public String dequeue() {
32+
// 如果head == tail 表示队列为空
33+
if (head == tail) return null;
34+
String ret = items[head];
35+
head = (head + 1) % n;
36+
return ret;
37+
}
38+
39+
public void printAll() {
40+
if (0 == n) return;
41+
for (int i = head; i % n != tail; i = (i + 1) % n) {
42+
System.out.print(items[i] + " ");
43+
}
44+
System.out.println();
45+
}
46+
47+
}

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

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package io.github.dunwu.algorithm.queue;
2+
3+
/**
4+
* Created by wangzheng on 2018/10/9.
5+
*/
6+
public class DynamicArrayQueue {
7+
8+
// 数组：items，数组大小：n
9+
private String[] items;
10+
private int n = 0;
11+
// head表示队头下标，tail表示队尾下标
12+
private int head = 0;
13+
private int tail = 0;
14+
15+
// 申请一个大小为capacity的数组
16+
public DynamicArrayQueue(int capacity) {
17+
items = new String[capacity];
18+
n = capacity;
19+
}
20+
21+
// 入队操作，将item放入队尾
22+
public boolean enqueue(String item) {
23+
// tail == n表示队列末尾没有空间了
24+
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;
34+
}
35+
36+
items[tail] = item;
37+
tail++;
38+
return true;
39+
}
40+
41+
// 出队
42+
public String dequeue() {
43+
// 如果head == tail 表示队列为空
44+
if (head == tail) return null;
45+
// 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
46+
String ret = items[head];
47+
++head;
48+
return ret;
49+
}
50+
51+
public void printAll() {
52+
for (int i = head; i < tail; ++i) {
53+
System.out.print(items[i] + " ");
54+
}
55+
System.out.println();
56+
}
57+
58+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/queue/QueueBasedOnLinkedList.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+
* 基于链表实现的队列
5+
* <p>
6+
* Author: Zheng
7+
*/
8+
public class QueueBasedOnLinkedList {
9+
10+
// 队列的队首和队尾
11+
private Node head = null;
12+
private Node tail = null;
13+
14+
// 入队
15+
public void enqueue(String value) {
16+
if (tail == null) {
17+
Node newNode = new Node(value, null);
18+
head = newNode;
19+
tail = newNode;
20+
} else {
21+
tail.next = new Node(value, null);
22+
tail = tail.next;
23+
}
24+
}
25+
26+
// 出队
27+
public String dequeue() {
28+
if (head == null) return null;
29+
30+
String value = head.data;
31+
head = head.next;
32+
if (head == null) {
33+
tail = null;
34+
}
35+
return value;
36+
}
37+
38+
public void printAll() {
39+
Node 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 {
48+
49+
private String data;
50+
private Node next;
51+
52+
public Node(String data, Node next) {
53+
this.data = data;
54+
this.next = next;
55+
}
56+
57+
public String getData() {
58+
return data;
59+
}
60+
61+
}
62+
63+
}

0 commit comments

Comments
 (0)