java实现顺序队列

简介: 队列是一种特殊的线性表,他的特殊性体现在只能在尾部进行插入,头部进行删除,所以可以将队列看成是一种特殊的线性表。他的鲜明特点就是“先进先出”或者叫“后进后出”。队列这种数据结构的实现一般都是基于线性表的,而线性表又有顺序表和链表两种,所以队列的实现就又分为顺序队列和链队列。这篇文章用以总结使用顺序表来实现的队列–顺序队列。

前言:


队列是一种特殊的线性表,他的特殊性体现在只能在尾部进行插入,头部进行删除,所以可以将队列看成是一种特殊的线性表。他的鲜明特点就是“先进先出”或者叫“后进后出”。队列这种数据结构的实现一般都是基于线性表的,而线性表又有顺序表和链表两种,所以队列的实现就又分为顺序队列和链队列。这篇文章用以总结使用顺序表来实现的队列–顺序队列。


一、实现过程



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,队列的出队和入队满足“先入先出”的规则,说明也没有问题。20210512152932796.gif


2.测试其他方法


其他方法里包括了清空、判空、长度等方法,长度在上面已经测试了显示是没有问题的,这里测试下清空和判空的方法,测试接口如下:


image.gif


从上面图片可以看出,插入五个元素后队列长度是5,此时队列非空false,然后清空队列,此时队列是空true,获取队列元素时null。可以发现其他方法的实现也是没有问题的。


三、总结



这篇文章总结了顺序队列的实现,代码是没有难度的,主要是掌握队列的思想。队列是一种使用很广的数据结构,使用频率也很高,比如finalize队列,线程池的等待队列,以及各种阻塞非阻塞队列等等。所以说掌握队列的思想还是很有必要的,这篇文章只是以一个实现者的角度去写的,可能并不是适合很多人,但也希望可以帮到看到这篇文章的你。


相关文章
|
27天前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
28 2
|
6月前
|
算法 Java
Java数据结构——队列
Java数据结构——队列
46 4
|
2月前
|
Java API 容器
JAVA并发编程系列(10)Condition条件队列-并发协作者
本文通过一线大厂面试真题,模拟消费者-生产者的场景,通过简洁的代码演示,帮助读者快速理解并复用。文章还详细解释了Condition与Object.wait()、notify()的区别,并探讨了Condition的核心原理及其实现机制。
|
27天前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
29 0
|
3月前
|
Java
java中的队列
这篇文章通过Java代码示例介绍了使用数组实现队列操作,包括队列的初始化、入队、出队、判断队列满和空以及遍历队列的方法。
java中的队列
|
4月前
|
设计模式 安全 Java
Java面试题:请解释Java中的线程池以及为什么要使用线程池?请解释Java中的内存模型以及如何避免内存泄漏?请解释Java中的并发工具包以及如何实现一个简单的线程安全队列?
Java面试题:请解释Java中的线程池以及为什么要使用线程池?请解释Java中的内存模型以及如何避免内存泄漏?请解释Java中的并发工具包以及如何实现一个简单的线程安全队列?
43 1
|
5月前
|
Java 开发者
揭秘!LinkedList是如何华丽变身成为Java队列之王的?
【6月更文挑战第18天】Java的`LinkedList`既是列表也是队列之星,实现`Queue`接口,支持FIFO操作。其内部的双向链表结构确保了添加/移除元素的高效性(O(1)),适合作为队列使用。它线程不安全,但可通过同步包装用于多线程环境。此外,`LinkedList`还能灵活变身栈或双端队列,提供多种数据结构功能。
55 11
|
5月前
|
Java
2023蓝桥杯大赛软件类省赛Java大学B组G题 买二增一 队列的简单应用
2023蓝桥杯大赛软件类省赛Java大学B组G题 买二增一 队列的简单应用
36 1
|
5月前
|
安全 Java
Java Queue新玩法:用LinkedList打造高效队列,让你的代码飞起来!
【6月更文挑战第18天】Java集合框架中的`LinkedList`不仅是列表,还可作为高效队列。由于其在链表两端进行添加/移除操作的时间复杂度为O(1),故适合实现并发环境下的任务队列。通过案例展示了如何创建、添加任务及确保线程安全,揭示了`LinkedList`提升代码性能的秘密,特别是在多线程应用中的价值。
47 4
|
5月前
|
安全 Java 调度
Java Queue深度解析:LinkedList为何成为队列的最佳实践?
【6月更文挑战第18天】Java的`LinkedList`适合作为队列,因其双向链表结构支持O(1)的头尾操作。非线程安全的`LinkedList`在单线程环境下效率高,多线程时可通过`Collections.synchronizedList`封装。此外,它还可兼做栈和双端队列,提供任务调度的高效解决方案。
59 3