データ構造キューのjava実装は、線形とチェーンの2つの方法を含む.
17629 ワード
実現された考え方は:
一般的な方式を採用して、まずQueのインターフェースを定義し、次にこのインターフェースを実現することによって、線形とチェーンの二種類の隊列が実現される.
インターフェースコードは以下の通りです.
一般的な方式を採用して、まずQueのインターフェースを定義し、次にこのインターフェースを実現することによって、線形とチェーンの二種類の隊列が実現される.
インターフェースコードは以下の通りです.
1 package com.peter.java.dsa.interfaces;
2
3 public interface Queue<T> {
4
5 /* put item at rear of queue; */
6 void insert(T data);
7
8 /* take item from front of queue */
9 T remove();
10
11 /* peek at front of queue */
12 T peek();
13
14 boolean isEmpty();
15
16 boolean isFull();
17
18 int size();
19
20 void clear();
21 } 1 package com.peter.java.dsa.common;
2
3 import com.peter.java.dsa.interfaces.Queue;
4
5 public class LinearQueue<T> implements Queue<T> {
6 private int capacity;
7 private T[] t;
8 private int front;
9 private int rear;
10 private int size;
11
12 public LinearQueue() {
13 // TODO Auto-generated constructor stub
14 capacity = 16;
15 t = (T[]) new Object[capacity];
16 front = -1;
17 rear = -1;
18 size = 0;
19 }
20
21 public LinearQueue(int capacity) {
22 this.capacity = capacity;
23 t = (T[]) new Object[capacity];
24 front = -1;
25 rear = -1;
26 size = 0;
27 }
28
29 @Override
30 public void insert(T data) {
31 // TODO Auto-generated method stub
32 if (isEmpty()) {
33 front = (front + 1) % t.length;
34 t[front] = data;
35 rear = (rear + 1) % t.length;
36 } else {
37 if (isFull()) {
38 resize();
39 }
40 rear = (rear + 1) % t.length;
41 t[rear] = data;
42 }
43 size++;
44 }
45
46 @Override
47 public T remove() {
48 // TODO Auto-generated method stub
49 T tmp = null;
50 if (!isEmpty()) {
51 tmp = t[front];
52 t[front] = null;
53 front = (front + 1) % t.length;
54 size--;
55 }
56 return tmp;
57 }
58
59 @Override
60 public T peek() {
61 // TODO Auto-generated method stub
62 T tmp = null;
63 if (!isEmpty()) {
64 tmp = t[front];
65 }
66 return tmp;
67 }
68
69 @Override
70 public boolean isEmpty() {
71 // TODO Auto-generated method stub
72 return front + rear == -2 && front == rear % t.length;
73 }
74
75 @Override
76 public boolean isFull() {
77 // TODO Auto-generated method stub
78 return front == rear % t.length;
79 }
80
81 @Override
82 public int size() {
83 // TODO Auto-generated method stub
84 return size;
85 }
86
87 @Override
88 public String toString() {
89 // TODO Auto-generated method stub
90 StringBuffer buffer = new StringBuffer();
91 buffer.append("Linear Queue Content:[");
92 if (front < rear) {
93 for (int i = front; i < rear + 1; i++) {
94 buffer.append(t[i] + ",");
95 }
96 } else {
97 for (int i = front; i < t.length; i++) {
98 buffer.append(t[i] + ",");
99 }
100 for (int i = 0; i < rear + 1; i++) {
101 buffer.append(t[i] + ",");
102 }
103 }
104 buffer.append("]");
105 buffer.replace(buffer.lastIndexOf(","), buffer.lastIndexOf(",") + 1, "");
106 return buffer.toString();
107 }
108
109 private void resize() {
110 int oldSize = t.length;
111 T[] tmp = (T[]) new Object[oldSize * 2];
112 for (int i = 0; i < oldSize; i++) {
113 tmp[i] = t[front];
114 front = (front + 1) % oldSize;
115 }
116 front = 0;
117 rear = oldSize - 1;
118 }
119
120 @Override
121 public void clear() {
122 // TODO Auto-generated method stub
123 front = -1;
124 rear = -1;
125 }
126
127 }