Skip to content

Commit 500c926

Browse files
algorithmzuoalgorithmzuo
committed
add code
1 parent ccd7d90 commit 500c926

2 files changed

Lines changed: 411 additions & 0 deletions

File tree

‎src/class04/Code01_LinkedListToQueueAndStack.java‎

Lines changed: 222 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,222 @@
1+
package class04;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
import java.util.Stack;
6+
7+
public class Code01_LinkedListToQueueAndStack {
8+
9+
public static class Node<V> {
10+
public V value;
11+
public Node<V> next;
12+
13+
public Node(V v) {
14+
value = v;
15+
next = null;
16+
}
17+
}
18+
19+
public static class MyQueue<V> {
20+
private Node<V> head;
21+
private Node<V> tail;
22+
private int size;
23+
24+
public MyQueue() {
25+
head = null;
26+
tail = null;
27+
size = 0;
28+
}
29+
30+
public boolean isEmpty() {
31+
return size == 0;
32+
}
33+
34+
public int size() {
35+
return size;
36+
}
37+
38+
public void offer(V value) {
39+
Node<V> cur = new Node<V>(value);
40+
if (tail == null) {
41+
head = cur;
42+
tail = cur;
43+
} else {
44+
tail.next = cur;
45+
tail = cur;
46+
}
47+
size++;
48+
}
49+
50+
// C/C++的同学需要做节点析构的工作
51+
public V poll() {
52+
V ans = null;
53+
if (head != null) {
54+
ans = head.value;
55+
head = head.next;
56+
size--;
57+
}
58+
if (head == null) {
59+
tail = null;
60+
}
61+
return ans;
62+
}
63+
64+
// C/C++的同学需要做节点析构的工作
65+
public V peek() {
66+
V ans = null;
67+
if (head != null) {
68+
ans = head.value;
69+
}
70+
return ans;
71+
}
72+
73+
}
74+
75+
public static class MyStack<V> {
76+
private Node<V> head;
77+
private int size;
78+
79+
public MyStack() {
80+
head = null;
81+
size = 0;
82+
}
83+
84+
public boolean isEmpty() {
85+
return size == 0;
86+
}
87+
88+
public int size() {
89+
return size;
90+
}
91+
92+
public void push(V value) {
93+
Node<V> cur = new Node<>(value);
94+
if (head == null) {
95+
head = cur;
96+
} else {
97+
cur.next = head;
98+
head = cur;
99+
}
100+
size++;
101+
}
102+
103+
public V pop() {
104+
V ans = null;
105+
if (head != null) {
106+
ans = head.value;
107+
head = head.next;
108+
size--;
109+
}
110+
return ans;
111+
}
112+
113+
public V peek() {
114+
return head != null ? head.value : null;
115+
}
116+
117+
}
118+
119+
public static void testQueue() {
120+
MyQueue<Integer> myQueue = new MyQueue<>();
121+
Queue<Integer> test = new LinkedList<>();
122+
int testTime = 5000000;
123+
int maxValue = 200000000;
124+
System.out.println("测试开始！");
125+
for (int i = 0; i < testTime; i++) {
126+
if (myQueue.isEmpty() != test.isEmpty()) {
127+
System.out.println("Oops!");
128+
}
129+
if (myQueue.size() != test.size()) {
130+
System.out.println("Oops!");
131+
}
132+
double decide = Math.random();
133+
if (decide < 0.33) {
134+
int num = (int) (Math.random() * maxValue);
135+
myQueue.offer(num);
136+
test.offer(num);
137+
} else if (decide < 0.66) {
138+
if (!myQueue.isEmpty()) {
139+
int num1 = myQueue.poll();
140+
int num2 = test.poll();
141+
if (num1 != num2) {
142+
System.out.println("Oops!");
143+
}
144+
}
145+
} else {
146+
if (!myQueue.isEmpty()) {
147+
int num1 = myQueue.peek();
148+
int num2 = test.peek();
149+
if (num1 != num2) {
150+
System.out.println("Oops!");
151+
}
152+
}
153+
}
154+
}
155+
if (myQueue.size() != test.size()) {
156+
System.out.println("Oops!");
157+
}
158+
while (!myQueue.isEmpty()) {
159+
int num1 = myQueue.poll();
160+
int num2 = test.poll();
161+
if (num1 != num2) {
162+
System.out.println("Oops!");
163+
}
164+
}
165+
System.out.println("测试结束！");
166+
}
167+
168+
public static void testStack() {
169+
MyStack<Integer> myStack = new MyStack<>();
170+
Stack<Integer> test = new Stack<>();
171+
int testTime = 5000000;
172+
int maxValue = 200000000;
173+
System.out.println("测试开始！");
174+
for (int i = 0; i < testTime; i++) {
175+
if (myStack.isEmpty() != test.isEmpty()) {
176+
System.out.println("Oops!");
177+
}
178+
if (myStack.size() != test.size()) {
179+
System.out.println("Oops!");
180+
}
181+
double decide = Math.random();
182+
if (decide < 0.33) {
183+
int num = (int) (Math.random() * maxValue);
184+
myStack.push(num);
185+
test.push(num);
186+
} else if (decide < 0.66) {
187+
if (!myStack.isEmpty()) {
188+
int num1 = myStack.pop();
189+
int num2 = test.pop();
190+
if (num1 != num2) {
191+
System.out.println("Oops!");
192+
}
193+
}
194+
} else {
195+
if (!myStack.isEmpty()) {
196+
int num1 = myStack.peek();
197+
int num2 = test.peek();
198+
if (num1 != num2) {
199+
System.out.println("Oops!");
200+
}
201+
}
202+
}
203+
}
204+
if (myStack.size() != test.size()) {
205+
System.out.println("Oops!");
206+
}
207+
while (!myStack.isEmpty()) {
208+
int num1 = myStack.pop();
209+
int num2 = test.pop();
210+
if (num1 != num2) {
211+
System.out.println("Oops!");
212+
}
213+
}
214+
System.out.println("测试结束！");
215+
}
216+
217+
public static void main(String[] args) {
218+
testQueue();
219+
testStack();
220+
}
221+
222+
}

0 commit comments

Comments
 (0)