雙向順序隊列ArrayDeque和雙向鏈式隊列LinkedList，JDK已經包含，在此略。ArrayDeque包括順序棧和順序隊列，LinkedList包含鏈式棧和鏈式隊列。ArrayDeque和LinkedList都是線程不安全的。PriorityQueue優先隊列也在JDK。
1.順序隊列的實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
package lang;import java.io.Serializable;import java.util.Arrays;/** * @ClassName: ArrayQueue * @Description: 順序隊列 * @date 2014年1月20日 下午3:46:19 * @param <T> */public class ArrayQueue<T> implements Serializable{ /** * @Fields serialVersionUID : TODO */ private static final long serialVersionUID = 7333344126529379197L; private int DEFAULT_SIZE = 10; private int capacity;//保存數組的長度 private Object[] elementData;//定義一個數組用于保存順序隊列的元素 private int front = 0;//隊頭 private int rear = 0;//隊尾 //以默認數組長度創建空順序隊列 public ArrayQueue() { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } //以一個初始化元素來創建順序隊列 public ArrayQueue(T element) { this(); elementData[0] = element; rear++; } public ArrayQueue(int initSize) { elementData = new Object[initSize]; } /** * 以指定長度的數組來創建順序隊列 * @param element 指定順序隊列中第一個元素 * @param initSize 指定順序隊列底層數組的長度 */ public ArrayQueue(T element, int initSize) { this.capacity = initSize; elementData = new Object[capacity]; elementData[0] = element; rear++; } /** * @Title: size * @Description: 獲取順序隊列的大小 * @return */ public int size() { return rear - front; } /** * @Title: offer * @Description: 入隊 * @param element */ public void offer(T element) { ensureCapacity(rear + 1); elementData[rear++] = element; } private void ensureCapacity(int minCapacity) { //如果數組的原有長度小于目前所需的長度 int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { int newCapacity = (oldCapacity * 3) / 2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } } /** * @Title: poll * @Description: 出隊 * @return */ public T poll() { if (isEmpty()) { throw new IndexOutOfBoundsException("空隊列異常"); } //保留隊列的front端的元素的值 T oldValue = (T) elementData[front]; //釋放隊列的front端的元素 elementData[front++] = null; return oldValue; } /** * @Title: peek * @Description: 返回隊列頂元素，但不刪除隊列頂元素 * @return */ public T peek() { if (isEmpty()) { throw new IndexOutOfBoundsException("空隊列異常"); } return (T) elementData[front]; } /** * @Title: isEmpty * @Description: 判斷順序隊列是否為空隊列 * @return */ public boolean isEmpty() { return rear == front; } /** * @Title: clear * @Description: 清空順序隊列 */ public void clear() { //將底層數組所有元素賦為null Arrays.fill(elementData, null); front = 0; rear = 0; } public String toString() { if (isEmpty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (int i = front; i < rear; i++) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } }} |
2. 鏈式隊列的實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
package lang;import java.io.Serializable;/** * @ClassName: LinkQueue * @Description: 鏈式隊列 * @date 2014年1月21日 下午3:24:38 * @param <T> */public class LinkQueue<T> implements Serializable{ /** * @Fields serialVersionUID : TODO */ private static final long serialVersionUID = -6726728595616312615L; //定義一個內部類Node，Node實例代表鏈隊列的節點。 private class Node { private T data;//保存節點的數據 private Node next;//指向下個節點的引用 //無參數的構造器 public Node() { } //初始化全部屬性的構造器 public Node(T data, Node next) { this.data = data; this.next = next; } } private Node front;//保存該鏈隊列的頭節點 private Node rear;//保存該鏈隊列的尾節點 private int size;//保存該鏈隊列中已包含的節點數 /** * <p>Title: LinkQueue </p> * <p>Description: 創建空鏈隊列 </p> */ public LinkQueue() { //空鏈隊列，front和rear都是null front = null; rear = null; } /** * <p>Title: LinkQueue </p> * <p>Description: 以指定數據元素來創建鏈隊列，該鏈隊列只有一個元素</p> */ public LinkQueue(T element) { front = new Node(element, null); //只有一個節點，front、rear都指向該節點 rear = front; size++; } /** * @Title: size * @Description: 獲取順序隊列的大小 * @return */ public int size() { return size; } /** * @Title: offer * @Description: 入隊 * @param element */ public void offer(T element) { //如果該鏈隊列還是空鏈隊列 if (front == null) { front = new Node(element, null); rear = front;//只有一個節點，front、rear都指向該節點 } else { Node newNode = new Node(element, null);//創建新節點 rear.next = newNode;//讓尾節點的next指向新增的節點 rear = newNode;//以新節點作為新的尾節點 } size++; } /** * @Title: poll * @Description: 出隊 * @return */ public T poll() { Node oldFront = front; front = front.next; oldFront.next = null; size--; return oldFront.data; } /** * @Title: peek * @Description: 返回隊列頂元素，但不刪除隊列頂元素 * @return */ public T peek() { return rear.data; } /** * @Title: isEmpty * @Description: 判斷順序隊列是否為空隊列 * @return */ public boolean isEmpty() { return size == 0; } /** * @Title: clear * @Description: 清空順序隊列 */ public void clear() { //將front、rear兩個節點賦為null front = null; rear = null; size = 0; } public String toString() { //鏈隊列為空鏈隊列時 if (isEmpty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = front; current != null; current = current.next) { sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } } public static void main(String[] args) { LinkQueue<String> queue = new LinkQueue<String>("aaaa"); //添加兩個元素 queue.offer("bbbb"); queue.offer("cccc"); System.out.println(queue); //刪除一個元素后 queue.poll(); System.out.println("刪除一個元素后的隊列：" + queue); //再次添加一個元素 queue.offer("dddd"); System.out.println("再次添加元素后的隊列：" + queue); //刪除一個元素后，隊列可以再多加一個元素 queue.poll(); //再次加入一個元素 queue.offer("eeee"); System.out.println(queue); }} |
3. 循環隊列的實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
package lang;import java.io.Serializable;import java.util.Arrays;/** * @ClassName: LoopQueue * @Description: 循環隊列 * @date 2014年1月20日 下午3:47:14 */public class LoopQueue<T> implements Serializable{ /** * @Fields serialVersionUID : TODO */ private static final long serialVersionUID = -3670496550272478781L; private int DEFAULT_SIZE = 10; private int capacity;//保存數組的長度 private Object[] elementData;//定義一個數組用于保存循環隊列的元素 private int front = 0;//隊頭 private int rear = 0;//隊尾 //以默認數組長度創建空循環隊列 public LoopQueue() { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } //以一個初始化元素來創建循環隊列 public LoopQueue(T element) { this(); elementData[0] = element; rear++; } /** * 以指定長度的數組來創建循環隊列 * @param element 指定循環隊列中第一個元素 * @param initSize 指定循環隊列底層數組的長度 */ public LoopQueue(T element, int initSize) { this.capacity = initSize; elementData = new Object[capacity]; elementData[0] = element; rear++; } //獲取循環隊列的大小 public int size() { if (isEmpty()) { return 0; } return rear > front ? rear - front : capacity - (front - rear); } //插入隊列 public void add(T element) { if (rear == front && elementData[front] != null) { throw new IndexOutOfBoundsException("隊列已滿的異常"); } elementData[rear++] = element; //如果rear已經到頭，那就轉頭 rear = rear == capacity ? 0 : rear; } //移除隊列 public T remove() { if (isEmpty()) { throw new IndexOutOfBoundsException("空隊列異常"); } //保留隊列的rear端的元素的值 T oldValue = (T) elementData[front]; //釋放隊列的rear端的元素 elementData[front++] = null; //如果front已經到頭，那就轉頭 front = front == capacity ? 0 : front; return oldValue; } //返回隊列頂元素，但不刪除隊列頂元素 public T element() { if (isEmpty()) { throw new IndexOutOfBoundsException("空隊列異常"); } return (T) elementData[front]; } //判斷循環隊列是否為空隊列 public boolean isEmpty() { //rear==front且rear處的元素為null return rear == front && elementData[rear] == null; } //清空循環隊列 public void clear() { //將底層數組所有元素賦為null Arrays.fill(elementData, null); front = 0; rear = 0; } public String toString() { if (isEmpty()) { return "[]"; } else { //如果front < rear，有效元素就是front到rear之間的元素 if (front < rear) { StringBuilder sb = new StringBuilder("["); for (int i = front; i < rear; i++) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } //如果front >= rear，有效元素為front->capacity之間、0->front之間的 else { StringBuilder sb = new StringBuilder("["); for (int i = front; i < capacity; i++) { sb.append(elementData[i].toString() + ", "); } for (int i = 0; i < rear; i++) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } } } public static void main(String[] args) { LoopQueue<String> queue = new LoopQueue<String>("aaaa", 3); //添加兩個元素 queue.add("bbbb"); queue.add("cccc"); //此時隊列已滿 System.out.println(queue); //刪除一個元素后，隊列可以再多加一個元素 queue.remove(); System.out.println("刪除一個元素后的隊列：" + queue); //再次添加一個元素，此時隊列又滿 queue.add("dddd"); System.out.println(queue); System.out.println("隊列滿時的長度：" + queue.size()); //刪除一個元素后，隊列可以再多加一個元素 queue.remove(); //再次加入一個元素，此時隊列又滿 queue.add("eeee"); System.out.println(queue); }} |
以上這篇java隊列實現方法(順序隊列,鏈式隊列,循環隊列)就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
原文鏈接：http://blog.csdn.net/jiutianhe/article/details/18606295
