05_队列

作者: 伶俐ll | 来源:发表于2020-10-21 08:10 被阅读0次

队列初识

  • 队列是一种特殊的线性表,只能在头尾两端进行操作
  • 队尾(rear):只能从队尾添加元素,一般叫做enQueue,入队
  • 队头(front):只能从队头移除元素,一般叫做deQueue,出队
  • 先进先出的原则,First In First Out,FIFO


    Snip20200914_24.png

队列的类型

  • 普通队列
    只能从队尾添加元素,只能从队头移除元素,先进先出,优先使用双向链表实现
  • 双端队列
    可以从两端添加或者删除元素,优先使用双向链表实现
  • 循环队列
    其实队列底层也可以使用动态数组实现,并且各项接口也可以优化到O(1)的时间复杂度,这个用数组实现并且优化之后的队列叫做循环队列
  • 循环双端队列
    可以进行两端添加、删除操作的循环队列

队列的接口设计

1. 普通队列
  • int size(){} // 元素的数量
  • boolean isEmpty(){} // 是否为空
  • void clear(){} // 清空
  • void enQueue(E element){} // 入队
  • E deQueue(){} // 出队
  • E front(){} // 获取队列的头元素
2. 双端队列
  • int size(){} // 元素的数量
  • boolean isEmpty(){} // 是否为空
  • void clear(){} // 清空
  • void enQueueRear(E element){} // 从队尾入队
  • E deQueueFront(){} // 从队头出队
  • void enQueueFront(E element){} // 从队头入队
  • E deQueueRear(){} // 从队尾出队
  • E front(){} // 获取队列的头元素
  • E rear(){} // 获取队列的尾元素

代码实现

  • 普通队列,使用双向链表实现
package Queue;

import LinkedList.LZLinkedList;

public class LZQueue<E> {
    private LZLinkedList<E> list = new LZLinkedList<>();

    /**
     * 入队
     */
    public void enQueue(E element){
        list.add(element);
    }

    /**
     * 出队
     */
    public void deQueue(){
        list.remove(0);
    }

    /**
     * 获取队列的头元素
     */
    public E front(){
       return list.get(0);
    }

    /**
     * 清空
     */
    public void clear(){
        list.clear();
    }

    /**
     * 获取队列的长度
     */
    public int size(){
        return list.size();
    }

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public String toString(){
        return list.toString();
    }
}
  • 双端队列,使用双向链表
package Queue;

import LinkedList.LZLinkedList;

public class LZQueue2<E> {
    private LZLinkedList<E> list = new LZLinkedList<>();

    /**
     * 从队尾入队
     */
    public void enQueueRear(E element){
        list.add(element);
    }

    /**
     * 从队头出队
     */
    public void deQueueFront(){
        list.remove(0);
    }

    /**
     * 从队头入队
     */
    public void enQueueFront(E element){
        list.add(0,element);
    }

    /**
     * 从队尾出队
     */
    public void deQueueRear(){
        list.remove(list.size()-1);
    }


    /**
     * 获取队列的头元素
     */
    public E front(){
        return list.get(0);
    }

    /**
     * 获取队列的尾元素
     */
    public E rear(){
        return list.get(list.size()-1);
    }

    /**
     * 清空
     */
    public void clear(){
        list.clear();
    }

    /**
     * 获取队列的长度
     */
    public int size(){
        return list.size();
    }

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public String toString(){
        return list.toString();
    }
}

  • 循环队列
package Queue;

public class LZCircleQueue <E>{

    /**
     * 元素的数量
     */
    private int size;
    /**
     * 第一个元素的下标
     */
    private int front;

    /**
     * 所有的元素
     */
    private  E[] elements;

    private  static final int DEFAULT_CAPACITY = 5;

