数据结构第二谈：数组模拟队列、数组模拟环形队列

╰+攻爆jí腚メ 2023-01-03 11:30 188阅读 0赞

### 文章目录 ###

*   *  1、数组模拟队列
     *  2、数组模拟环形队列

## 1、数组模拟队列 ##

> 队列是一个有序列表，可以用数组或是链表来实现。 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出 示意图：(使用数组模拟队列示意图)

![image.png][]

*  队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
 *  因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:
 *  ![image.png][image.png 1]

**代码**：

/** * 使用数组模拟队列 */
    class ArrayQueue { 
    
        private int maxSize;//队列的最大容量
        private int[] queue;
        private int top = -1;//表示队列头当前的指针
        private int front = 0;//表示尾指针
    
        public ArrayQueue(int size) { 
            this.maxSize = size;
            queue = new int[this.maxSize];
        }
    
        /** * 入队列 */
        public void addQueue(int num) { 
            if (isFull()) throw new RuntimeException("队列满");
            queue[front++] = num;
        }
    
        /** * 出队列 */
        public int getNum() { 
            if (isEmpty()) throw new RuntimeException("队列空");
            return queue[++top];
        }
    
        /** * 判空 */
        public boolean isEmpty() { 
            if (top == front - 1) return true;
            else return false;
        }
    
        /** * 判满 * * @return */
        public boolean isFull() { 
            if (front == maxSize - 1) return true;
            else return false;
        }
    
        /** * 返回当前队列中元素个数 * * @return */
        public int getSize() { 
            return front - top - 1;
        }
    }

## 2、数组模拟环形队列 ##

> 对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)

![image.png][image.png 2]

思路：

1.  front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr\[front\] 就是队列的第一个元素 front 的初始值 = 0
2.  rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定. rear 的初始值 = 0
3.  当队列满时，条件是 (rear + 1) % maxSize == front 【满】
4.  对队列为空的条件， rear == front 空
5.  当我们这样分析， 队列中有效的数据的个数 (rear + maxSize - front) % maxSize // rear = 1 front = 0
6.  我们就可以在原来的队列上修改得到，一个环形队列

/** * 使用数组模拟环形队列 */
    class RingQueue { 
        private int maxSize;//队列容量
        private int front = 0;//头指针
        private int rear = 0;
        private int[] arr;
    
        public RingQueue(int size) { 
            this.maxSize = size;
            arr = new int[maxSize];
        }
    
        /** * 入队列 */
        public void add(int num) { 
            if (isFull()) throw new RuntimeException("队列满");
            arr[rear] = num;
            rear = (rear + 1) % maxSize;
        }
    
        /** * 出队列 */
        public int get() { 
            if (isEmpty()) throw new RuntimeException("队列空");
            int temp = arr[front];
            front = (front + 1) % maxSize;
            return temp;
        }
    
        /** * 判空 * * @return */
        public boolean isEmpty() { 
            if (rear == front) return true;
            else return false;
        }
    
        /** * 判满 * * @return */
        public boolean isFull() { 
            if ((rear + 1) % maxSize == front) return true;
            else return false;
        }
    
        /** * 返回队列长度 */
        public int getLenth() { 
            return (rear - front + maxSize) % maxSize;
        }
    }

[image.png]: /images/20221119/04a02477f8924895acc71745e7c390f7.png
[image.png 1]: /images/20221119/3aeb9cf832904a2eaf6cab3647c79c0b.png
[image.png 2]: /images/20221119/bfb250dadab041248df1822294dd2274.png