3_栈和队列.md

栈和队列

栈

栈的实现

• 栈的基本功能：

public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

• 基于动态数组的栈的实现

public class ArrayStack<E> implements Stack<E>{
    Array<E> array;

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

    public ArrayStack(){
        array=new Array<>();
    }

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

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

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

    @Override
    public E pop() {
        return array.removeLast();
    }

    @Override
    public E peek() {
        E ele=array.get(array.getSize()-1);
        return ele;
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public String toString() {
        StringBuilder ret=new StringBuilder();
        ret.append("Stack: ");
        ret.append("[");
        for(int i=0;i<array.getSize();i++){
            ret.append(array.get(i));
            if(i!=array.getSize()-1){
                ret.append(", ");
            }
        }
        ret.append("] top");
        return ret.toString();
    }
}

时间复杂度分析

操作	时间复杂度
push(E)	均摊时间复杂度：O(1)
pop()	均摊时间复杂度：O(1)
peek()	O(1)
getSize()	O(1)
isEmpty()	O(1)

队列

• 队列是一种线性结构

• 相比数组，队列对应的操作是数组的子集

• 只能从一端(队尾)添加元素，只能从另一端(队首)取出元素

队列的基本功能

public interface Queue<E> {
    void enqueue(E e);
    E dequeue();
    E getFront();
    int getSize();
    boolean isEmpty();
}

数组队列

实现

/**
* 基于动态数组的队列的实现
*/
public class ArrayQueue<E> implements Queue<E>{
    Array<E> array;

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

    public ArrayQueue(){
        array=new Array<>();
    }

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

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

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

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

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

    @Override
    public String toString() {
        StringBuilder ret=new StringBuilder();
        ret.append("Queue: ");
        ret.append("front [");
        for(int i=0;i<array.getSize();i++){
            ret.append(array.get(i));
            if(i!=array.getSize()-1){
                ret.append(", ");
            }
        }
        ret.append("] tail");
        return ret.toString();
    }
}

时间复杂度分析

操作	时间复杂度
enqueue(e)	均摊时间复杂度：O(1)
dequeue()	O(n)
front()	O(1)
getSize()	O(1)
isEmpty()	O(1)

循环队列

• 数组队列的问题

  出队操作，要移动数据，时间复杂度是O(n)

• 循环队列

队列为空判断条件：

front == tail

队列为满判断条件：

(tail + 1) % data.length == front 

动态调整数组大小的resize函数：

private void resize(int newCapacity) {
    //预留一个位置，用来判断队列是否已满
    E[] newData=(E[])new Object[newCapacity+1];
    for(int i=0;i<size;i++){
        //将原来循环队列中数据复制到新数组，原来的data数据是从 font开始的
        //复制到数组，新数组是从0小标开始的
        newData[i]=data[(i+front)%data.length];
    }
    data=newData;
    front=0;
    tail=size;
}

实现

public class LoopQueue<E> implements Queue<E>{
    private E[] data;
    private int front,tail;
    private int size;

    public LoopQueue(int capacity){
        //循环队列会浪费一个单位空间
        data=(E[])new Object[capacity+1];
        front=0;
        tail=0;
        size=0;
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length-1;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front==tail;
    }

    @Override
    public void enqueue(E e) {
        //入队操作，先判断队列是否满了
        if((tail+1)%data.length==front){
            resize(getCapacity()*2);
        }
        data[tail]=e;
        tail=(tail+1)%data.length;
        size++;
    }

    @Override
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalArgumentException("con not dequeue from empty queue");
        }
        E ret=data[front];
        data[front]=null;
        front=(front+1)%data.length;
        size--;
        if(size==getCapacity()/4 && getCapacity()/2!=0){
            resize(getCapacity()/2);
        }
        return ret;
    }

    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("con not dequeue from empty queue");
        }
        return data[front];
    }

    private void resize(int newCapacity) {
        E[] newData=(E[])new Object[newCapacity+1];
        for(int i=0;i<size;i++){
            newData[i]=data[(i+front)%data.length];
        }
        data=newData;
        front=0;
        tail=size;
    }

    @Override
    public String toString() {
        StringBuilder ret=new StringBuilder();
        ret.append(String.format("LooPQueue: size=%d,capacity=%d\n",size,getCapacity()));
        ret.append("font [");
        for(int i=front;i!=tail;i=(i+1)%data.length){
            ret.append(data[i]);
            if((i+1)%data.length!=tail){
                ret.append(", ");
            }
        }
        ret.append("] tail");
        return ret.toString();
    }
}

时间复杂度分析

操作	时间复杂度
enqueue(e)	均摊时间复杂度：O(1)
dequeue()	均摊时间复杂度：O(1)
front()	O(1)
getSize()	O(1)
isEmpty()	O(1)

比较

public class Main {
    public static void main(String[] args) {
       int opCount=100000;
       ArrayQueue<Integer> arrayQueue=new ArrayQueue<>();
       double t1=testQueue(arrayQueue,opCount);
       System.out.println("Array Queue time:"+t1+"s");

        LoopQueue<Integer> loopQueue=new LoopQueue<>();
        double t2=testQueue(loopQueue,opCount);
        System.out.println("Loop Queue time:"+t2+"s");
    }

    //测试使用q运行opCount个enqueue和dequeue操作所需要的时间，单位：秒
    private static double testQueue(Queue<Integer> q,int opCount){
        long startTime=System.nanoTime();

        Random random=new Random();
        for(int i=0;i<opCount;i++){
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for(int i=0;i<opCount;i++){
            q.dequeue();
        }
        long endTime=System.nanoTime();
        return (endTime-startTime)/1000000000.0;
    }
}