数据结构-栈和队列

Stack

  • 栈也是一种线性结构
  • 相比数组,栈对应的操作是数组的子集
  • 栈是一种后进先出的数据结构(LIFO)
  • 只能从一端添加元素,也只能从一端取出元素
  • 这一端称为栈顶


栈的应用是非常广泛的,如无处不在的撤销操作,程序运行时调用的系统栈,剪贴板里面的内容等等

创建自己的栈

首先确定栈的方法,创建栈的接口

public interface Stack<E> {

    int getSize();
    boolean isEmpty();
    void push(E e); //入栈
    E pop();    //出栈
    E peek();   //看一下栈顶元素
}

借用上面自定义中的数组来实现栈
创建ArrayStack类,实现接口中的方法

public class ArrayStack<E> implements Stack<E> {

    private 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();
    }

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

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

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

    @Override
    public E peek(){
        return array.getLast();
    }

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

根据栈的特性,在Array类中添加两个方法

    public E getLast(){
        return get(size - 1);
    }

    public E getFirst(){
        return get(0);
    }

创建main函数进行测试

public class Main {

    public static void main(String[] args) {

        ArrayStack<Integer> stack = new ArrayStack<>();

        for(int i = 0 ; i < 5 ; i ++){
            stack.push(i*i);
            System.out.println(stack);
        }

        stack.pop();
        System.out.println(stack);
    }
}

结果

Stack: [0] top
Stack: [0, 1] top
Stack: [0, 1, 4] top
Stack: [0, 1, 4, 9] top
Stack: [0, 1, 4, 9, 16] top
Stack: [0, 1, 4, 9] top

时间复杂度分析

push和pop可能会触发resize操作

  • int getSize(); O(1)
  • boolean isEmpty(); O(1)
  • void push(E e); O(1) 均摊
  • E pop(); O(1) 均摊
  • E peek(); O(1)

Queue

  • 栈队列也是一种线性结构
  • 相比数组, 队列对应的操作也是数组的子集
  • 队列是一种先进先出的数据结构(FIFO)
  • 只能从一端(队尾)添加元素,也只能从一端(队首)取出元素

创建自己的队列

确定队列的方法, 创建队列的接口

public interface Queue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E e);  //入队
    E dequeue();        //出队
    E getFront();       //查看队首
}

依然使用自己创建的动态数组来实现队列
创建ArrayQueue类, 实现Queue的方法, 并进行测试

public class ArrayQueue<E> implements Queue<E> {

    private 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();
    }

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

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

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

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

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

    public static void main(String[] args) {

        //每入队三个, 出队一个
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);
            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

输出结果

Queue: front [0] tail
Queue: front [0, 1] tail
Queue: front [0, 1, 2] tail
Queue: front [1, 2] tail
Queue: front [1, 2, 3] tail
Queue: front [1, 2, 3, 4] tail
Queue: front [1, 2, 3, 4, 5] tail
Queue: front [2, 3, 4, 5] tail
Queue: front [2, 3, 4, 5, 6] tail
Queue: front [2, 3, 4, 5, 6, 7] tail
Queue: front [2, 3, 4, 5, 6, 7, 8] tail
Queue: front [3, 4, 5, 6, 7, 8] tail
Queue: front [3, 4, 5, 6, 7, 8, 9] tail

时间复杂度

  • int getSize(); O(1)
  • boolean isEmpty(); O(1)
  • void enqueue(E e); O(1) 均摊
  • E dequeue(); O(n)
  • E getFront(); O(1)

循环队列

数组队列在出队时由于需要将后面的元素都向前挪一位,时间复杂度是O(n),如果使用循环队列,时间复杂度就会降低

创建LoopQueue类,进行测试

public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front, tail;
    private int size;

    //由于判空的条件是front == tail,
    //当front不在下标为o的位置,队列满时,tail会从头开始
    //因为判空条件是front == tail,
    //所以判满条件是(tail + 1) % data.length == front
    //这样就应该在创建队列时多开辟一个空间
    //      front
    //        ↓
    //⏹⏹⏹⏹⏹⏹⏹⏹⏹
    //      ↑
    //     tail
    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 boolean isEmpty(){
        return front == tail;
    }

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

    // 入队时首先判断一下队列是否已满
    // 已满的话需要进行扩容
    @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("Cannot dequeue from an 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("Queue is empty.");
        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;
    }

    // 重写toString方法时
    // 需要注意for 循环的起始位置和终止条件
    @Override
    public String toString(){

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

    public static void main(String[] args){

        LoopQueue<Integer> queue = new LoopQueue<>(5);
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

循环队列的时间复杂度

  • int getSize(); O(1)
  • boolean isEmpty(); O(1)
  • void enqueue(E e); O(1) 均摊
  • E dequeue(); O(1) 均摊
  • E getFront(); O(1)

数组队列和循环队列的比较

创建一个main函数进行测试

import java.util.Random;

public class Main {

    // 测试使用q运行opCount个enqueueu和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;
    }

    public static void main(String[] args) {

        int opCount = 100000;

        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue, time: " + time1 + " s");

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

运行结果

ArrayQueue, time: 58.8541207 s
LoopQueue, time: 0.0163572 s

主要差异:
ArrayQueue出队的时间复杂度是O(n)级别的,再加上外层的循环就是O(n^2)级别的了,所以对于ArrayQueue来说,testQueue方法的时间复杂度是O(n^2)级别的; 而循环队列出队的时间复杂度是O(1)级别的, 再加上外层的循环就是O(n)级别的了,所以对于LoopQueue来说,testQueue方法的时间复杂度是O(n)级别的

完整代码

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容