爱喝兽奶帝天荒

这个屌丝很懒，什么也没留下！

热门标签

通过Java实现数据结构：链式队列以及顺序循环队列

作者：爱喝兽奶帝天荒 | 2024-07-25 12:27:34

踩

目录

（一）链式队列

一、代码结构

二、程序源码

1.PollEmptyException类：

2.MyQueue类（包含双向链表节点内部类，当然类外定义也可以）：

(1）定义

(2）内部类ListNode

(3）成员变量

(4) 相关方法

1）入队方法

2）出队方法（包括一个出队判空抛出异常的底层方法）

3）获取队头元素方法（调用判空抛出异常的方法）

4）判断队列是否为空的方法

三、测试案例

Test类源码如下

运行结果如下

（二）顺序循环队列

一、代码结构

二、程序源码

1.PollEmptyException类：

2.OfferFullException类：

3.MyQueue类：

（1）定义

（2）成员变量

（3）相关方法

1）构造方法

2）入队方法（包括一个入队判满抛出异常的底层方法）

3）出队方法（包括一个出队判空抛出异常的底层方法）

4）获取队头元素方法（调用判空抛出异常的方法）

5）判断队列是否为满的方法

6）判断队列是否为空的方法

三、测试案例

Test类源码如下

运行结果如下

队列是一种先进先出的特殊数据结构，在Java的集合框架中可以通过应用了Queue接口的LinkedList集合类实现（LinkedList不仅可以作为双向链表使用，也可以作为栈和队列使用）。本文将以双向链表为底层结构模拟实现队列（链式队列）以及以数组为底层结构模拟实现队列（顺序循环队列），并实现队列中的入队、出队、获取队头元素、判断队列是否为空的方法。

（一）链式队列

一、代码结构

1.MyQueue:实现链式队列。

2.PollEmptyException:用于队列为空时做出非法操作时抛出异常。

3.Test:其main方法用于测试MyQueue相关操作。

二、程序源码

1.PollEmptyException类：


public class PollEmptyException extends RuntimeException{
    public PollEmptyException() {
        super();
    }
 
    public PollEmptyException(String message) {
        super(message);
    }
}

注意：PollEmptyException属于运行时异常，应当继承于RuntimeException，并且重写相关方法。

2.MyQueue类（包含双向链表节点内部类，当然类外定义也可以）：

(1）定义

public class MyQueue

(2）内部类ListNode


    static class ListNode{
        //数组域
        public int val;
        //两个指针域
        public ListNode prev;
        public ListNode next;
        //指定数值的构造方法
        public ListNode(int val){
            this.val=val;
        }
    }

(3）成员变量


    //队头指针
    private ListNode front;
    //队尾指针
    private ListNode rear;

(4) 相关方法

1）入队方法


    //入队方法
    public int offer(int val){
        ListNode listNode=new ListNode(val);
        if(front==null){
            front=rear=listNode;
        }else{
            rear.next=listNode;
            listNode.prev=rear;
            rear=listNode;
        }
        return listNode.val;
    }

2）出队方法（包括一个出队判空抛出异常的底层方法）


    //判空抛出异常方法
    private void checkPollisEmpty(){
        if(front==null){
            throw new PollEmptyException();
        }
    }
 
    //出队方法
    public int poll(){
        //出队判空抛出异常
        try{
            checkPollisEmpty();
        }catch (PollEmptyException e){
            e.printStackTrace();
        }
        int val= front.val;
        //判断是否为单一元素队列
        if(front.next==null)
        {
            front=rear=null;
        }
        front=front.next;
        front.prev=null;
        return val;
 
    }

3）获取队头元素方法（调用判空抛出异常的方法）


    //获取队头元素方法
    public int peek(){
        //判空抛出异常
        try{
            checkPollisEmpty();
        }catch (PollEmptyException e){
            e.printStackTrace();
        }
        return front.val;
    }

4）判断队列是否为空的方法


    //判断队列是否为空
    public boolean isEmpty(){
        return front==null;
    }

三、测试案例

Test类源码如下


public class Test {
    public static void main(String[] args) {
        MyQueue myQueue=new MyQueue();
        //入队操作
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);
        //获取队头元素值
        System.out.println("当前队头元素值为"+myQueue.peek());
        System.out.println("*****************************");
        //出队操作
        System.out.println("出队元素值为"+myQueue.poll());
        System.out.println("当前队头元素值为"+myQueue.peek());
        System.out.println("*****************************");
        //判空操作
        System.out.println(myQueue.isEmpty());
 
    }
}

运行结果如下

（二）顺序循环队列

顺序循环队列与链式队列的区别是，其底层通过数组实现，并且多出了判满操作。

由于入队时只能从队尾rear处入队，出队时只能从队头front处出队，所以显而易见队头前面的存储空间会随着队列的使用而被搁置浪费（即无法再被新元素占用），所以我们可以通过令front以及rear两个指示器循环移动的方式实现逻辑上为环的循环数组，进而实现顺序循环队列，具体代码如下。

一、代码结构

1.MyQueue:实现链式队列。

2.PollEmptyException:用于队列为空时做出非法操作时抛出异常。

3.OfferFullException:用于队列为满时做出非法操作时抛出异常。

4.Test:其main方法用于测试MyQueue相关操作。

二、程序源码

1.PollEmptyException类：


public class PollEmptyException extends RuntimeException{
    public PollEmptyException() {
        super();
    }
 
    public PollEmptyException(String message) {
        super(message);
    }
}

2.OfferFullException类：


public class OfferFullException extends RuntimeException{
    public OfferFullException() {
        super();
    }
 
    public OfferFullException(String message) {
        super(message);
    }
}

注意：PollEmptyException和OfferFullException均属于运行时异常，应当继承于RuntimeException，并且重写相关方法。

3.MyQueue类：

（1）定义

public class MyQueue

（2）成员变量


    //数组引用，指向队列所储存元素的数组
    private int[]elem;
    //队头指示器（指向当前队头元素的位置）
    private int front;
    //队尾指示器（指向下一个入队元素的位置）
    private int rear;

（3）相关方法

1）构造方法


 public MyQueue(){
        elem=new int[10];
    }

2）入队方法（包括一个入队判满抛出异常的底层方法）


    //检查队列是否为满的方法
    private void checkFull(){
        if(isFull()){
            throw new OfferFullException();
        }
    }
    //入队方法
    public int offer(int val){
        //判满抛出异常
        try{
            checkFull();
        }catch (OfferFullException e){
            e.printStackTrace();
        }
        elem[rear]=val;
        rear=(rear+1)%elem.length;
        return val;
    }

入队时rear加1再对数组长度取余数，就可以保证rear在数组下标中不断循环，从而避免空间浪费。

3）出队方法（包括一个出队判空抛出异常的底层方法）


    //检查队列是否为空的方法
    private void checkEmpty(){
        if(isEmpty()){
            throw new PollEmptyException();
        }
    }
 
    //出队方法
    public int poll(){
        //判空抛出异常
        try{
            checkEmpty();
        }catch (PollEmptyException e){
            e.printStackTrace();
        }
         int val=elem[front];
        front=(front+1)%elem.length;
        return val;
    }

出队时front加1再对数组长度取余数，就可以保证front在数组下标中不断循环，从而避免空间浪费。

4）获取队头元素方法（调用判空抛出异常的方法）


    //获取队头元素方法
    public int peek(){
        //判空抛出异常
        try{
            checkEmpty();
        }catch (PollEmptyException e){
            e.printStackTrace();
        }
        return elem[front];
    }

5）判断队列是否为满的方法


    //判断队列是否为满方法
    public boolean isFull(){
        return (rear+1)%elem.length==front;
    }

注意：循环顺序队列判满不能直接简单地判断front和rear是否直接相等，因为直接相等时也可能时队列为空的情况，此时二者无法区分。因此为了正确判满，可以采用故意空出一个存储空间的方法，此时队列的实际存储大小为数组长度减一，判满时可以判断rear+1再对数组长度取余是否等于front来检测队列是否为满，这也与判断队列为空区分开（即判断队列为空此时可以采取直接判断front与rear是否相等的方式）。

除去空出存储空间的方法，也可以设置队列有效元素个数usedSize或者标志位flag，通过对标志变量进行检查也可以起到判满判空的效果。

6）判断队列是否为空的方法


    //判断队列是否为空方法
    public boolean isEmpty(){
        return front==rear;
    }

三、测试案例

Test类源码如下


public class Test {
    public static void main(String[] args) {
        MyQueue myQueue=new MyQueue();
        //入队操作
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);
        //获取队头元素值
        System.out.println("当前队头元素值为"+myQueue.peek());
        System.out.println("*****************************");
        //出队操作
        System.out.println("出队元素值为"+myQueue.poll());
        System.out.println("当前队头元素值为"+myQueue.peek());
        System.out.println("*****************************");
        //判空操作
        System.out.println(myQueue.isEmpty());
 
    }
}

运行结果如下

以上便是通过Java实现链式队列以及顺序循环队列的全部内容，如有不当，敬请斧正！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/880206