【数据结构与算法】队列-模拟实现队列以及设计循环队列

曾经终败给现在 2023-09-27 14:05 137阅读 0赞

#### 文章目录 ####

*  队列的概念
 *  链表实现栈
 *  设计循环队列
 *  总结

## 队列的概念 ##

> 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。  
> 队列是一种先进先出的数据结构,注意和栈进行区分,不要记混.

队列的实现有链式结构和顺序结构,接下来会使用链表和数组分别实现队列

队列中的方法有以下这些:

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>offer(E e)</td> 
   <td>入队列</td> 
  </tr> 
  <tr> 
   <td>poll()</td> 
   <td>出队列</td> 
  </tr> 
  <tr> 
   <td>peek()</td> 
   <td>获取队头元素</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>获取队列中有效元素个数</td> 
  </tr> 
  <tr> 
   <td>boolean isEmpty()</td> 
   <td>检测队列是否为空</td> 
  </tr> 
 </tbody> 
</table>

接下来来实现这些功能

## 链表实现栈 ##

链表实现栈有以下点需要注意:

*  入队只能在队尾增加元素,可以遍历到最后一个元素,再进行增加元素 但每次入队都要进行遍历,就会很慢,为了解决这个问题,可以用tail记录下来最后一个元素,这样入队时,直接用tail就可以了
 *  在出队时要注意空指针异常,也就是当前队列为空的情况 我这里解决的方法是使用自定义异常也可以使用别的方法来解决
 *  除了空队列的这种情况,还要考虑只有一个元素的情况,如果入队的元素是第一个,要将head和tail同时指向要入队的结点. 如果当前队列只有一个元素,进行出队时,要将head和tail都置为null

代码如下:

public class MyQueue extends MyNullException{
        
        static class Node{
        
            public int val;
            public Node next;
    
            public Node(int val) {
        
                this.val = val;
            }
        }
    
        public Node head;
        public Node tail;
    
        /**
         * 入队
         * add与offer的区别
         * @param val
         */
        public void offer(int val){
        
            Node node = new Node(val);
            if (isEmpty()){
        
                head = node;
                tail = node;
            }else {
        
                tail.next = node;
                tail = tail.next;
            }
        }
    
        /**
         * 出队
         * @return
         */
        public int poll(){
        
            if (isEmpty()){
        
                throw new MyNullException("当前队列为空,出队失败!");
            }
            int ret = head.val;
            if (head.next == null){
        
                head = null;
                tail = null;
            }else {
        
                head = head.next;
            }
            return ret;
        }
    
        /**
         * 查看队头元素
         * @return
         */
        public int peek(){
        
            if (isEmpty()){
        
                throw new MyNullException("当前队列为空,查看失败!");
            }
            return head.val;
        }
    
        public boolean isEmpty(){
        
            return head == null;
        }
    
        public int size(){
        
            int ret = 0;
            Node cur = head;
            while (cur != null){
        
                ret++;
                cur = cur.next;
            }
            return ret;
        }
    }

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

## 设计循环队列 ##

接下来用数组来实现队列,用数组来实现队列注意是采用循环队列这种方式  
![在这里插入图片描述][18cb7ca3b4b14d28996ab80c149e71d9.png]  
一般情况下,这样实现队列会有什么问题,首先队列出队是从队头出元素,队尾新增元素,出队时只需要front往前走一步,入队只需要让数组的rear下标设置为要增加元素的值,再让rear往后走一步就行,但是数组的长度是有限的,`如果当前数组满了,就需要进行扩容,但之前如果频繁出队会造成数组的前面空间大量的浪费`.  
因此为了解决这个问题,推荐使用数组设计一个循环队列,`循环队列最大的特点就是 front 可以不从0下标开始放数据,而rear也可以在队列不满的情况下,即使到了数组的最后一个元素,可以接着从0下标开始存放数据`  
看下图:  
![在这里插入图片描述][a2aa4f76838e4d199c50c7a640f56529.png]  
上图可知:front是从1下标开始存放元素的,如果此时rear下标是9,在入队一个元素,`如何让9到0下标呢?`此时就不能只让rear自增1了,而要让rear+1后进行取余

> 入队时: rear = (rear+1) % 数组长度;  
> 出队时: front = (front+1) % 数组长度;

那么接下来要考虑一个问题,`什么时候这个队列是满的?front等于rear?`  
front等于rear也可能是空队列,为了解决这个问题,有两种方法:

1.  `使用计数器,将数组中元素的有效个数记录下来`
2.  `浪费一个空间,也就是当 (rear+1) % 数组长度== front 时为队列满这种情况`

代码如下:

public class MyCircularQueue{
        
        public int[] elem;
        public int usedSize;// 有效个数
        public int front;
        public int rear;
    
        public MyCircularQueue(int k){
        
            this.elem = new int[k+1];
        }
    
        /**
         * 入队
         * 如果需要扩容,就需要考虑从哪里开始拷贝
         * @param val
         * @return
         */
        public boolean enQueue(int val){
        
            if (!isFull()){
        
                elem[rear] = val;
                rear = (rear+1) % elem.length;
                // usedSize++;
                return true;
            }else{
        
                return false;
            }
        }
    
        /**
         * 出队
         * @return
         */
        public boolean deQueue(){
        
            if (isEmpty()){
        
                return false;
            }else {
        
                front = (front+1) % elem.length;
                // usedSize--;
                return true;
            }
        }
    
        /**
         * 获取队头元素
         * @return
         */
        public int Front(){
        
            if (isEmpty()){
        
                return -1;
            }else {
        
                return elem[front];
            }
        }
    
        /**
         * 获取队尾元素
         * 注意下标: 0和elem.length的时候
         * @return
         */
        public int Rear(){
        
            if (isEmpty()){
        
                return -1;
            }
            return (rear == 0) ? elem[elem.length-1] : elem[rear-1];
        }
        /**
         * 判断当前队列是否满了
         * @return
         */
        public boolean isFull(){
        
            /*if (usedSize == elem.length){
                return true;
            }
            return false;*/
    
            return (rear+1) % elem.length == front;
        }
    
        /**
         * 判断队列是否为空
         * @return
         */
        public boolean isEmpty(){
        
            /*if (usedSize == 0){
                return true;
            }
            return false;*/
    
            return rear == front;
        }
    }

## 总结 ##

*  队列是先进先出的数据结构,不要和栈记混淆了.
 *  掌握链表实现栈,以及循环队列的原理
 *  熟悉循环队列中什么情况下队列满了 出队和入队时 front和rear 怎么进行调整

![在这里插入图片描述][9a80c15f5dba421981ac46cc9878685f.png_pic_center]

[18cb7ca3b4b14d28996ab80c149e71d9.png]: https://img-blog.csdnimg.cn/18cb7ca3b4b14d28996ab80c149e71d9.png
[a2aa4f76838e4d199c50c7a640f56529.png]: https://img-blog.csdnimg.cn/a2aa4f76838e4d199c50c7a640f56529.png
[9a80c15f5dba421981ac46cc9878685f.png_pic_center]: https://img-blog.csdnimg.cn/9a80c15f5dba421981ac46cc9878685f.png#pic_center