亲宝软件园·资讯

展开

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

白露非霜 人气: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());

    }


}

 

加载全部内容

相关教程
猜你喜欢
用户评论