前言:
队列是一种特殊的线性表,他的特殊性体现在只能在尾部进行插入,头部进行删除,所以可以将队列看成是一种特殊的线性表。他的鲜明特点就是“先进先出”或者叫“后进后出”。队列这种数据结构的实现一般都是基于线性表的,而线性表又有顺序表和链表两种,所以队列的实现就又分为顺序队列和链队列。这篇文章用以总结使用顺序表来实现的队列–顺序队列。
一、实现过程
1.提供队列的接口:IQueue
该接口定义了队列中必须实现的方法,因此在队列实现时只需要继承该接口然后正确实现该接口中的方法即可。无论是顺序队列还是链队列。都可以通过实现该接口来实现,下面是该接口中具体定义的方法。
public interface IQueue { void clear(); boolean isEmpty(); int length(); Object peek();//查看队列头元素 void offer(Object object) throws Exception;//入队 Object poll();//出队 }
2.提供顺序队列的实现:ShunxuQueue
因为队列的特点是只能在尾部插入,头部删除,且是先进先出。所以我们需要定义两个指针(栈只需要一个),分别来指向头部和尾部。这两个指针就叫front和rear(习惯性命名),他们初始状态下为0,也代表了对列为空。注意前面这句话,初始状态下front和rear都为0,所以一旦有数据插入,我们就不能让front和rear相等了。所以当有一个数据元素时,front和rear不能都指向0,我们应该将rear指向尾部元素的后一位。这也就是为什么rear应该指向尾部元素后一位的原因。除了front和rear这两个指针,还需要提供一个数组用以存储数据。front和rear便是指向的数组的下标。然后使用构造函数对数组进行初始化。代码如下:
/** * * 队列可以插入的一端被称为队尾,可以删除的一端被称为队列头, * 所以队列的典型特征就是队尾插入,队头删除 * * @author pcc * @version 1.0.0 * @className ShunxuQueue * @date 2021-04-29 09:32 */ public class ShunxuQueue implements IQueue{ int front = 0; int rear = 0; Object[] objArray; public ShunxuQueue(int n){ objArray = new Object[n]; } }
3.提供清空(clear)、判空(isEmpty)、队列长度(length)等方法
这几个方法的实现都是非常简单,就一起说下就好。清空方法自然就是清空队列了。我们只需要将数组清空,将front和rear置为初始状态就好;判空方法,只需要判断front和rear是否相对即可,相等自然就是空,这也是队列的初始装填;队列的长度方法也很简单,已经知道rear指向的是队尾后一个元素,front指向的是队头的下标,所以队列的长度就是rear-front。三个方法的具体实现如下:
@Override public void clear() { objArray = null; front = rear = 0; } @Override public boolean isEmpty() { return front == rear; } @Override public int length() { return rear - front; }
4.提供入队方法:offer
根据队列的实现思想:尾部插入,头部删除;rear指向尾部元素的下一位。我们可以知道插入时只需要考虑rear即可,删除时才需要考虑fornt。因此代码如下实现:
@Override public void offer(Object object) throws Exception{ rear++; if(rear<=objArray.length) objArray[rear-1] = object; else throw new Exception("队列已满"); }
5.提供出队方法:poll
在出队时我们就需要考虑front的下标位置了。每次出队都应该让front加一位,front的最大值应该是和rear相等,此时队列为空。代码实现如下:
@Override public Object poll() { if(front!=rear){ Object obj = objArray[front]; front++; return obj; } return null; }
6.提供获取队列头部元素的方法:peek
该方法只是获取到队列的头部元素,并不对元素进行出队操作。因此在判定队列有效的情况下可以直接将front下标的位置的元素直接返回。代码如下:
@Override public Object peek() { if(objArray!=null) return objArray[front]; return null; }
7.提供实现的完整代码
到这里IQueue接口中所有的方法就全部都实现了,顺序队列的实现其实很简单,只要是知道思路相信绝大部分实现起来是没有压力的,完整代码如下:
/** * * 队列可以插入的一端被称为队尾,可以删除的一端被称为队列头, * 所以队列的典型特征就是队尾插入,队头删除 * * * @author pcc * @version 1.0.0 * @className ShunxuQueue * @date 2021-04-29 09:32 */ public class ShunxuQueue implements IQueue{ int front = 0; int rear = 0; Object[] objArray; public ShunxuQueue(int n){ objArray = new Object[n]; } @Override public void clear() { objArray = null; front = rear = 0; } @Override public boolean isEmpty() { return front == rear; } @Override public int length() { return rear - front; } @Override public Object peek() { if(objArray!=null) return objArray[front]; return null; } @Override public void offer(Object object) throws Exception{ rear++; if(rear<=objArray.length) objArray[rear-1] = object; else throw new Exception("队列已满"); } @Override public Object poll() { if(front!=rear){ Object obj = objArray[front]; front++; return obj; } return null; } }
二、测试顺序队列的相应方法
1.测试入队和出队
顺序队列的实现代码已经写完,接下来就需要测试下这些实现是否是正确的,先来测试下入队和出队的方法。按照图中的顺序插入若是输出的也是这个顺序,则说明队列的入队和出队没有问题。
从上图可以看到队列长度是5,队列的出队和入队满足“先入先出”的规则,说明也没有问题。
2.测试其他方法
其他方法里包括了清空、判空、长度等方法,长度在上面已经测试了显示是没有问题的,这里测试下清空和判空的方法,测试接口如下:
从上面图片可以看出,插入五个元素后队列长度是5,此时队列非空false,然后清空队列,此时队列是空true,获取队列元素时null。可以发现其他方法的实现也是没有问题的。
三、总结
这篇文章总结了顺序队列的实现,代码是没有难度的,主要是掌握队列的思想。队列是一种使用很广的数据结构,使用频率也很高,比如finalize队列,线程池的等待队列,以及各种阻塞非阻塞队列等等。所以说掌握队列的思想还是很有必要的,这篇文章只是以一个实现者的角度去写的,可能并不是适合很多人,但也希望可以帮到看到这篇文章的你。