数据结构---队列及简单实现有界队列

时间:2020-04-06 白露非霜人气:0

队列也是一种特殊的线性表，它只允许在两端进行操作，插入或者取出，不允许操作中间的数据。比如只允许在对头出队，队尾入队。这样就具有先进先出的特性（first in first out-FIFO）。就像排队买东西一样，不允许插队，先排先买。

队列分为单向队列（有序队列），就是上面所说的排队模型，先进先出的操作，只允许一边进，另一边出，比如Java中的Queue。另外一种就是双端队列，两端都可以进行进出操作。比如java中的Deque。

既然队列也是线性表的一种，那么实现队列，就可以用数组或者链表来实现。

如果再细分一点的话，可以看着这俩接口的实现，简单列举几个：

PriorityQueue：数组实现的有序队列，可以传入一个比较器Comparator，实现队列中元素的顺序。。

ArrayDeque：数组实现的双端队列

LinkedList：用链表实现的双端队列

Juc并发包下面：

ArrayBlockingQueue：数组实现的阻塞队列

PriorityBlockingQueue：带优先级的阻塞队列

LinkedBlockingQueue：链表实现的阻塞队列

可以看出大佬们的命名是很规范的，从类名直接可以看出来这队列的特性以及用什么数据结构实现的。

简单用数组实现一个有界队列

1.初始化一个数组，这个是头尾都是指向的0

2.插入三个元素，尾移动三位，指向了3

3.取出一个元素，头移动一位指向了1

我们会发现头指针走过的数组元素其实是空出来了的（index = 0）。假设尾指针走到最后了，但是因为我们有取出元素，前面有空位，所以按理来说，我们还可以继续加入元素进去，但是这个时候怎么指针怎么回去呢？可以重新创建一个数组继续开始，这样的话会重新开辟内存空间，而且还需要将现有的数据复制到新的数组中去。如果我们只想让这个队列保持初始化大小，没有扩容操作，创建一个新的数组去继续放，从空间和时间复杂度来说都不合适了。这个时候我们可以通过取模操作，让指针回去，从头开始，既不用开辟新空间，也不用移动数据。这样的话就需要考虑空队列和满队这两个状态的判断。如果满了就无法插入，新数据直接丢弃，按如上逻辑实现一个简单队列。

package com.nijunyang.algorithm.queue;

/**
 * Description:
 * Created by nijunyang on 2020/4/4 21:44
 */
public class MyQueue<E> {
    private static final int DEFAULT_SIZE = 10;
    private Object[] elements;
    private int headIndex;
    private int tailIndex;
    private int capacity; //从容量
    private int size;  //已放元素个数

    public MyQueue() {
        this(DEFAULT_SIZE);
    }

    public MyQueue(int capacity) {
        this.elements = new Object[capacity];
        this.capacity = capacity;

    }

    public void push(E e){
        if (isFull()) {  //插入先判断是否满
            return;
        }
        elements[tailIndex] = e;
        size++;
        tailIndex = (tailIndex + 1) % capacity;  //取模实现循环的操作
    }

    public E pop(){
        if(isEmpty()) {  //取元素先判空
            return null;
        }
        E e = (E) elements[headIndex];
        headIndex = (headIndex + 1) % capacity; //取模实现循环的操作
        size--;
        return e;
    }

    public boolean isEmpty(){
        return this.size == 0;
    }

    public int size(){
        return this.size;
    }

    public int getCapacity(){
        return this.capacity;
    }

    public boolean isFull(){
        return this.size == this.capacity;
    }

    public static void main(String[] args) {
        MyQueue<Integer> myQueue = new MyQueue(3);
        myQueue.push(1);
        System.out.println(myQueue.size());
        myQueue.push(2);
        myQueue.push(3);
        System.out.println(myQueue.pop());
        System.out.println(myQueue.size());
        myQueue.push(4);
        myQueue.push(5);
        System.out.println(myQueue.size());

    }


}

加载全部内容