    /**
     * 构造函数
     */
    public LZCircleQueue(){
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    /**
     * 入队
     * @param element
     */
    public void enQueue(E element){
        if (elements.length<(size + 1)){
            ensureCapacity();
        }

        int index = index(size);
        elements[index] = element;
        size ++;
    }

    /**
     * 出队
     * @param
     * @return
     */
    public void deQueue(){
        elements[front] = null;
        front = index(1);
        size--;
    }

    /**
     * 获取队列的头元素
     */
    public E front(){
        return elements[front];
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        for (int i = 0;i<size;i++){
            elements[index(i)] = null;
        }
        front = 0;
        size = 0;
    }

    /**
     * 元素的数量
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return  size == 0;
    }

    /**
     * 扩容
     */
    private void ensureCapacity(){
        int oldCapacity = elements.length;
        int newCapacity = oldCapacity + (oldCapacity>>1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0;i<size;i++){
            newElements[i] = elements[index(i)];
        }
        elements = newElements;
        //重置front
        front = 0;
    }

    private int index(int index){
        index += front;
        return index - (index>= elements.length?elements.length:0);
//        return (front + index) % elements.length;
    }

    @Override
    public String toString(){
        StringBuffer string = new StringBuffer();
        string.append("size = ").append(size).append("\n[");
        for (int i = 0;i< elements.length;i++){
            if (i != 0){
                string.append(", ");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }

}

  • 循环双端队列
package Queue;

public class LZCircleQueue2 <E>{

    /**
     * 元素的数量
     */
    private int size;
    /**
     * 第一个元素的下标
     */
    private int front;

    /**
     * 所有的元素
     */
    private  E[] elements;

    private  static final int DEFAULT_CAPACITY = 5;

    /**
     * 构造函数
     */
    public LZCircleQueue2(){
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    /**
     * 从队尾入队
     * @param element
     */
    public void enQueueRear(E element){
        if (elements.length<(size + 1)){
            ensureCapacity();
        }

        elements[index(size)] = element;
        size ++;
    }

    /**
     * 从队头出队
     * @param
     * @return
     */
    public void deQueueFront(){
        elements[front] = null;
        front = index(1);
        size--;
    }

    /**
     * 从队头入队
     * @param
     * @return
     */
    public void enQueueFront(E element){
        if (elements.length<(size + 1)){
            ensureCapacity();
        }

        front = index(-1);
        elements[front] = element;
        size ++;
    }

    /**
     * 从队尾出队
     * @param
     * @return
     */
    public void deQueueRear(){
        int index = index(size-1);
        elements[index] = null;
        size --;
    }

    /**
     * 获取队列的头元素
     */
    public E front(){
        return elements[front];
    }

    /**
     * 获取队列的尾元素
     */
    public E rear(){
        return elements[index(size-1)];
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        for (int i = 0;i<size;i++){
            elements[index(i)] = null;
        }
        front = 0;
        size = 0;
    }

    /**
     * 元素的数量
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return  size == 0;
    }

    /**
     * 扩容
     */
    private void ensureCapacity(){
        int oldCapacity = elements.length;
        int newCapacity = oldCapacity + (oldCapacity>>1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0;i<size;i++){
            newElements[i] = elements[index(i)];
        }
        elements = newElements;
        //重置front
        front = 0;
    }

    private int index(int index){
        index += front;
        if (index<0){
            return index + elements.length;
        }
        return index - (index>= elements.length?elements.length:0);
//        return (front + index) % elements.length;
    }

    @Override
    public String toString(){
        StringBuffer string = new StringBuffer();
        string.append("size = ").append(size).append("\n[");
        for (int i = 0;i< elements.length;i++){
            if (i != 0){
                string.append(", ");
            }
            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }

}

复杂度

时间复杂度都是O(1)级别

相关文章

  • 05_队列

    队列初识 队列是一种特殊的线性表,只能在头尾两端进行操作 队尾(rear):只能从队尾添加元素,一般叫做enQue...

  • 05_解密 QQ 号_队列

    新学期开始了,小哈是小哼的新同桌(小哈是个小美女哦~),小哼向小哈询问 QQ 号,小哈当然不会直接告诉小哼啦,原因...

  • 第02天(函数、工程管理)_知识点图片

    01_普通函数调用流程 02_递归函数的调用流程 03_递归实现累加 04_工程管理 05_工程管理

  • 05_两个栈实现一个队列【python】

    1.题目描述 题目一:用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。题目二:...

  • 《另一个天堂》_目录

    第一章 01_欧青(序) 02_那个女孩(一) 03_那个女孩(二) 04_ 05_ 06_ 07_ 08_

  • 第04天(面对对象编程)_02

    05_结构体指针类型匿名字段.go 06_面向过程和对象函数的区别.go 07_为结构体类型添加方法.go 08_...

  • 队列

    队列特性 对比队列和栈 基于数组的队列 对比队列学习循环队列 循环队列难点 阻塞队列 并发队列 应用:线程池中拒绝...

  • 队列

    文章结构 什么是队列 实现队列顺序队列链式队列循环队列 Java中的队列 1. 什么是队列 队列也是一种操作受限的...

  • iOS底层-- GCD源码分析(1)-- dispatch_qu

    手动目录认识队列队列的结构队列的产生主队列全局队列创建的队列管理队列 代码版本dispatch version :...

  • 队列,异步,同步,线程通俗理解

    一、队列 串行队列 并行队列 主队列(只在主线程执行的串行队列) 全局队列(系统的并行队列) 二、 任务(是否具有...

网友评论

      本文标题:05_队列

      本文链接:https://www.haomeiwen.com/subject/yfdzektx.html