如何实现一个双端队列 - 数据库敲门人

Contents

1 零双端队列性质
2 一实现思路
3 二代码实现

零双端队列性质

见名知意，就是可以在队首、队尾分别执行入队、出队操作的一种队列。

一实现思路

参照用数组实现队列的思路，我们就完全可以实现一个双端队列。因为，我们底层的动态数组已经实现了addFirst()/addLast()，removeFirst()/removeLast()，getFirst()/getLast()的方法。因此，我们双端队列如果需要在队首、队尾分别出队，入队的操作，我们只需要调用底层数据的对应方法就可以。另外，查看队首、队尾元素值，我们调用底层数组的getFirst()/getLast()方法即可。

二代码实现

/**
 * @Author:asher
 * @Date:2021/4/12 14:41
 * @Description:PACKAGE_NAME
 * @Version:1.0
 */
public class Deque<E> implements Queue<E> {
    private Array<E> array;

    public Deque(int capacity) {
        array = new Array<>(capacity);
    }

    public Deque() {
        this(10);
    }

    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    //队首入队，双端队列新添加的方法
    public void enqueueFirst(E e) {
        array.addFirst(e);
    }

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    //队尾出队，双端队列新加的方法
    public E dequeueLast() {
        return array.removeLast();
    }

    @Override
    public E getFront() {
        return array.getFirst();
    }

    //查看队尾元素，双端队列新加的
    public E getLast() {
        return array.getLast();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("Dequeue size: %d , length: %d\n", array.getSize(),array.getCapacity()));
        stringBuilder.append("Dequeue: head[");
        for (int i = 0; i < getSize(); i++) {
            stringBuilder.append(array.get(i));
            if (i != getSize()-1) {
                stringBuilder.append(" , ");
            }
        }
        stringBuilder.append("] tail");
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        Deque deque=new Deque(5);
        System.out.println(deque);
      //队尾入队元素2
        deque.enqueue(2);
        System.out.println(deque);
      //队首入队元素1
        deque.enqueueFirst(1);
        System.out.println(deque);
      //队首继续入队元素0
        deque.enqueueFirst(0);
      //队尾入队元素3
        deque.enqueue(3);

        System.out.println(deque);
      //队首出队
        System.out.println(deque.dequeue());
        System.out.println(deque);
      //队尾出队
        System.out.println(deque.dequeueLast());
        System.out.println(deque);
    }
}
//结果：
Dequeue size: 0 , length: 5
Dequeue: head[] tail
Dequeue size: 1 , length: 5
Dequeue: head[2] tail
Dequeue size: 2 , length: 5
Dequeue: head[1 , 2] tail
Dequeue size: 4 , length: 5
Dequeue: head[0 , 1 , 2 , 3] tail
0
Dequeue size: 3 , length: 5
Dequeue: head[1 , 2 , 3] tail
3
Dequeue size: 2 , length: 2
Dequeue: head[1 , 2] tail

说明：这个Dequeue的类，使我们自己通过动态数组实现的一个双端队列。JDK自带也有一个Deque接口。同时，我们的Dequeue也同样实现了前面我们自己定义的Queue那个接口。并且，添加了自己固有的在队尾出队dequeueLast()、队首添加元素的方法enqueueFirst()。

Post Views: 1,811