《大话数据结构》队列的顺序存储和链式存储
《大话数据结构》队列的顺序存储和链式存储
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），且实现代码来看，链式队列相比循环队列要简单很多，所以个人推荐使用链式队列。