数据结构与算法—双端队列的实现

• 接口
• 代码

接口

Dequeue接口

package p1.接口;

public interface Dequeue<E> extends Queue<E> {
    public void addFirst(E element);
    public void addLast(E element);
    public E removeFirst();
    public E reomveLast();
    public E getFirst();
    public E getLast();
}

Queue接口

package p1.接口;
/**
 * @Auther: wjw
 * @Date: 2022/1/14-01-14-17:42
 * @Description: p2.线性结构
 * @version: 1.0
 */

public interface Queue<E> extends Iterable<E> {
    public void offer(E element);   //入队
    public E poll();    //出队
    public E element();    //查看队首元素
    public boolean isEmpty();
    public void clear();
    public int size();
}

代码

package p3.实例应用;

import p1.接口.Dequeue;
import p1.接口.Stack;

import java.util.Iterator;


/**
 * @Auther: wjw
 * @Date: 2022/1/14-01-14-16:43
 * @Description: p3.实例应用
 * @version: 1.0
 */
//双端队列要具有队列与栈的功能
public class ArrayDeque<E> implements Dequeue<E>, Stack<E>{
    //所需变量
    private E[] data;
    private int front;//头指针
    private int rear;//尾指针
    private int size;//有效元素个数
    private static int DEFAULT_CAPACITY = 10;

    //构造函数
    public ArrayDeque() {
        data = (E[]) new Object[DEFAULT_CAPACITY + 1];
        front = 0;
        rear = 0;
        size = 0;
    }
    //添加元素有俩中 队尾和队首
    //队首
    @Override
    //front要向前移 font要减1
    public void addFirst(E element) {

        if ((rear + 1) % data.length == front) {
            resize(data.length * 2 - 1);
        }
        //font要向前移 font要减1 然后front就要到最后
        front = (front - 1 + data.length) % data.length;
        //移动完后data为
        data[front] = element;
        size++;
    }
    //扩容
    //与循环对列的一样所以就直接复制了
    private void resize(int newLen) {
        E[] newData = (E[]) new Object[newLen];
        int index = 0;
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            newData[index++] = data[i];
        }
        data = newData;
        front = 0;
        rear = index;
    }

    //队尾添加
    @Override
    public void addLast(E element) {
        //判断是否要扩容
        //如果角标满了就扩容
        if ((rear + 1) % data.length == front) {
            resize(data.length * 2 - 1);
        }
        //元素先进尾部，然后尾部向后移
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
    }
    //删队首
    @Override
    public E removeFirst() {
        //第一步判断是否为空
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        //直接取front对应元素 然后删除
        E ret = data[front];

        front = (front + 1) % data.length;
        size--;
        //判断是否要缩容
        if (size <= (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY) {
            resize(data.length / 2 + 1);
        }
        return null;
    }
    //删队尾
    @Override
    public E reomveLast() {
        //第一步判断是否为空
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        //先让rear向前移，再把那个元素删掉 最后对长度取余
        rear = (rear - 1 + data.length) % data.length;
        //往前移后把所要删除的元素取出
        E ret = data[rear];
        size--;
        //判断缩容
        if (size <= (data.length - 1) / 4 && data.length - 1 > DEFAULT_CAPACITY) {
            resize(data.length / 2 + 1);
        }
        return ret;
    }

    @Override
    public E getFirst() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        //如果不是空 返回元素
        return data[front];
    }

    @Override
    public E getLast() {
        if (isEmpty()) {
            throw new IllegalArgumentException("queue is null");
        }
        //如果不是返回元素 就是(rear - 1 + data.length) % data.length
        //就得到最后元素的角标
        return data[(rear - 1 + data.length) % data.length];
    }
    //入队的操作就是addLast(element);添加到表尾
    @Override
    public void offer(E element) {
        addLast(element);
    }
    //出队的操作，删除表头
    @Override
    public E poll() {
        return removeFirst();
    }
    //查看队首元素
    @Override
    public E element() {
        return getFirst();
    }
    //查看表头
    @Override
    public E peek() {
        return getLast();
    }
    //判空就是判断size是否为空并且front==rear
    @Override
    public boolean isEmpty() {
        return size == 0 && front == rear;
    }

    @Override
    public void push(E element) {
        addLast(element);
    }

    @Override
    public E pop() {
        return reomveLast();
    }
    //清空
    @Override
    public void clear() {
        E[] data = (E[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        rear = 0;
        size = 0;
    }
    //size 就返回size
    @Override
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()) {
            sb.append(']');
            return sb.toString();
        }
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            sb.append(data[i]);
            if ((i + 1) % data.length == rear) {
                sb.append(']');
            } else {
                sb.append(',');
                sb.append(' ');
            }
        }
        return sb.toString();
    }

    @Override
    public Iterator<E> iterator() {
        return new ArrayDequeIterator();
    }

    class ArrayDequeIterator implements Iterator<E> {
        private int cur = front;

        @Override
        public boolean hasNext() {
            return cur != rear;
        }

        @Override
        public E next() {
            E ret = data[cur];
            cur = (cur + 1) % data.length;
            return ret;
        }
    }

}