java队列实现（顺序队列、链式队列、循环队列）

青旅半醒 2022-06-09 13:59 220阅读 0赞

**双向顺序队列ArrayDeque和双向链式队列LinkedList，JDK已经包含，在此略。ArrayDeque包括顺序栈和顺序队列，LinkedList包含链式栈和链式队列。ArrayDeque和LinkedList都是线程不安全的。PriorityQueue优先队列也在JDK。**

**算法与数据结构技术学习，更多知识请访问[https://www.itkc8.com][https_www.itkc8.com]**

**1.顺序队列的实现**

**\[java\]** [view plain][] [copy][view plain]

1. **package** lang;  
2.   
3. **import** java.io.Serializable;  
4. **import** java.util.Arrays;  
5.   
6. /\*\* 
7.  \* @ClassName: ArrayQueue 
8.  \* @Description: 顺序队列 
9.  \* @date 2014年1月20日 下午3:46:19 
10.  \* @param <T> 
11.  \*/  
12. **public** **class** ArrayQueue<T> **implements** Serializable\{  
13.   /\*\* 
14.    \* @Fields serialVersionUID : TODO 
15.    \*/  
16.   **private** **static** **final** **long** serialVersionUID = 7333344126529379197L;  
17.   
18.   **private** **int** DEFAULT\_SIZE = 10;  
19.   
20.   **private** **int** capacity;//保存数组的长度  
21.   
22.   **private** Object\[\] elementData;//定义一个数组用于保存顺序队列的元素  
23.   
24.   **private** **int** front = 0;//队头  
25.   
26.   **private** **int** rear = 0;//队尾  
27.   
28.   //以默认数组长度创建空顺序队列  
29.   **public** ArrayQueue() \{  
30.     capacity = DEFAULT\_SIZE;  
31.     elementData = **new** Object\[capacity\];  
32.   \}  
33.   
34.   //以一个初始化元素来创建顺序队列  
35.   **public** ArrayQueue(T element) \{  
36.     **this**();  
37.     elementData\[0\] = element;  
38.     rear++;  
39.   \}  
40.     
41.   **public** ArrayQueue(**int** initSize) \{  
42.     elementData = **new** Object\[initSize\];  
43.   \}  
44.   
45.   /\*\* 
46.    \* 以指定长度的数组来创建顺序队列 
47.    \* @param element 指定顺序队列中第一个元素 
48.    \* @param initSize 指定顺序队列底层数组的长度 
49.    \*/  
50.   **public** ArrayQueue(T element, **int** initSize) \{  
51.     **this**.capacity = initSize;  
52.     elementData = **new** Object\[capacity\];  
53.     elementData\[0\] = element;  
54.     rear++;  
55.   \}  
56.   
57.   /\*\* 
58.    \* @Title: size      
59.    \* @Description: 获取顺序队列的大小     
60.    \* @return 
61.    \*/  
62.   **public** **int** size() \{  
63.     **return** rear - front;  
64.   \}  
65.   
66.   /\*\* 
67.    \* @Title: offer      
68.    \* @Description: 入队     
69.    \* @param element 
70.    \*/  
71.   **public** **void** offer(T element) \{  
72.     ensureCapacity(rear + 1);  
73.     elementData\[rear++\] = element;  
74.   \}  
75.     
76.   **private** **void** ensureCapacity(**int** minCapacity) \{  
77.     //如果数组的原有长度小于目前所需的长度  
78.     **int** oldCapacity = elementData.length;  
79.     **if** (minCapacity > oldCapacity) \{  
80.       **int** newCapacity = (oldCapacity \* 3) / 2 + 1;  
81.       **if** (newCapacity < minCapacity)  
82.         newCapacity = minCapacity;  
83.       // minCapacity is usually close to size, so this is a win:  
84.       elementData = Arrays.copyOf(elementData, newCapacity);  
85.     \}  
86.   
87.   \}  
88.   
89.   /\*\* 
90.    \* @Title: poll      
91.    \* @Description: 出队     
92.    \* @return 
93.    \*/  
94.   **public** T poll() \{  
95.     **if** (isEmpty()) \{  
96.       **throw** **new** IndexOutOfBoundsException("空队列异常");  
97.     \}  
98.     //保留队列的front端的元素的值  
99.     T oldValue = (T) elementData\[front\];  
100.     //释放队列的front端的元素  
101.     elementData\[front++\] = **null**;  
102.     **return** oldValue;  
103.   \}  
104.   
105.   /\*\* 
106.    \* @Title: peek      
107.    \* @Description: 返回队列顶元素，但不删除队列顶元素     
108.    \* @return 
109.    \*/  
110.   **public** T peek() \{  
111.     **if** (isEmpty()) \{  
112.       **throw** **new** IndexOutOfBoundsException("空队列异常");  
113.     \}  
114.     **return** (T) elementData\[front\];  
115.   \}  
116.   
117.   /\*\* 
118.    \* @Title: isEmpty      
119.    \* @Description: 判断顺序队列是否为空队列     
120.    \* @return 
121.    \*/  
122.   **public** **boolean** isEmpty() \{  
123.     **return** rear == front;  
124.   \}  
125.   
126.   /\*\* 
127.    \* @Title: clear      
128.    \* @Description: 清空顺序队列 
129.    \*/  
130.   **public** **void** clear() \{  
131.     //将底层数组所有元素赋为null  
132.     Arrays.fill(elementData, **null**);  
133.     front = 0;  
134.     rear = 0;  
135.   \}  
136.   
137.   **public** String toString() \{  
138.     **if** (isEmpty()) \{  
139.       **return** "\[\]";  
140.     \} **else** \{  
141.       StringBuilder sb = **new** StringBuilder("\[");  
142.       **for** (**int** i = front; i < rear; i++) \{  
143.         sb.append(elementData\[i\].toString() + ", ");  
144.       \}  
145.       **int** len = sb.length();  
146.       **return** sb.delete(len - 2, len).append("\]").toString();  
147.     \}  
148.   \}  
149. \}

2. **链式队列的实现**

**\[java\]** [view plain][] [copy][view plain]

1. **package** lang;  
2.   
3. **import** java.io.Serializable;  
4.   
5. /\*\* 
6.  \* @ClassName: LinkQueue 
7.  \* @Description:  链式队列 
8.  \* @date 2014年1月21日 下午3:24:38 
9.  \* @param <T> 
10.  \*/  
11. **public** **class** LinkQueue<T> **implements** Serializable\{  
12.   /\*\* 
13.    \* @Fields serialVersionUID : TODO 
14.    \*/  
15.   **private** **static** **final** **long** serialVersionUID = -6726728595616312615L;  
16.   
17.   //定义一个内部类Node，Node实例代表链队列的节点。  
18.   **private** **class** Node \{  
19.       
20.     **private** T data;//保存节点的数据  
21.      
22.     **private** Node next;//指向下个节点的引用  
23.   
24.     //无参数的构造器  
25.     **public** Node() \{  
26.     \}  
27.   
28.     //初始化全部属性的构造器  
29.     **public** Node(T data, Node next) \{  
30.       **this**.data = data;  
31.       **this**.next = next;  
32.     \}  
33.   \}  
34.     
35.   **private** Node front;//保存该链队列的头节点  
36.     
37.   **private** Node rear;//保存该链队列的尾节点  
38.   
39.   **private** **int** size;//保存该链队列中已包含的节点数  
40.   
41.   /\*\* 
42.    \* Title: LinkQueue       
43.    \* Description: 创建空链队列   
44.    \*/  
45.   **public** LinkQueue() \{  
46.     //空链队列，front和rear都是null  
47.     front = **null**;  
48.     rear = **null**;  
49.   \}  
50.   
51.   /\*\* 
52.    \* Title: LinkQueue      
53.    \* Description: 以指定数据元素来创建链队列，该链队列只有一个元素  
54.    \*/  
55.   **public** LinkQueue(T element) \{  
56.     front = **new** Node(element, **null**);  
57.     //只有一个节点，front、rear都指向该节点  
58.     rear = front;  
59.     size++;  
60.   \}  
61.   
62.   /\*\* 
63.    \* @Title: size      
64.    \* @Description: 获取顺序队列的大小     
65.    \* @return 
66.    \*/  
67.   **public** **int** size() \{  
68.     **return** size;  
69.   \}  
70.   
71.   /\*\* 
72.    \* @Title: offer      
73.    \* @Description: 入队     
74.    \* @param element 
75.    \*/  
76.   **public** **void** offer(T element) \{  
77.     //如果该链队列还是空链队列  
78.     **if** (front == **null**) \{  
79.       front = **new** Node(element, **null**);       
80.       rear = front;//只有一个节点，front、rear都指向该节点  
81.     \} **else** \{       
82.       Node newNode = **new** Node(element, **null**);//创建新节点       
83.       rear.next = newNode;//让尾节点的next指向新增的节点       
84.       rear = newNode;//以新节点作为新的尾节点  
85.     \}  
86.     size++;  
87.   \}  
88.   
89.   /\*\* 
90.    \* @Title: poll      
91.    \* @Description: 出队     
92.    \* @return 
93.    \*/  
94.   **public** T poll() \{  
95.     Node oldFront = front;  
96.     front = front.next;  
97.     oldFront.next = **null**;  
98.     size--;  
99.     **return** oldFront.data;  
100.   \}  
101.   
102.   /\*\* 
103.    \* @Title: peek      
104.    \* @Description: 返回队列顶元素，但不删除队列顶元素     
105.    \* @return 
106.    \*/  
107.   **public** T peek() \{  
108.     **return** rear.data;  
109.   \}  
110.   
111.   /\*\* 
112.    \* @Title: isEmpty      
113.    \* @Description: 判断顺序队列是否为空队列     
114.    \* @return 
115.    \*/  
116.   **public** **boolean** isEmpty() \{  
117.     **return** size == 0;  
118.   \}  
119.   
120.   /\*\* 
121.    \* @Title: clear      
122.    \* @Description: 清空顺序队列 
123.    \*/  
124.   **public** **void** clear() \{  
125.     //将front、rear两个节点赋为null  
126.     front = **null**;  
127.     rear = **null**;  
128.     size = 0;  
129.   \}  
130.   
131.   **public** String toString() \{  
132.     //链队列为空链队列时  
133.     **if** (isEmpty()) \{  
134.       **return** "\[\]";  
135.     \} **else** \{  
136.       StringBuilder sb = **new** StringBuilder("\[");  
137.       **for** (Node current = front; current != **null**; current = current.next) \{  
138.         sb.append(current.data.toString() + ", ");  
139.       \}  
140.       **int** len = sb.length();  
141.       **return** sb.delete(len - 2, len).append("\]").toString();  
142.     \}  
143.   \}  
144.   
145.   **public** **static** **void** main(String\[\] args) \{  
146.     LinkQueue<String> queue = **new** LinkQueue<String>("aaaa");  
147.     //添加两个元素  
148.     queue.offer("bbbb");  
149.     queue.offer("cccc");  
150.     System.out.println(queue);  
151.     //删除一个元素后  
152.     queue.poll();  
153.     System.out.println("删除一个元素后的队列：" + queue);  
154.     //再次添加一个元素  
155.     queue.offer("dddd");  
156.     System.out.println("再次添加元素后的队列：" + queue);  
157.     //删除一个元素后，队列可以再多加一个元素  
158.     queue.poll();  
159.     //再次加入一个元素  
160.     queue.offer("eeee");  
161.     System.out.println(queue);  
162.   \}  
163. \}

**3. 循环队列的实现**

**\[java\]** [view plain][] [copy][view plain]

1. **package** lang;  
2.   
3. **import** java.io.Serializable;  
4. **import** java.util.Arrays;  
5.   
6. /\*\* 
7.  \* @ClassName: LoopQueue 
8.  \* @Description: 循环队列 
9.  \* @date 2014年1月20日 下午3:47:14 
10.  \*/  
11. **public** **class** LoopQueue<T> **implements** Serializable\{  
12.   /\*\* 
13.    \* @Fields serialVersionUID : TODO 
14.    \*/  
15.   **private** **static** **final** **long** serialVersionUID = -3670496550272478781L;  
16.   
17.   **private** **int** DEFAULT\_SIZE = 10;  
18.   
19.   **private** **int** capacity;//保存数组的长度  
20.   
21.   **private** Object\[\] elementData;//定义一个数组用于保存循环队列的元素  
22.   
23.   **private** **int** front = 0;//队头  
24.   
25.   **private** **int** rear = 0;//队尾  
26.   
27.   //以默认数组长度创建空循环队列  
28.   **public** LoopQueue() \{  
29.     capacity = DEFAULT\_SIZE;  
30.     elementData = **new** Object\[capacity\];  
31.   \}  
32.   
33.   //以一个初始化元素来创建循环队列  
34.   **public** LoopQueue(T element) \{  
35.     **this**();  
36.     elementData\[0\] = element;  
37.     rear++;  
38.   \}  
39.   
40.   /\*\* 
41.    \* 以指定长度的数组来创建循环队列 
42.    \* @param element 指定循环队列中第一个元素 
43.    \* @param initSize 指定循环队列底层数组的长度 
44.    \*/  
45.   **public** LoopQueue(T element, **int** initSize) \{  
46.     **this**.capacity = initSize;  
47.     elementData = **new** Object\[capacity\];  
48.     elementData\[0\] = element;  
49.     rear++;  
50.   \}  
51.   
52.   //获取循环队列的大小  
53.   **public** **int** size() \{  
54.     **if** (isEmpty()) \{  
55.       **return** 0;  
56.     \}  
57.     **return** rear > front ? rear - front : capacity - (front - rear);  
58.   \}  
59.   
60.   //插入队列  
61.   **public** **void** add(T element) \{  
62.     **if** (rear == front && elementData\[front\] != **null**) \{  
63.       **throw** **new** IndexOutOfBoundsException("队列已满的异常");  
64.     \}  
65.     elementData\[rear++\] = element;  
66.     //如果rear已经到头，那就转头  
67.     rear = rear == capacity ? 0 : rear;  
68.   \}  
69.   
70.   //移除队列  
71.   **public** T remove() \{  
72.     **if** (isEmpty()) \{  
73.       **throw** **new** IndexOutOfBoundsException("空队列异常");  
74.     \}  
75.     //保留队列的rear端的元素的值  
76.     T oldValue = (T) elementData\[front\];  
77.     //释放队列的rear端的元素  
78.     elementData\[front++\] = **null**;  
79.     //如果front已经到头，那就转头  
80.     front = front == capacity ? 0 : front;  
81.     **return** oldValue;  
82.   \}  
83.   
84.   //返回队列顶元素，但不删除队列顶元素  
85.   **public** T element() \{  
86.     **if** (isEmpty()) \{  
87.       **throw** **new** IndexOutOfBoundsException("空队列异常");  
88.     \}  
89.     **return** (T) elementData\[front\];  
90.   \}  
91.   
92.   //判断循环队列是否为空队列  
93.   **public** **boolean** isEmpty() \{  
94.     //rear==front且rear处的元素为null  
95.     **return** rear == front && elementData\[rear\] == **null**;  
96.   \}  
97.   
98.   //清空循环队列  
99.   **public** **void** clear() \{  
100.     //将底层数组所有元素赋为null  
101.     Arrays.fill(elementData, **null**);  
102.     front = 0;  
103.     rear = 0;  
104.   \}  
105.   
106.   **public** String toString() \{  
107.     **if** (isEmpty()) \{  
108.       **return** "\[\]";  
109.     \} **else** \{  
110.       //如果front < rear，有效元素就是front到rear之间的元素  
111.       **if** (front < rear) \{  
112.         StringBuilder sb = **new** StringBuilder("\[");  
113.         **for** (**int** i = front; i < rear; i++) \{  
114.           sb.append(elementData\[i\].toString() + ", ");  
115.         \}  
116.         **int** len = sb.length();  
117.         **return** sb.delete(len - 2, len).append("\]").toString();  
118.       \}  
119.       //如果front >= rear，有效元素为front->capacity之间、0->front之间的  
120.       **else** \{  
121.         StringBuilder sb = **new** StringBuilder("\[");  
122.         **for** (**int** i = front; i < capacity; i++) \{  
123.           sb.append(elementData\[i\].toString() + ", ");  
124.         \}  
125.         **for** (**int** i = 0; i < rear; i++) \{  
126.           sb.append(elementData\[i\].toString() + ", ");  
127.         \}  
128.         **int** len = sb.length();  
129.         **return** sb.delete(len - 2, len).append("\]").toString();  
130.       \}  
131.     \}  
132.   \}  
133.   
134.   **public** **static** **void** main(String\[\] args) \{  
135.     LoopQueue<String> queue = **new** LoopQueue<String>("aaaa", 3);  
136.     //添加两个元素  
137.     queue.add("bbbb");  
138.     queue.add("cccc");  
139.     //此时队列已满  
140.     System.out.println(queue);  
141.     //删除一个元素后，队列可以再多加一个元素  
142.     queue.remove();  
143.     System.out.println("删除一个元素后的队列：" + queue);  
144.     //再次添加一个元素，此时队列又满  
145.     queue.add("dddd");  
146.     System.out.println(queue);  
147.     System.out.println("队列满时的长度：" + queue.size());  
148.     //删除一个元素后，队列可以再多加一个元素  
149.     queue.remove();  
150.     //再次加入一个元素，此时队列又满  
151.     queue.add("eeee");  
152.     System.out.println(queue);  
153.   \}  
154. \}

**算法与数据结构技术学习，更多知识请访问[https://www.itkc8.com][https_www.itkc8.com]**

[https_www.itkc8.com]: https://www.itkc8.com
[view plain]: http://blog.csdn.net/jiutianhe/article/details/18606295#