Skip to content

Commit 4df3c87

Browse files
hackfengJamhackfengJam
committed
add Queue
1 parent e38a6fe commit 4df3c87

File tree

5 files changed

+278
-2
lines changed

5 files changed

+278
-2
lines changed

‎Array/src/Array.java‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -75,6 +75,15 @@ public E get(int index) {
7575
return data[index];
7676
}
7777

78+
public E getLast() {
79+
return get(size - 1);
80+
}
81+
82+
public E getFirst() {
83+
return get(0);
84+
}
85+
86+
7887
// 修改 index 索引位置的元素
7988
public void set(int index, E e) {
8089
if (index < 0 || index >= size) {
@@ -127,7 +136,7 @@ public E remove(int index) {
127136

128137

129138
// 从数组中删除第一个元素，返回删除的元素
130-
public E removeFirst(int index) {
139+
public E removeFirst() {
131140

132141
return remove(0);
133142
}

‎Queue/src/Array.java‎

Lines changed: 182 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,182 @@
1+
public class Array<E> {
2+
3+
private E[] data;
4+
private int size;
5+
6+
/**
7+
* 构造函数，传入数组的容量 capacity 构造 Array
8+
*
9+
* @param capacity
10+
*/
11+
public Array(int capacity) {
12+
data = (E[]) new Object[capacity]; // new E[capacity] 不支持该语法，历史遗留问题
13+
size = 0;
14+
}
15+
16+
// 无参数的构造函数，默认数组的容量 capacity=10
17+
public Array() {
18+
this(10);
19+
}
20+
21+
// 获取数组中的元素个数
22+
public int getSize() {
23+
return size;
24+
}
25+
26+
// 获取数组的容量
27+
public int getCapacity() {
28+
return data.length;
29+
}
30+
31+
// 返回数组是否为空
32+
public boolean isEmpty() {
33+
return size == 0;
34+
}
35+
36+
// 向所有元素后添加一个新元素
37+
public void addLast(E e) {
38+
/*if (size == data.length) {
39+
throw new IllegalArgumentException("AddLast failed. Array is full.");
40+
}
41+
42+
data[size] = e;
43+
size++;*/
44+
add(size, e);
45+
}
46+
47+
// 在所有元素前添加一个新元素
48+
public void addFirst(E e) {
49+
add(0, e);
50+
}
51+
52+
// 在第 index 个位置插入一个新元素 e
53+
public void add(int index, E e) {
54+
55+
if (index < 0 || index > size) {
56+
throw new IllegalArgumentException("add failed. Require index >=0 and index < size.");
57+
}
58+
if (size == data.length) {
59+
resize(2 * data.length);
60+
}
61+
62+
63+
for (int i = size - 1; i >= index; i--) {
64+
data[i + 1] = data[i];
65+
}
66+
data[index] = e;
67+
size++;
68+
}
69+
70+
//获取 index 索引位置的元素
71+
public E get(int index) {
72+
if (index < 0 || index >= size) {
73+
throw new IllegalArgumentException("Get failed. Index is illegal.");
74+
}
75+
return data[index];
76+
}
77+
78+
public E getLast() {
79+
return get(size - 1);
80+
}
81+
82+
public E getFirst() {
83+
return get(0);
84+
}
85+
86+
87+
// 修改 index 索引位置的元素
88+
public void set(int index, E e) {
89+
if (index < 0 || index >= size) {
90+
throw new IllegalArgumentException("Set failed. Index is illegal.");
91+
}
92+
data[index] = e;
93+
}
94+
95+
// 查找数组中是否有元素 e
96+
public boolean contains(E e) {
97+
for (int i = 0; i < size; i++) {
98+
if (data[i].equals(e)) {
99+
return true;
100+
}
101+
}
102+
return false;
103+
}
104+
105+
// 查找数组中元素 e 所在的索引，如果不存在元素 e，则返回 -1
106+
public int find(E e) {
107+
for (int i = 0; i < size; i++) {
108+
if (data[i].equals(e)) {
109+
return i;
110+
}
111+
}
112+
return -1;
113+
}
114+
115+
// 从数组中删除 index 位置的元素，返回删除的元素
116+
public E remove(int index) {
117+
118+
if (index < 0 || index > size) {
119+
throw new IllegalArgumentException("remove failed. Index is illegal.");
120+
}
121+
E ret = data[index];
122+
for (int i = index + 1; i < size; i++) {
123+
data[i - 1] = data[i];
124+
}
125+
size--;
126+
127+
// 该行可选
128+
data[size] = null; // loitering objects != memory leak
129+
130+
if (size == data.length / 4 && data.length / 2 != 0) {
131+
resize(data.length / 2);
132+
}
133+
134+
return ret;
135+
}
136+
137+
138+
// 从数组中删除第一个元素，返回删除的元素
139+
public E removeFirst() {
140+
141+
return remove(0);
142+
}
143+
144+
// 从数组中删除最后元素，返回删除的元素
145+
public E removeLast() {
146+
147+
return remove(size - 1);
148+
}
149+
150+
// 从数组中删除元素e
151+
public void removeElement(E e) {
152+
int index = find(e);
153+
if (index != -1) {
154+
remove(index);
155+
}
156+
}
157+
158+
159+
@Override
160+
public String toString() {
161+
StringBuilder res = new StringBuilder();
162+
res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
163+
res.append("[");
164+
for (int i = 0; i < size; i++) {
165+
res.append(data[i]);
166+
if (i != size - 1) {
167+
res.append(", ");
168+
}
169+
}
170+
res.append("]");
171+
return res.toString();
172+
}
173+
174+
175+
private void resize(int newCapacity) {
176+
E[] newData = (E[]) new Object[newCapacity];
177+
for (int i = 0; i < size; i++) {
178+
newData[i] = data[i];
179+
}
180+
data = newData;
181+
}
182+
}

‎Queue/src/ArrayQueue.java‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
public class ArrayQueue<E> implements Queue<E> {
2+
3+
private Array<E> array;
4+
5+
public ArrayQueue(int capacity) {
6+
array = new Array<>(capacity);
7+
}
8+
9+
public ArrayQueue() {
10+
array = new Array<>();
11+
}
12+
13+
@Override
14+
public int getSize() {
15+
return array.getSize();
16+
}
17+
18+
@Override
19+
public boolean isEmpty() {
20+
return array.isEmpty();
21+
}
22+
23+
public int getCapacity() {
24+
return array.getCapacity();
25+
}
26+
27+
@Override
28+
public void enqueue(E e) {
29+
array.addLast(e);
30+
}
31+
32+
@Override
33+
public E dequeue() {
34+
return array.removeFirst();
35+
}
36+
37+
@Override
38+
public E getFront() {
39+
return array.getFirst();
40+
}
41+
42+
@Override
43+
public String toString() {
44+
StringBuilder res = new StringBuilder();
45+
res.append("Queue: ");
46+
res.append("front [");
47+
for (int i = 0; i < array.getSize(); i++) {
48+
res.append(array.get(i));
49+
if (i != array.getSize() - 1) {
50+
res.append(", ");
51+
}
52+
}
53+
res.append("] tail");
54+
return res.toString();
55+
}
56+
57+
public static void main(String[] args) {
58+
ArrayQueue<Integer> queue = new ArrayQueue<>();
59+
for (int i = 0; i < 10; i++) {
60+
queue.enqueue(i);
61+
System.out.println(queue);
62+
63+
if (i % 3 == 2) {
64+
queue.dequeue();
65+
System.out.println(queue);
66+
}
67+
}
68+
}
69+
}

‎Queue/src/Queue.java‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
public interface Queue<E> {
2+
// 获取队列大小
3+
int getSize();
4+
5+
// 队列是否为空
6+
boolean isEmpty();
7+
8+
// 元素e入队
9+
void enqueue(E e);
10+
11+
// 队首元素出队
12+
E dequeue();
13+
14+
// 查看队首元素
15+
E getFront();
16+
}

‎Stack/src/Array.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -135,7 +135,7 @@ public E remove(int index) {
135135

136136

137137
// 从数组中删除第一个元素，返回删除的元素
138-
public E removeFirst(int index) {
138+
public E removeFirst() {
139139

140140
return remove(0);
141141
}

0 commit comments

Comments
 (0)