玩转数据结构——栈和队列（队列）

1 interface Queue01{
2
3 int getSize();
4 boolean isEmpty();
5 void enqueue(E e);
6 E dequeue();
7 E getFront();
8 }

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

1 public class ArrayQueue01 implements Queue01{
2
3 private Array01 array;
4
5 public ArrayQueue01(int capacity){
6 array = new Array01<>(capacity);
7 }
8
9 public ArrayQueue01(){
10 array = new Array01<>();
11 }
12
13 @Override
14 public int getSize(){
15 return array.getSize();
16 }
17
18 @Override
19 public boolean isEmpty(){
20 return 0 == array.getSize();
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 if(isEmpty()){
35 throw new IllegalArgumentException("Dequeue failed. The queue is empty.");
36 }
37
38 return array.removeFirst();
39 }
40
41 @Override
42 public E getFront(){
43 return array.getFirst();
44 }
45
46 @Override
47 public String toString(){
48 StringBuilder res = new StringBuilder();
49 res.append(String.format("ArrayQueue01: size = %d, capacity = %d\n",array.getSize(),array.getCapacity()));
50 res.append("Front [");
51 for(int i = 0; i ){
52 res.append(array.get(i));
53 if(array.getSize() - 1 != i){
54 res.append(", ");
55 }
56 }
57
58 res.append("] Tail");
59
60 return res.toString();
61
62 }
63
64 public static void main(String[] args) {
65
66 ArrayQueue01 queue = new ArrayQueue01<>();
67 for(int i = 0 ; i <8 ; i ++){
68 queue.enqueue(i);
69 System.out.println(queue);
70 if(i % 3 == 2){
71 queue.dequeue();
72 System.out.println(queue);
73 }
74 }
75 }
76 }