双向顺序队列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
