循环队列和链队列（Java）

心已赠人 2023-06-27 06:09 15阅读 0赞

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

![format_png][]

**1.循环队列**

队列的**顺序储存结构**：用数组存储队列，引入front指针指向队头元素，rear指针指向队尾元素的下一个位置，当front=rear时，为空队列，结构如下图所示。

![format_png 1][]

当执行入队操作时，若数组尾部已满，而数组前部因有元素出队而有空位时，我们把新插入的元素从头开始入队，这样就类似于头尾相接的结构。

队列的这种头尾相接的顺序存储结构称为**循环队列**，如下图所示。

![format_png 2][]

上面队列的定义中提到，当front=rear时，为空队列，而在循环队列中，队列满时，front也等于rear，将无法判断队满和空的情况。

一种办法是设置一个标志变量flag，当front=rear时，通过判断flag是0还是1来确定队列满空情况；

另一种方法是，在数组中只剩一个空闲单位时，定义为队列满，如下图所示。（本文程序采用这种办法）

![format_png 3][]

因为rear可能比front大，也可能比front小，所以队列满的条件应该为：**(rear+1)%maxSize==fron**t；同理，队列长度的计算公式为：**(rear-front+maxSize)%maxSize**。

实现程序：

/**
     * <循环队列>
     *
     * 注意点：表长的表示、队列满的判断、front和rear的改变
     *
     */
    public class SqQueue<E> {
        private E[] data;
        private int front;
        private int rear;
        private int maxSize;
        private static final int DEFAULT_SIZE= 10;
         
        /*
         * 初始化
         */
        public SqQueue(){
            this(DEFAULT_SIZE);
        }
        public SqQueue(int maxSize){
            data=(E[]) new Object[maxSize];
            this.maxSize=maxSize;
            front=0;
            rear=0;
        }
         
        /*
         * 求循环队列长度
         */
        public int getLength() {
            return (rear-front+maxSize)%maxSize;
        }
         
        /*
         * 入队操作
         */
        public void enQueue(E e) {
            if((rear+1)%maxSize==front)
                throw new RuntimeException("队列已满，无法入队！");
            data[rear]=e;
            rear=(rear+1)%maxSize;
            //不是rear=rear+1，当rear在数组尾部时，后移一位会转到数组头部
        }
         
        /*
         * 出队操作
         */
        public E deQueue() {
            if(rear==front)
                throw new RuntimeException("队列为空！");
            E e=data[front];
            front=(front+1)%maxSize;
            //不是front++，理由同rear
            return e;
        }
         
        /*
         * 打印操作
         */
        public void printQueue() {
            int k=front;
            for(int i=0;i<getLength();i++) {
                System.out.print(data[k]+" ");
                k=(k+1)%maxSize;
            }
            System.out.println();
        }
         
        /*
         * 测试代码
         */
        public static void main(String[] args) {
            SqQueue<String> aQueue=new SqQueue<>(5);   
            aQueue.enQueue("a");
            aQueue.enQueue("b");
            aQueue.enQueue("c");
            aQueue.enQueue("d");
            aQueue.printQueue();
            System.out.println("-----");
            aQueue.getLength();
            aQueue.deQueue();
            aQueue.deQueue();
            aQueue.enQueue("e");
            aQueue.printQueue();
        }
         
    }

**2.队列的链式存储结构**

用单链表存储队列，称为**链队列**。

定义front指针指向头结点，rear指针指向终端结点，空队列时，front和rear都指向头结点。

![format_png 4][]

![format_png 5][]

实现程序：

/**
     * 链队列
     *
     * 注意点：出队操作时，若队头是队尾（即队中仅有一个结点），则删除后要将rear指向头结点。
     *
     */
    public class LinkQueue<E> {
        private QNode front,rear;
        private int count;
         
        class QNode{
            E data;
            QNode next;
            public QNode(E data,QNode next) {
                this.data=data;
                this.next=next;
            }
        }
         
        public LinkQueue() {
            front=new QNode(null, null);
            rear=front;
            count=0;
        }
         
        /*
         * 入队操作
         */
        public void enQueue(E e) {
            QNode node=new QNode(e, null);
            rear.next=node;
            rear=node;
            count++;
        }
         
        /*
         * 出队操作
         */
        public E deQueue() {
            if(rear==front)
                throw new RuntimeException("队列为空！");
            QNode node=front.next;
            E e=node.data;
            front.next=node.next;
            //若队头是队尾，则删除后要将rear指向头结点。
            if(rear==node)
                rear=front;
            node=null;
            count--;
            //通过count来判断，可能更容易理解
            //if(count==0)
            //  rear=front;
            return e;
        }
         
        /*
         * 获取队列长度
         */
        public int getLength() {
            return count;
        }
         
        /*
         * 打印输出队列
         */
        public void printQueue() {
            if(count==0) {
                System.out.println("空队列"); 
            }else {
                QNode node=front;
                for(int i=0;i<count;i++) {
                    node=node.next;
                    System.out.print(node.data+" ");
                }
                System.out.println();
            }
        }
         
        /*
         * 测试代码
         */
        public static void main(String[] args) {
            LinkQueue<String> lQueue =new LinkQueue<>();
            lQueue.printQueue();
            lQueue.enQueue("A");
            lQueue.enQueue("B");
            lQueue.enQueue("c");
            lQueue.enQueue("D");
            lQueue.printQueue();<br>       
            lQueue.deQueue();
            lQueue.deQueue();
            lQueue.enQueue("E");
            lQueue.printQueue();
        }
    }

**3.循环队列和链队列的选择**

基本操作时间都为**O(1)**。但链队列每次申请和释放结点会存在一点时间开销，且其需要存储一个指针域；而循环队列必须固定空间长度，存在空间浪费问题，且没链队列灵活。

综上，在可以确定队列长度最大值的情况下，建议用**循环队列**；当无法预估队列的长度时，使用**链队列**。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNjA4NTc1NjA1MC0xMzgwMDg3MzEucG5n?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNjA5MDc1MTE0Ny02MDIxODg5OTEucG5n?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNjA5MDIzNTUyNS01NDA2MTQyNDUucG5n?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNjA5MTUxNDM4MS0xMTAzMTQxODM1LnBuZw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNjA5MjQzNjg5My0xODQyMDI4ODc3LnBuZw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNjA5MjQ1ODMxOS0zNDI2OTE2MTYucG5n?x-oss-process=image/format,png