1. 简介
成都的火车南站早上真的恐怖,地铁站人山人海,从地铁里面一直排队到门口,虽然人很多但是不得不说我国人民素质还是蛮高的,都是来了之后排在队伍的最后面,没有一个人去插队。这样不仅避免了人员拥挤的混乱,也让需要乘坐地铁的人可以尽快乘上地铁。
其实我们的队列就像排队等地铁一样,遵从先来后到,先来的人先上车后来的人后上车,队列则是先插入的数据,先取出去,后来的数据后取出去,先进先出的原则。而且总是从一端进入,另一端出去。
忽略那些排了队然后不想排的和插队的人。
顺序队列结构如下。
队列也是一种线性表,满足前驱后继,同样可以有顺序队列和链式队列,而顺序队列一般可以使用数组进行实现,那么队头就是下标为0,而队尾则是数组的最后一位(length-1),而链式列表可以使用链表,队头就是第一个结点,而队尾则是最后一个结点。
了解了队列的基本知识,下面看一下顺序队列基本实现思路,首先我们要定义两个标识一个是队尾,一个是队首,这两个标识就像两个小旗子,队列最前面和最后面的人都拿着一个旗子,好让别人知道现在的队首和队尾究竟是那一个人,如果新增数据首先知道数组的长度是否足够,如果不够则需要代码实现扩容,如果够则在队尾加入数据,同时将指向队尾的标识(小旗子)现在指向新增数据上,而获取数据时首先拿出数据,同时将旗子交给他的下一个数据。
讲到这儿有同学开始质疑,难道你第一个人上车了,下一个不向前走一走吗?确实如此,但是如果每次取数据都需要移动,因为采用的是顺序存储结构(数组)那么取数据的时间复杂度将会是O(n),因为你需要改变数组的结构,每一个人都要向前移动,实际上我们不需要这样做只需要把队首的取出来,然后把队首的旗子交给下一个,我们每次去拿数据只是去找队首的旗子在谁的手上就拿谁。但是这样又会存在一个问题,如果你前面走了两个人(取出了两个数据),然后后面不断的来了新的人(数据),然后数组因为初始化了容量发现已经满了,此时实际上我们并没有满,因为前面还有两个位置,而这就是我们常说的假溢出,就像你去坐公交车上车后看到后面全坐满了,而前面还有两个位置,你告诉师傅我要下车,因为没有位置了。
通过上面出现的问题,诞生出了一种循环队列,听名字就知道收尾相连接,实际上就是你上公交车后发现后面没有位置了,前面还有,那么肯定坐在前面撒。同样如果我们在插入数据时发现队尾已经超出数组长度了,但是队首确不是为0,也就是已经有人离开了,那么新增的就到前面去,同时队尾的旗子他也要拿上,直到队首的旗子和队尾的旗子相遇时也就是相等时,此时才满了,才需要进行扩容。而取数据时如果队尾小于队首那么每次取出数据后,旗子是交给前一个人,而不是后一个人。
2. 实现循环队列
package netty;
/** * 队列顺序存储-循环存储 * @author damao * @date 2019-11-28 10:39 */public class CircularQueue<T> {
private DataArray<T>[] dataArrays = new DataArray[DEFAULT_CAPACITY];
private static int DEFAULT_CAPACITY = 3;
/** * 前端指针,默认指向数组的第一位 */ private int front = 0;
/** * 后端指针,默认指向数组的第一位 */ private int rear = 0;
public boolean inQueue(T t){ DataArray<T> dataArray = new DataArray(); dataArray.setData (t); dataArrays[rear] = dataArray; rear++; capacityExpansion(); return true; }
public T outQueue(){ if(rear < front && front == DEFAULT_CAPACITY){ front = 0; } if(dataArrays[front] == null){ throw new RuntimeException ("Queue is already empty"); } T data = dataArrays[front].getData (); dataArrays[front].setData (null); front++; return data; }
public void capacityExpansion(){ if(rear == DEFAULT_CAPACITY && front != 0){ rear = 0; }else if(front == rear || (front<rear && rear == DEFAULT_CAPACITY)){ //容量扩大2倍 int newCapacity = DEFAULT_CAPACITY*2; DataArray<T>[] newDataArrays = new DataArray[DEFAULT_CAPACITY*2]; if(front < rear){ System.arraycopy (dataArrays,0,newDataArrays,0,DEFAULT_CAPACITY); }else { System.arraycopy (dataArrays,front,newDataArrays,0,DEFAULT_CAPACITY-front); System.arraycopy (dataArrays,0,newDataArrays,DEFAULT_CAPACITY-front,rear); } front = 0; rear = DEFAULT_CAPACITY; DEFAULT_CAPACITY = newCapacity; dataArrays = newDataArrays; } }
public static class DataArray<T>{
T data;
public T getData() { return data; }
public void setData(T data) { this.data=data; } }}
测试结果如下。
3. 使用链式存储结构实现栈
此处使用的是单向链表,非双向链表,由于链表不存在溢出的状况,所以不需要扩容,只需要新增数据时将旗子交给新来的,而取数据时将旗子交给他的下一个。
package netty;
/** * @author damao * @date 2019-11-28 10:40 */public class LinkedQueue<T>{
Node<T> front;
Node<T> rear;
public boolean inQueue(T t){ if(rear == null){ front = rear = new Node(t,null); }else { Node<T> node = new Node(t,null); rear = rear.next = node; } return true; }
public T outQueue(){ if(front == null){ throw new RuntimeException ("Queue is already empty"); } Node<T> result = front; front = result.next; result.next = null; return result.data; }
public static class Node<T>{
T data;
Node<T> next;
public Node(T data, Node<T> next) { this.data=data; this.next=next; } }}
测试结果如下
ps:两者的优缺点,顺序存储由于需要扩容,才能实现不会被溢出,而扩容之后需要将原数据进行拷贝,所以插入数据时相对而言会比链式队列慢一点,而取数据都是O(1),且实现代码来看,链式队列相比循环队列要简单很多,所以个人推荐使用链式队列。