数据结构——队列

简介

队列是是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

 

队列是一种先进先出的线性表，简称FIFO允许插入的以端称为队尾，允许删除的一端被称为队头。

入队

出队

队列的两种存储表示：

• 顺序表示：与顺序栈相似，队列的顺序存储结构会用一组地址连续的存储单元依次存储对猎头到队列尾的元素，还分别有头指针和尾指针指向队列头和队列尾。

  • 顺序结构队列的初始化：①设置队列最大长度；②头尾指针为0；③插入新队尾元素，尾指针加一；④删除头元素时，头指针加一。
  • 队列假溢出：当队列的最大空间为6，而头指针为5，尾指针为6时，将不可再继续插入新的队尾元素，实际上队列的实际可用空间并未沾满，此为“假溢出”现象。
  • 假溢出的解决方案：循环队列，队空条件：头指针=尾指针；队满条件：（尾指针+1）%MAXQSIZE == 头指针。　

• 链式表示：用链表标识的队列简称为链队。

  • 链队的初始化：①构造一个只有头结点的控队，头尾指针相等，头结点的指针域为null。
  • 入队：为新队尾元素分配结点，将新结点插入队尾，修改队尾指针的值。
  • 出队：判断对是否为空，空则出错，否则取出队列的队头元素，修改头指针。　　

队列的应用

• 用于管理多线程中的线程。
• 用于实施排队系统。

队列的抽象接口

public interface Queue<E> { /** * 队列的容量 * @return */ int getSize(); /** * 队列是否为空 * @return */ boolean isEmpty(); /** * 向队列中添加元素 * @param e */ void enqueue(E e); /** * 向队列取出元素 * @return */ E dequeue(); /** * 查看队列第一个元素 * @return */ E getFront(); }

数组实现队列

