数据结构--队列

队列：

• 定义：只能在不同端进行插入或删除操作的线性表（受限的线性表）
• 特点：先进先出（每次进队的元素作为新队尾元素，每次出队的元素只能是队头的元素）
• 队列的实现：
  • 数组
  • 链表
• 普通数组队列创建后空间固定，后期扩容效率低，改成循环队列后，可以重复利用出队后滞留的空间。

---

普通数组队列（非循环队列）

public class SqQueue<T> {
    int maxCap;//最大容量
    T[] data;//存放数据
    public int rear;//队尾指针
    public int front;//队头指针

    /**
    * 初始化队列
    */

    public SqQueue() {
        this.maxCap=10;//空参实例化队列最大容量为10
        data= (T[]) new Object[maxCap];
        rear=0;
        front=0;
    }

    public SqQueue(int cap) {
        this.maxCap=cap;
        data= (T[]) new Object[cap];
        rear=0;
        front=0;
    }

    /**
    * 扩容（每次扩容为原来的1.5倍）
    */
    private void expandCap(){
        T[] newArr= (T[]) new Object[(int) (data.length*1.5)];
        for (int i = 0; i < data.length; i++) {
            newArr[i]=data[i];
        }
        this.data=newArr;
        this.maxCap=newArr.length;
    }

    /**
    * 队空
    * @return
    */
    public boolean isEmpty(){
        return front==rear;
    }

    /**
    * 队满
    * @return
    */
    public boolean isFill(){
        return rear==maxCap;
    }

    /**
    * 入队
    * @param data
    */
    public void add(T data){
        if (isFill()){
            expandCap();
        }
        this.data[rear]=data;
        rear++;
    }

    /**
    * 出队
    * @return
    */
    public T poll(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        T data=this.data[front];
        front++;
        return data;
    }

    /**
    * 取队头元素
    * @return
    */
    public T peek(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        return data[front];
    }

    /**
    * 获取队列元素个数
    * @return
    */
    public int getSize(){
        return rear-front;
    }

}

---

链队（单链表实现）

public class LinkQueue<T> {

    static class QueNode<T> {
        T data;
        QueNode next;

        public QueNode() {
            this.data = null;
            this.next=null;
        }

        public QueNode(T data) {
            this.data = data;
            this.next=null;
        }
    }

    QueNode front;
    QueNode rear;

    public LinkQueue() {
        this.front = null;
        this.rear = null;
    }

    /**
    * 队空
    *
    * @return
    */
    public boolean isEmpty() {
        return front == null;
    }

    /**
    * 入队
    *
    * @param data
    */
    public void add(T data) {
        QueNode<T> node = new QueNode<>(data);
        if (isEmpty()) {
            front = rear = node;
        } else {
            rear.next = node;
            rear = node;
        }
    }

    /**
    * 出队
    * @return
    */
    public T poll() {
        T t;
        //原链队空
        if (isEmpty()) {
            throw new IllegalArgumentException("队空");
        }
        //原链队只有一个结点
        if (front == rear) {
            //取首结点值
            t = (T) front.data;
            //置为空
            front = rear = null;
        } else {              //原链队有多个结点
            //取首结点值
            t = (T) front.data;
            //front指向下一个结点
            front = front.next;
        }
        return t;
    }

    /**
    * 返回队头元素
    *
    * @return
    */
    public T peek() {
        if (isEmpty())
            throw new IllegalArgumentException("队空");
        T t=(T)front.data;		//取首结点值
        return t;
    }

    /**
    * 遍历队列元素
    */
    public void listQue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        QueNode<T> temp = front;
        while (temp!=null){
            System.out.print(temp.data+"\t");
            temp=temp.next;
        }
        System.out.println();
    }

    /**
    * 获取队列元素个数
    * @return
    */
    public int getSize(){
        QueNode<T> temp = front;
        int count=0;
        while (temp!=null){
            count++;
            temp=temp.next;
        }
        return count;
    }
}

---

循环顺序队（循环队列）

