队列 (Queue) 是一种限定性的有序线性表,它只允许在表的一端插入元素,而在另一端删除元素,所以队列具有先进先出 (Fist In Fist Out,缩写为FIFO)的特性。
数据元素:可以是任意类型的数据,但必须属于同一个数据对象。
关系:队列中数据元素之间是线性关系。
基本操作:
1.初始化操作。使用构造方法设置一个空队列。
2.isEmpty():判空操作。若队列为空,则返回TRUE,否则返回FALSE。
3.isFull():判满操作。若队列为满,则返回TRUE,否则返回FALSE。
4.getSize():获取队列元素个数。
5.add(E e):进队操作。在队列Q的队尾插入e。如果队满,抛出异常。
6.poll():出队操作。使队列Q的队头元素出队,并用e返回其值。如果队空,抛出异常。
7.getHead ():取队头元素操作。用e取得队头元素的值。如果队列为空,则返回null。
8.clear():队列置空操作。将队列Q置为空队列。
9.destroy():队列销毁操作。释放队列的空间。
队列的一种顺序存储称为顺序队列。与顺序栈类似,在队列的顺序存储结构中,用一组地址连续的存储单元依次存放从队头到队尾的元素,如一维数组Queue[maxSize]。
由于队列中队头和队尾的位置都是动态变化的,因此需要附设两个指针 front和 rear。
front = rear = 0
。front == rear
。rear == maxSize
。maxSize
,则将数据存入rear所指的数组元素中,否则无法存入数据;然后将尾指针往后移: rear + 1
。front + 1
。定义接口方法:
/** * description:自定义队列接口 * * @author RenShiWei * Date: 2021/5/29 20:45 **/ public interface Queue<E> { /** * @return 是否队空 */ boolean isEmpty(); /** * @return 是否队满 */ boolean isFull(); /** * @return 队列的可承载元素个数 */ int getCapacity(); /** * @return 队列元素个数 */ int getSize(); /** * 队尾入队 * * @param e 入队元素 */ void add(E e); /** * 队首出队 * * @return 出队元素 */ E poll(); /** * 获取队首元素 * * @return 队首元素 */ E getHead(); }
/** * description:数组队列 * * @author RenShiWei * Date: 2021/5/29 20:41 **/ public class ArrayQueue<E> implements Queue<E> { /** 表示可存储元素的最大容量 */ private int maxSize; /** 队列头 */ private int front; /** 队列尾 */ private int rear; /** 该数据用于存放数据,模拟队列 */ private E[] data; /** * 初始化队列 * * @param arrMaxSize 初始队列最大容量 */ @SuppressWarnings("unchecked") public ArrayQueue(int arrMaxSize) { maxSize = arrMaxSize; data = (E[]) new Object[maxSize]; front = 0; rear = 0; } /** * @return 是否队空 */ @Override public boolean isEmpty() { return front == rear; } /** * @return 是否队满 */ @Override public boolean isFull() { return rear == maxSize; } /** * @return 队列元素个数 */ @Override public int getSize() { return rear - front; } /** * 队尾入队 * * @param e 入队元素 */ @Override public void add(E e) { if (isFull()) { throw new IllegalArgumentException("队列已满,不能入队!"); } data[rear++] = e; } /** * 队首出队 * * @return 出队元素 */ @Override public E poll() { if (isEmpty()) { throw new IllegalArgumentException("队列为空,不能出队!"); } //出队位置置null E temp = data[front]; data[front++] = null; return temp; } /** * 获取队首元素 * 如果队空,返回null * * @return 队首元素 */ @Override public E getHead() { return data[front]; } /** * @return 队列的可承载元素个数 */ @Override public int getCapacity() { return data.length - 1; } /** * @return 队列的有效容量(未使用的空间数量) */ public int getEmptyCount() { return maxSize - rear; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Queue: "); res.append("front ["); for (int i = front; i < rear; i++) { res.append(data[i]); if (i != rear - 1) { res.append(", "); } } res.append("] rear"); return res.toString(); } /** * 队列测试 */ public static void main(String[] args) { ArrayQueue<Integer> queue = new ArrayQueue<>(5); Scanner sc = new Scanner(System.in); char c; boolean loop = true; while (loop) { System.out.println("s(toString):输出队列"); System.out.println("e(exit):退出程序"); System.out.println("a(add):添加数据到队列"); System.out.println("p(poll):从队列取出数据"); System.out.println("h(getHead):查看队列头的数据"); System.out.println("n(isEmpty):是否队空"); System.out.println("f(isFull):是否队满"); c = sc.next().charAt(0); switch (c) { case 's': System.out.println("当前队列:" + queue.toString() + "\t元素个数:" + queue.getSize() + "\t有效容量:" + queue.getEmptyCount()); break; case 'e': sc.close(); loop = false; break; case 'a': System.out.println("请输入一个整数"); queue.add(sc.nextInt()); break; case 'p': System.out.printf("出队元素:%d\n", queue.poll()); break; case 'h': System.out.printf("队首元素:%d\n", queue.getHead()); break; case 'n': System.out.println("队空:" + queue.isEmpty()); break; case 'f': System.out.println("队满:" + queue.isFull()); break; default: break; } } System.out.println("程序退出"); } }
假溢出现象
在非空顺序队列中,队头指针始终指向当前的队头元素,而队尾指针始终指向真正队尾元素。当rear == maxSize - 1
时,认为队满。但此时不一定是真的队满,因为随着部分元素的出队,数组前面会出现一些空单元,如下图所示。由于只能在队尾入队,使得上述空单元无法使用。把这种现象称为假溢出。
问题:目前这个数组使用一次就不能用(出队的空间),没有达到复用的效果。可使用算法将其改造成环形队列(取模:%)。
为了解决假溢出现象并使得队列空间得到充分利用,一个较巧妙的办法是将顺序队列的数组看成一个环状的空间,即规定最后一个单元的后继为第一个单元,我们形象地称之为循环队列。
front = rear = 0
。front
指向队列的第一个元素,rear
指向队列最后一个元素的后一个位置(希望损失一个位置作为约定,用来区分队空和队满)。front == rear
。(rear + 1) % maxSize == front
。(rear + maxSize - front) % maxSize
。rear
所指的数组元素中,指针变化:rear = ( rear+1) % maxSize
。front
所指的数组元素中,指针变化:front = ( front+1 ) % maxSize
。下图给出了循环队列的几种情况:
/** * description:循环队列 * * @author RenShiWei * Date: 2021/5/30 16:38 **/ public class LoopQueue<E> implements Queue<E> { /** 存储元素 数组的长度(有效长度需要-1) */ private int maxSize; /** 队列头 */ private int front; /** 队列尾 */ private int rear; /** 该数据用于存放数据,模拟队列 */ private E[] data; /** * 初始化环形队列 * * @param arrMaxSize 初始队列容量 */ @SuppressWarnings("unchecked") public LoopQueue(int arrMaxSize) { //循环队列需要有意识浪费一个空间 maxSize = arrMaxSize + 1; data = (E[]) new Object[maxSize]; } /** * @return 是否队空 */ @Override public boolean isEmpty() { return front == rear; } /** * @return 是否队满 */ @Override public boolean isFull() { return (rear + 1) % maxSize == front; } /** * @return 队列的可承载元素个数 */ @Override public int getCapacity() { return data.length - 1; } /** * @return 队列元素个数 */ @Override public int getSize() { return (rear + maxSize - front) % maxSize; } /** * 队尾入队 * * @param e 入队元素 */ @Override public void add(E e) { if (isFull()) { throw new IllegalArgumentException("队列已满,不能入队!"); } data[rear] = e; //rear指针后移一位 rear = (rear + 1) % maxSize; } /** * 队首出队 * * @return 出队元素 */ @Override public E poll() { if (isEmpty()) { throw new IllegalArgumentException("队列为空,不能出队!"); } E temp = data[front]; //出队位置置null data[front] = null; //front指针后移一位 front = (front + 1) % maxSize; return temp; } /** * 获取队首元素 * 如果队空,返回null * * @return 队首元素 */ @Override public E getHead() { return data[front]; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("Queue: size = %d , capacity = %d\n", getSize(), getCapacity())); res.append("front ["); for (int i = front; i != rear; i = (i + 1) % data.length) { res.append(data[i]); if ((i + 1) % data.length != rear) { res.append(", "); } } res.append("] tail"); return res.toString(); } /** * 队列测试 */ public static void main(String[] args) { LoopQueue<Integer> queue = new LoopQueue<>(5); Scanner sc = new Scanner(System.in); char c; boolean loop = true; while (loop) { System.out.println("s(toString):输出队列"); System.out.println("e(exit):退出程序"); System.out.println("a(add):添加数据到队列"); System.out.println("p(poll):从队列取出数据"); System.out.println("h(getHead):查看队列头的数据"); System.out.println("n(isEmpty):是否队空"); System.out.println("f(isFull):是否队满"); c = sc.next().charAt(0); switch (c) { case 's': System.out.println("当前队列:" + queue.toString()); break; case 'e': sc.close(); loop = false; break; case 'a': System.out.println("请输入一个整数"); queue.add(sc.nextInt()); break; case 'p': System.out.printf("出队元素:%d\n", queue.poll()); break; case 'h': System.out.printf("队首元素:%d\n", queue.getHead()); break; case 'n': System.out.println("队空:" + queue.isEmpty()); break; case 'f': System.out.println("队满:" + queue.isFull()); break; default: break; } } System.out.println("程序退出"); } }
相比数组队列来说,循环队列解决了数组空间不能再次利用的问题。但依然存在一些问题:
ArrayList
来分析,在存储空间允许的条件下是可以一直添加元素的。因此,是否可以实现动态的将循环队列进行扩容或者缩容,上述两个问题,可以利用下面的动态循环队列来实现。
当然,上述的数组队列,也可以改造成动态的,但是出队元素的空间依然会浪费,所以没必要进行实现。
为了解决循环队列,队满不能入队,以及频繁入队出队引起的空间浪费,而引出动态循环队列的概念。即在队满时进行扩容,在队列元素个数下降到一定情况下进行缩容。
front
指针置为0;将rear
指针值到最后一个元素的位置(即存储有效元素的数量)。/** * description:动态循环 * * @author RenShiWei * Date: 2021/5/30 17:06 **/ public class DynamicLoopQueue<E> implements Queue<E> { /** 存储元素 数组的长度(有效长度需要-1) */ private int maxSize; /** 队列头 */ private int front; /** 队列尾 */ private int rear; /** 该数据用于存放数据,模拟队列 */ private E[] data; /** * 初始化环形队列 * * @param arrMaxSize 初始队列容量 */ @SuppressWarnings("unchecked") public DynamicLoopQueue(int arrMaxSize) { //循环队列需要有意识浪费一个空间 maxSize = arrMaxSize + 1; data = (E[]) new Object[maxSize]; } /** * @return 是否队空 */ @Override public boolean isEmpty() { return front == rear; } /** * @return 是否队满 */ @Override public boolean isFull() { return (rear + 1) % maxSize == front; } /** * @return 队列的可承载元素个数 */ @Override public int getCapacity() { return data.length - 1; } /** * @return 队列元素个数 */ @Override public int getSize() { return (rear + maxSize - front) % maxSize; } /** * 队尾入队 * * @param e 入队元素 */ @Override public void add(E e) { if (isFull()) { //队满不再进行报错,而是进行动态扩容 resize(getCapacity() * 2); } data[rear] = e; //rear指针后移一位 rear = (rear + 1) % maxSize; } /** * 队首出队 * * @return 出队元素 */ @Override public E poll() { if (isEmpty()) { throw new IllegalArgumentException("队列为空,不能出队!"); } E temp = data[front]; //出队位置置null data[front] = null; //front指针后移一位 front = (front + 1) % maxSize; //当数组实际元素减小到空间的一半的时候,对其进行缩小 //if(size == data.length / 2) /* 解决当一半的时候一次添加,一次删除,造成的一直扩容和减小的操作, 增加必须要扩容,所以可以让缩容变得更懒时在进行,即1/4时 data.length / 2 != 0防止数组大小最后变成0,造成异常 */ if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0) { resize(getCapacity() / 2); } return temp; } /** * 获取队首元素 * 如果队空,返回null * * @return 队首元素 */ @Override public E getHead() { return data[front]; } /** * 扩容方法 * * @param newCapacity 扩容后的队列大小 */ @SuppressWarnings("unchecked") private void resize(int newCapacity) { E[] newData = (E[]) new Object[newCapacity + 1]; //有多个元素循环多少次 for (int i = 0; i < getSize(); i++) { //循环队列会发生偏移,重新赋值给新数组 newData[i] = data[(i + front) % data.length]; } data = newData; maxSize = data.length; //重置指针 front = 0; rear = getSize(); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("Queue: size = %d , capacity = %d\n", getSize(), getCapacity())); res.append("front ["); for (int i = front; i != rear; i = (i + 1) % data.length) { res.append(data[i]); if ((i + 1) % data.length != rear) { res.append(", "); } } res.append("] tail"); return res.toString(); } /** * 队列测试 */ public static void main(String[] args) { DynamicLoopQueue<Integer> queue = new DynamicLoopQueue<>(3); Scanner sc = new Scanner(System.in); char c; boolean loop = true; while (loop) { System.out.println("s(toString):输出队列"); System.out.println("e(exit):退出程序"); System.out.println("a(add):添加数据到队列"); System.out.println("p(poll):从队列取出数据"); System.out.println("h(getHead):查看队列头的数据"); System.out.println("n(isEmpty):是否队空"); System.out.println("f(isFull):是否队满"); c = sc.next().charAt(0); switch (c) { case 's': System.out.println("当前队列:" + queue.toString()); break; case 'e': sc.close(); loop = false; break; case 'a': System.out.println("请输入一个整数"); queue.add(sc.nextInt()); break; case 'p': System.out.printf("出队元素:%d\n", queue.poll()); break; case 'h': System.out.printf("队首元素:%d\n", queue.getHead()); break; case 'n': System.out.println("队空:" + queue.isEmpty()); break; case 'f': System.out.println("队满:" + queue.isFull()); break; default: break; } } System.out.println("程序退出"); } }