队列的两种实现方法

- 日理万妓 2023-01-08 10:30 186阅读 0赞

## 概念 ##

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出

入队列：进行插入操作的一端称为队尾  
出队列：进行删除操作的一端称为队头

#### 当head==tail时 ####

情况1：队列为空  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70]  
情况2：队列为满  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70 1]

## 用链表的方式形成队列 ##

public class MyQueueByLinkedList {
        
        //Node 这个类叫做内部类
        static class Node{
        
            public int val;
            Node next = null;
    
            public Node(int val){
        
                this.val = val;
            }
        }
    
        //创建一个链表就得有头节点  此处的head不是傀儡节点
        private Node head = null;
        private Node tail = null;
    
        //入队列
        //此处尾部入队列，头部出队列的方式实现
        public void offer(int val){
        
            Node newNode = new Node(val);
            if (head == null){
        
                head = newNode;
                tail = newNode;
                return;
            }
            //如果当前不是空链表
            tail.next = newNode;
            tail = tail.next;
        }
    
        //出队列
        public Integer poll(){
        
            if (head == null){
        
                return null;
            }
            int ret = head.val;
            head = head.next;
            if (head == null){
        
                tail = null;
            }
            return ret;
        }
    
        //取队首元素
        public Integer peek(){
        
            if (head == null){
        
                return null;
            }
            return head.val;
        }
    }

## 用数组的方式形成队列 ##

public class MyQueueByArray {
        
        private int[] array = new int[100];
        private int head = 0;
        private int tail = 0;
        private int size = 0;
    
        public void offer(int val){
        
            if (size == array.length){
        
                return;
            }
            array[tail] = val;
            tail++;
            //如果超出了有效范围，就从头开始
            if (tail > array.length){
        
                tail = 0;
            }
            size++;
        }
    
        public Integer poll(){
        
            if (size == 0){
        
                return null;
            }
            Integer ret = array[head];
            head++;
            if (head >= array.length){
        
                head = 0;
            }
            size--;
            return ret;
        }
    
        public Integer peek(){
        
            if (size == 0){
        
                return null;
            }
            return array[head];
        }
    }

## 具体实现 ##

<table> 
 <thead> 
  <tr> 
   <th>错误处理</th> 
   <th>抛出异常</th> 
   <th>返回特殊值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>入队列</td> 
   <td>add(e)</td> 
   <td>offer(e)</td> 
  </tr> 
  <tr> 
   <td>出队列</td> 
   <td>remove()</td> 
   <td>poll()</td> 
  </tr> 
  <tr> 
   <td>入队列</td> 
   <td>element()</td> 
   <td>peek()</td> 
  </tr> 
 </tbody> 
</table>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70]: /images/20221119/651df3f007354da190f916dad7dc90af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTM2MTg5_size_16_color_FFFFFF_t_70 1]: /images/20221119/dcf52d0b1d2d49ffaaa9f565d50ecd26.png