1. 循环队列定义：

   public class CSqQueueClass<E>{  
       int maxSize;
       private E [] data;//存放数据
       private int front,rear;	//头尾指针	
       public CSqQueueClass(){  
           maxSize=10;
           data = (E[])new Object[maxSize];
           front=0;
           rear=0;
       }
       public CSqQueueClass(int cap){  
           maxSize=cap;
           data = (E[])new Object[cap];
           front=0;
           rear=0;
       }
   
       /**
       * 队空
       * @return
       */
       public boolean isEmpty(){
           return front==rear;
       }
   
       /**
       * 入队
       * @param data
       */
       public void push(E e){ 
           if ((rear+1)%MaxSize==front){//队满，空一个位置标志队满，如果不空位置，当队满时尾指针会跳回前面，如果恰好和队头指针重合的话，无法区分是满了还是为空（判断条件一样了） 
               throw new IllegalArgumentException("队满");
           }		
           data[rear]=e;
           rear=(rear+1)%MaxSize;
       }
   
       /**
       * 出队
       * @return
       */
       public E pop(){  
           if (empty()){//队空
               throw new IllegalArgumentException("队空");
           }				
           E temp = (E)data[front];
           front=(front+1)%MaxSize;
           return temp;
       } 
   
       /**
       * 取队头元素
       * @return
       */
       public E peek(){  
           if (empty()){//队空
               throw new IllegalArgumentException("队空");
           }		
           return (E)data[front];
       }
   
       /**
       * 获取队列元素个数
       * @return
       */
       public int getSize() {
           return (rear - front+ maxSize ) % maxSize;
       }
   
       /**
       * 遍历队列元素
       */
       public void show() {
           if (isEmpty()) {
               throw new RuntimeException("队列为空");
           }
           for (int i = front; i < front + getSize(); i++) {
               System.out.printf(data[i % maxSize]);
           }
       }
   }

---

Java 队列

1. ArrayDeque

继承关系：

• Iterator 接口
  • Collection接口
    • Queue接口
      • Deque接口：双端队列（两端都可插入删除）
        • ArrayDeque 类

特点：ArrayDeque作为可变的数组双端队列，不允许插入null，线程不安全，作为栈使用时比 Stack 类效率要高，作为队列使用时比 LinkedList 要快

常用方法：

1. 添加元素

   addFirst(E e)在数组前面添加元素

   addLast(E e)在数组后面添加元素

   offerFirst(E e) 在数组前面添加元素，并返回是否添加成功

   offerLast(E e) 在数组后天添加元素，并返回是否添加成功

2. 删除元素

   removeFirst()删除第一个元素，并返回删除元素的值,如果元素为null，将抛出异常

   pollFirst()删除第一个元素，并返回删除元素的值，如果元素为null，将返回null

   removeLast()删除最后一个元素，并返回删除元素的值，如果为null，将抛出异常

   pollLast()删除最后一个元素，并返回删除元素的值，如果为null，将返回null

   removeFirstOccurrence(Object o) 删除第一次出现的指定元素

   removeLastOccurrence(Object o) 删除最后一次出现的指定元素

3. 获取元素

   getFirst() 获取第一个元素,如果没有将抛出异常

   getLast() 获取最后一个元素，如果没有将抛出异常

4. 队列操作

   add(E e) 在队列尾部添加一个元素

   offer(E e) 在队列尾部添加一个元素，并返回是否成功

   remove() 删除队列中第一个元素，并返回该元素的值，如果元素为null，将抛出异常(其实底层调用removeFirst())

   poll() 删除队列中第一个元素，并返回该元素的值,如果元素为null，将返回null(其实调用的是pollFirst())

   element() 获取第一个元素，如果没有将抛出异常peek() 获取第一个元素，如果返回null

5. 栈操作

   push(E e) 栈顶添加一个元素

   pop(E e) 移除栈顶元素,如果栈顶没有元素将抛出异常

6. 其他

   size() 获取队列中元素个数

   isEmpty() 判断队列是否为空

   iterator() 迭代器，从前向后迭代

   descendingIterator() 迭代器，从后向前迭代

   contain(Object o) 判断队列中是否存在该元素

   toArray() 转成数组

   clear() 清空队列

   clone() 克隆(复制)一个新的队列

7. LinkedList：可做普通链表队列使用（单端）

---

• 本文作者： zzr
• 本文链接： http://zzruei.github.io/2023/0264331bef.html
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！