Skip to content

Commit a84da3e

Browse files
dunwudunwu
committed
update codes
1 parent ae07862 commit a84da3e

File tree

17 files changed

+809
-304
lines changed

17 files changed

+809
-304
lines changed

‎README.md‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -74,6 +74,31 @@
7474
- [长度最小的子数组.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/长度最小的子数组.java)
7575
- [零矩阵.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/零矩阵.java)
7676

77+
### 链表
78+
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)
84+
- [两数相加.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/两数相加.java)
85+
- [二进制链表转整数.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/二进制链表转整数.java)
86+
- [删除排序链表中的重复元素.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/删除排序链表中的重复元素.java)
87+
- [单链表示例.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/单链表示例.java)
88+
- [双链表示例.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/双链表示例.java)
89+
- [反转链表.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/反转链表.java)
90+
- [合并 K 个排序链表.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/合并K个排序链表.java)
91+
- [合并 K 个排序链表解法 2.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/合并K个排序链表解法2.java)
92+
- [合并两个有序链表.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/合并两个有序链表.java)
93+
- [回文链表.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/回文链表.java)
94+
- [排序链表.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/排序链表.java)
95+
- [环形链表.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/环形链表.java)
96+
- [相交链表.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/相交链表.java)
97+
- [移除重复节点.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/移除重复节点.java)
98+
- [移除链表元素.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/移除链表元素.java)
99+
- [返回倒数第 k 个节点.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/返回倒数第k个节点.java)
100+
- [链表的中间结点.java](https://github.com/dunwu/algorithm-tutorial/blob/master/codes/algorithm/src/main/java/io/github/dunwu/algorithm/list/链表的中间结点.java)
101+
77102
### 字符串
78103

79104
- [二进制求和](https://github.com/dunwu/algorithm/blob/master/codes/data-structure/src/main/java/io/github/dunwu/ds/str/AddBinary.java)

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/stack/GenericStack.java‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package io.github.dunwu.algorithm.stack;
2+
3+
/**
4+
* 简化版泛型栈
5+
*
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @since 2020-06-09
8+
*/
9+
public class GenericStack<T> {
10+
11+
private int size = 0;
12+
private Node<T> top = null;
13+
14+
public void push(T value) {
15+
Node<T> node = new Node<>(value, null);
16+
if (top == null) {
17+
top = node;
18+
} else {
19+
node.next = top;
20+
top = node;
21+
}
22+
size++;
23+
}
24+
25+
public T pop() {
26+
if (top == null) {
27+
return null;
28+
}
29+
T val = top.data;
30+
top = top.next;
31+
size--;
32+
return val;
33+
}
34+
35+
public T peek() {
36+
if (top == null) {
37+
return null;
38+
}
39+
return top.data;
40+
}
41+
42+
public int getSize() {
43+
return size;
44+
}
45+
46+
public boolean isEmpty() {
47+
return size == 0;
48+
}
49+
50+
public void printAll() {
51+
Node<T> p = top;
52+
while (p != null) {
53+
System.out.print(p.data + " ");
54+
p = p.next;
55+
}
56+
System.out.println();
57+
}
58+
59+
private static class Node<T> {
60+
61+
private T data;
62+
private Node<T> next;
63+
64+
public Node(T data, Node<T> next) {
65+
this.data = data;
66+
this.next = next;
67+
}
68+
69+
public T getData() {
70+
return data;
71+
}
72+
73+
}
74+
75+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/stack/SampleBrowser.java‎

Lines changed: 192 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,192 @@
1+
package io.github.dunwu.algorithm.stack;
2+
3+
/**
4+
* 使用前后栈实现浏览器的前进后退。
5+
*
6+
* @author chinalwb
7+
*/
8+
public class SampleBrowser {
9+
10+
public static void main(String[] args) {
11+
SampleBrowser browser = new SampleBrowser();
12+
browser.open("http://www.baidu.com");
13+
browser.open("http://news.baidu.com/");
14+
browser.open("http://news.baidu.com/ent");
15+
browser.goBack();
16+
browser.goBack();
17+
browser.goForward();
18+
browser.open("http://www.qq.com");
19+
browser.goForward();
20+
browser.goBack();
21+
browser.goForward();
22+
browser.goBack();
23+
browser.goBack();
24+
browser.goBack();
25+
browser.goBack();
26+
browser.checkCurrentPage();
27+
}
28+
29+
private String currentPage;
30+
private LinkedListBasedStack backStack;
31+
private LinkedListBasedStack forwardStack;
32+
33+
public SampleBrowser() {
34+
this.backStack = new LinkedListBasedStack();
35+
this.forwardStack = new LinkedListBasedStack();
36+
}
37+
38+
public void open(String url) {
39+
if (this.currentPage != null) {
40+
this.backStack.push(this.currentPage);
41+
this.forwardStack.clear();
42+
}
43+
showUrl(url, "Open");
44+
}
45+
46+
public boolean canGoBack() {
47+
return this.backStack.size() > 0;
48+
}
49+
50+
public boolean canGoForward() {
51+
return this.forwardStack.size() > 0;
52+
}
53+
54+
public String goBack() {
55+
if (this.canGoBack()) {
56+
this.forwardStack.push(this.currentPage);
57+
String backUrl = this.backStack.pop();
58+
showUrl(backUrl, "Back");
59+
return backUrl;
60+
}
61+
62+
System.out.println("* Cannot go back, no pages behind.");
63+
return null;
64+
}
65+
66+
public String goForward() {
67+
if (this.canGoForward()) {
68+
this.backStack.push(this.currentPage);
69+
String forwardUrl = this.forwardStack.pop();
70+
showUrl(forwardUrl, "Foward");
71+
return forwardUrl;
72+
}
73+
74+
System.out.println("** Cannot go forward, no pages ahead.");
75+
return null;
76+
}
77+
78+
public void showUrl(String url, String prefix) {
79+
this.currentPage = url;
80+
System.out.println(prefix + " page == " + url);
81+
}
82+
83+
public void checkCurrentPage() {
84+
System.out.println("Current page is: " + this.currentPage);
85+
}
86+
87+
/**
88+
* A LinkedList based Stack implementation.
89+
*/
90+
public static class LinkedListBasedStack {
91+
92+
// public static void main(String[] args) {
93+
// LinkedListBasedStack stack = new LinkedListBasedStack();
94+
// stack.push("A");
95+
// stack.push("B");
96+
// stack.push("C");
97+
// stack.pop();
98+
// stack.push("D");
99+
// stack.push("E");
100+
// stack.pop();
101+
// stack.push("F");
102+
// stack.print();
103+
//
104+
//// String data = stack.getTopData();
105+
//// System.out.println("Top data == " + data);
106+
// }
107+
108+
private int size;
109+
private Node top;
110+
111+
static Node createNode(String data, Node next) {
112+
return new Node(data, next);
113+
}
114+
115+
public void clear() {
116+
this.top = null;
117+
this.size = 0;
118+
}
119+
120+
public void push(String data) {
121+
Node node = createNode(data, null);
122+
if (top == null) top = node;
123+
node.next = top;
124+
top = node;
125+
size++;
126+
}
127+
128+
public String pop() {
129+
if (top == null) {
130+
return null;
131+
}
132+
133+
String val = top.data;
134+
top = top.next;
135+
return val;
136+
}
137+
138+
public String getTopData() {
139+
if (top == null) return null;
140+
return top.data;
141+
}
142+
143+
public int size() {
144+
return this.size;
145+
}
146+
147+
public void print() {
148+
System.out.println("Print stack:");
149+
Node currentNode = this.top;
150+
while (currentNode != null) {
151+
String data = currentNode.getData();
152+
System.out.print(data + "\t");
153+
currentNode = currentNode.next;
154+
}
155+
System.out.println();
156+
}
157+
158+
public static class Node {
159+
160+
private String data;
161+
private Node next;
162+
163+
public Node(String data) {
164+
this(data, null);
165+
}
166+
167+
public Node(String data, Node next) {
168+
this.data = data;
169+
this.next = next;
170+
}
171+
172+
public void setData(String data) {
173+
this.data = data;
174+
}
175+
176+
public String getData() {
177+
return this.data;
178+
}
179+
180+
public void setNext(Node next) {
181+
this.next = next;
182+
}
183+
184+
public Node getNext() {
185+
return this.next;
186+
}
187+
188+
}
189+
190+
}
191+
192+
}

0 commit comments

Comments
 (0)