深入理解数据结构（2）——用数组实现队列

╰半橙微兮° 2024-02-20 09:20 31阅读 0赞

> 数组是一种数据结构，队列也是一种数据结构。它们都是由基础的语法实现的。
> 
> 如果一个数据结构可以用另外的数据结构来实现，那么可以有力的证明——“数据结构是一种思想”，是一种讲语法组合起来实现某种功能的手段
> 
> “整体大于局部”

## 一、队列的特点——要实现哪些功能？ ##

> 从尾进，从头出

对于数组来说，每次从尾部插入元素，从头部删除元素。当数组后端插满元素的时候，此时前端删除元素就会导致——数组前端因为删除元素变空，后部因插入元素变满。如何解决这个问题？

我们可以设想有这样一个环形数组——刚开始两只指针front和rear都在0下标。每放入一个元素，rear就会往后走一步；每从队头front处出一个元素，front就会往后走一步（但是移除数据会导致前面位置有空缺）。如果rear移到最后一位是，再插入元素，rear就会移到数组的0下标处。这样问题就得到解决。

![ee2e5ed8945644bc9882ff4acb83aeec.png][]

![965e5c39f43844e68d32a535421bc531.png][]

![6ac8374f03f74f4d82e25028029f2e92.png][]

这里有两个问题：1、rear从7下标到0下标怎么过去？2、如何判断此事是空还是满？

问题1：不要用rear++，因为无法处理7下标到0下标的问题，用——rear = (rear + 1) % length

问题2：rear下一位是front，说明是满的。如果rear和front的下标是相同的，说明是空的

## 二、代码实现 ##

class MyCircularQueue {
    
        private int[] elem;
        private int front;//表示队列的头
        private int rear;//表示队列的尾
    
        public MyCircularQueue(int k) {
    /*这里创建数组时要多用一个空间，如果想要放置7个元素的话，在放第6个元素的时候，rear在最后一
    *个下标处，他后面就是front。如果此时放入第7个元素，会被判定为“满”。所以要多要一个空间
    */
            this.elem = new int[k+1];
        }
    
        /**
         * 入队列     
         */
        public boolean enQueue(int value) {
            //1、检查是否队列是满的
            if(isFull()){
                return false;
            }
            
            elem[rear] = value;
            rear = (rear+1) % elem.length;
            return true;
        }
    
        /**
         * 出队列
         */
        public boolean deQueue() {
            if(isEmpty()) {
                return false;
            }
            //front++;
            front = (front+1) % elem.length;
            return true;
        }
    
        /**
         * 得到队头元素
         */
        public int Front() {
            if(isEmpty()) {
                return -1;
            }
            return elem[front];
        }
    
        /**
         * 得到队尾元素
         */
        public int Rear() {
            if(isEmpty()) {
                return -1;
            }
            //return (rear-1);  不可以这样写，因为当rear在0下标时会为-1
            int index = (rear == 0) ? elem.length-1 : rear-1;
            return elem[index];
        }
    
        public boolean isEmpty() {
            return front == rear;
        }
    
        /**
         * 队列是否为满
         */
        public boolean isFull() {
            //如果real的下一位是front，则说明是满的
           /* if( (rear+1) % elem.length == front) {
                return true;
            }
            return false;*/
            return (rear+1) % elem.length == front;
        }
    }

[ee2e5ed8945644bc9882ff4acb83aeec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/2e09b1a34cc7483891669aadea4dc3e0.png
[965e5c39f43844e68d32a535421bc531.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/e4fb09744c8a4644b4667ca4912dea55.png
[6ac8374f03f74f4d82e25028029f2e92.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/2e6bef2d0a8c472eaae506a76955cf93.png