public class ArrayQueue<E> implements Queue<E> { private E[] data; private int size; public ArrayQueue(){ this(10); } public ArrayQueue(int capacity){ this.data = (E[]) new Object[capacity]; this.size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } /** * 获取队列的容量 * @return */ public int getCapacity(){ return data.length; } @Override public void enqueue(E e) { addLast(e); } @Override public E dequeue() { return removeFirst(); } @Override public E getFront() { return get(0); } /** * 获取指定索引位置的值 * @param index * @return */ public E get(int index){ if(index < 0 || index >= size){ throw new IllegalArgumentException("Get failed. index is illegal."); } return data[index]; } /** * 数组尾部新增元素 * @param e */ private void addLast(E e){ add(size, e); } /** * 在指定位置插入元素 * @param index * @param e */ private void add(int index, E e){ if(index < 0 || index > size){ throw new IllegalArgumentException("AddLast failed. require index >=0 and index <= size"); } if(size == data.length){ //扩容 resize(2 * data.length); } for(int i = size - 1; i >= index; i --){ data[i + 1] = data[i]; } data[index] = e; size ++; } /** * 数组扩容 * @param newCapacity */ private void resize(int newCapacity){ E[] newData = (E[])new Object[newCapacity]; for (int i = 0; i < size; i++) { newData[i] = data[i]; } data = newData; } /** * 删除数组中第一个元素 * @return */ public E removeFirst(){ return remove(0); } /** * 删除栈数组中index位置的元素, 并返回删除的元素 * @param index * @return */ private E remove(int index){ if(index < 0 || index >= size){ throw new IllegalArgumentException("Remove failed. index is illegal."); } E ret = data[index]; for (int i = index; i < size - 1; i++) { data[i] = data[i + 1]; } size --; data[size] = null; if(size == data.length / 4 && data.length / 2 != 0){ //当数组长度缩小为原数组的4分之一的时候才进行数组的缩容， //缩小为原数组的2分之一，预留空间，防止有数据添加导致扩容浪费性能 resize(data.length / 2); } return ret; } @Override public String toString(){ StringBuilder sb = new StringBuilder(); sb.append("Queue: "); sb.append("front ["); for (int i = 0; i < size; i++) { sb.append(data[i]); if(i != size - 1){ sb.append(", "); } } sb.append("] tail"); return sb.toString(); } }

循环队列

队列首位相接的顺序存储结构。

通过这样的方法，我们成功避免了数据搬移操作。看起来不难理解在用数组实现的非循环队列中，队满的判断条件是 tail == n，队空的判断条件是 head == tail。那针对循环队列，如何判断队空和队满呢？ 队列为空的判断条件仍然是 head == tail。但队列满的判断条件就稍微有点复杂了。

tail=3，head=4，n=8，所以总结一下规律就是：(3+1)%8=4。当队满时，(tail+1)%n=head，当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会 浪费一个数组的存储空间。

基于数组实现

public class LoopQueue<E> implements Queue<E> { private E[] data; //队首 private int front; //队尾 private int tail; private int size; public LoopQueue(){ this(10); } public LoopQueue(int capacity){ //在该实现中front==tail表示队列为空，所以存储容量的时候要空一格 this.data = (E[]) new Object[capacity + 1]; this.front = 0; this.tail = 0; this.size = 0; } public int getCapacity(){ return data.length - 1; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return front == tail; } @Override public void enqueue(E e) { if((tail + 1) % data.length == front){ resize(getCapacity() * 2); } data[tail] = e; tail = (tail + 1) % data.length; size ++; } private void resize(int newCapacity){ E[] newData = (E[])new Object[newCapacity + 1]; for (int i = 0; i < size; i++) { newData[i] = data[(i + front) % data.length]; } data = newData; front = 0; tail = size; } @Override public E dequeue() { if(isEmpty()){ throw new IllegalArgumentException("Cannot dequeue from an empty queue."); } E ret = data[front]; data[front] = null; front = (front + 1) % data.length; size --; if(size == getCapacity() / 4 && getCapacity() / 2 != 0){ resize(getCapacity() / 2); } return ret; } @Override public E getFront() { if(isEmpty()){ throw new IllegalArgumentException("Queue is Empty."); } return data[front]; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append(String.format("Queue：size=%d, capacity=%d\n",size,getCapacity())); sb.append("front ["); for (int i = front; i != tail; i = (i + 1) % data.length) { sb.append(data[i]); if((i + 1) % data.length != tail){ sb.append(", "); } } sb.append("] tail"); return sb.toString(); } }

链表队列

public class LinkedListQueue<E> implements Queue<E> { private class Node<E>{ public E e; public Node<E> next; public Node(E e){ this.e = e; } @Override public String toString() { return e.toString(); } } private Node<E> head, tail; private Integer size; public LinkedListQueue(){ head = null; tail = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void enqueue(E e) { if(tail == null){ head = tail = new Node<>(e); }else { tail = tail.next = new Node<>(e); } size ++; } @Override public E dequeue() { if(isEmpty()){ throw new IllegalArgumentException("Cannot dequeue from an empty queue."); } Node<E> retNode = head; head = head.next; retNode.next = null; if(head == null){ tail = null; } size --; return retNode.e; } @Override public E getFront() { if(isEmpty()){ throw new IllegalArgumentException("Cannot dequeue from an empty queue."); } return head.e; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("Queue: front "); Node<E> cur = head; while (cur != null){ sb.append(cur + "->"); cur = cur.next; } sb.append("NULL tail"); return sb.toString(); } }

对比测试

public class Test { //测试使用queue运行opCount个enQueue和deQueue操作所需的时间，单位：秒 private static double testQueue(Queue<Integer> queue,int opCount){ long startTime = System.nanoTime(); Random random = new Random(); for (int i = 0; i < opCount; i++) { queue.enqueue(random.nextInt(Integer.MAX_VALUE)); } for (int i = 0; i < opCount; i++) { queue.dequeue(); } long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { int opCount = 100000; ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>(); double time1 = testQueue(arrayQueue,opCount); System.out.println("ArrayQueue, time: "+time1+" s"); LoopQueue<Integer> loopQueue = new LoopQueue<Integer>(); double time2 = testQueue(loopQueue,opCount); System.out.println("LoopQueue, time: "+time2+" s"); LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<Integer>(); double time3 = testQueue(linkedListQueue,opCount); System.out.println("LinkedListQueue, time: "+time3+" s"); } }

可见链表队列和循环队列相差不大，而数组队列时间差距是将近200多倍。

应用

阻塞队列

阻塞队列在队列基础上增加了阻塞操作。在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生 产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。

 

而且不仅如此，基于阻塞队列，我可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。比如前面的例子，我们可以多配置几个“消费者”，来应对一个“生产者”。

并发队列

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法 上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用 更加广泛的原因。

 

参考： https://blog.csdn.net/weixin_39084521/article/details/89820114

https://www.cnblogs.com/smallzhen/p/14165352.html