数据结构之队列

基本概念

　　队列(Queue)是限制在表的前端删除、表的后端插入的特殊线性表，按照先进先出(FIFO：First In First Out)原则操作数据，插入操作的端称为队尾，删除操作的端称为队头。

　　队列中没有元素时称为空队列。

　　队列分为：

　　　　单项队列：只能在一端插入数据，另外一端删除数据。

　　　　双向队列：每一段都可以插入删除数据。

　　　　优先级队列：数据在插入的时候会根据关键字插入到合适的位置以确保队列的有序。

　　Java API提供的队列为java.util.Queue<E> extends Collection<E>。

单向队列的模拟实现

 1 public class MyQueue {
 2     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 3 
 4     private Object[] elementData;//维护队列数据的数组
 5     private int start;//元素起始位置
 6     private int end;//元素结束位置
 7 
 8     public MyQueue() {
 9         elementData = new Object[10];
10         start = -1;
11         end = -1;
12     }
13 
14     public MyQueue(int minCapacity) {
15         elementData = new Object[minCapacity];
16         start = -1;
17         end = -1;
18     }
19 
20     //队尾插入元素
21     public void insert(Object item) {
22         grow();
23         if (isEmpty()) start = 0;
24         elementData[++end] = item;
25         System.out.println(String.format("insert-start:%s,end:%s", start, end));
26     }
27 
28     //队头删除元素
29     public Object remove() {
30         if (isEmpty()) return new EmptyStackException();
31         Object item = elementData[start];
32         elementData[start] = null;
33         if (start == end) start = end = -1;
34         else start++;
35         System.out.println(String.format("remove-start:%s,end:%s", start, end));
36         return item;
37     }
38 
39     //是否需要增加队列长度
40     private void grow() {
41         if (end != elementData.length - 1) return;
42         if (start > end - start) {
43             Object[] newElementData = new Object[elementData.length];
44             int i = 0;
45             for (Object object : elementData) {
46                 if (object != null) newElementData[i++] = object;
47             }
48             start = 0; end = i - 1;
49             elementData = newElementData;
50             return;
51         }
52         int newCapacity = elementData.length << 1 > MAX_ARRAY_SIZE ? MAX_ARRAY_SIZE : elementData.length << 1;
53         System.out.println(String.format("grow:%s---->%s", elementData.length, newCapacity));
54         elementData = Arrays.copyOf(elementData, newCapacity);
55     }
56 
57     //是否为空队列
58     public boolean isEmpty() {
59         return start == -1 && end == -1;
60     }
61 
62     public static void main(String[] args) {
63         MyQueue myQueue = new MyQueue(2);
64         myQueue.insert("1");
65         myQueue.insert("2");
66         myQueue.insert("3");
67         myQueue.insert("4");
68         myQueue.insert("5");
69         myQueue.insert("6");
70         System.out.println(myQueue.remove());
71         System.out.println(myQueue.remove());
72         System.out.println(myQueue.remove());
73         System.out.println(myQueue.remove());
74         myQueue.insert("7");
75         myQueue.insert("8");
76         myQueue.insert("9");
77         myQueue.insert("10");
78         myQueue.insert("11");
79         myQueue.insert("12");
80         while (!myQueue.isEmpty()) System.out.println(myQueue.remove());
81         myQueue.insert(13);
82 
83     }
84 }

双向队列

　　双向队列就是两端都可以插入和删除数据的队列，这些操作数据的方法可叫做insertStart()，insertEnd()，removeStart()，removeEnd()。

　　如果禁止调用insertStart()和removeStart()，则此双向队列的功能和栈一样。

　　如果禁止调用insertStart()和removeEnd()，则此双向队列的功能和单向队列的功能一样。

优先级队列

　　待讲

总结

　　1、栈、单向队列、优先级队列是用来简化某些程序操作的数据结构，而不是做为存储数据的。

　　2、这些数据结构一次只能操作一个数据项。

　　3、栈在栈顶插入数据、栈顶移除数据，只能访问最后一个插入的数据项（栈顶元素）。

　　4、单向队列只能队尾插入数据、队头移除数据；基于数组还可实现循环队列。

　　5、优先级队列是有序的插入数据，并且只能访问最大或者最小的元素。

　　6、这些数据结构都可以由数组实，也可以用别的实现（后续讲解）。