数据结构--栈和队列

一、栈（stack）

1、定义

栈也是一种线性的数据结构

规定的是只能从栈顶添加元素、也只能从栈顶去除元素

·栈是一种后进先出的数据结构

·Last In First Out (LIFO)

2、栈的具体实现

public interface Stack_I<T> {
    //入栈
    void push(T ele);

    //出栈
    T pop();

    //查看栈顶元素
    T peek();

    //判断栈是否为空
    boolean isEmpty();

    //判断栈中元素的个数
    int getSize();
}

3、时间复杂度分析

4、数组栈

以数组作为栈的底层结构实现一个私有的栈结构

//  以数组作为栈的底层数据结构
public class ArrStack<T> implements Stack_I<T> {

    private MyArr<T> data;//容器
    int size; //栈中实际存放元素的个数

    public ArrStack() {
        this.data = new MyArr<>(100);
        this.size = 0;
    }

    @Override
    public void push(T ele) {
        this.data.add(ele);
        this.size++;
    }

    @Override
    public T pop() {
        if (isEmpty()){
            return null;
        }
        this.size--;
        return this.data.removeFromLast();
    }

    @Override
    public T peek() {
        return this.data.getLastValue();
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

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

5、测试

public class StackTest<T> {

    public void test(Stack_I<T> stack, List<T> list) {
        //开始时间
        long startTime = System.nanoTime();
        //入栈
        for (int i = 0; i < list.size(); i++) {
            stack.push(list.get(i));
        }
        System.out.println("栈中元素的个数：" + stack.getSize());
        //出栈操作
        while (!stack.isEmpty()) {
            T ele = stack.pop();
            System.out.print(ele + "---->");
        }

        //结束时间
        long endTime = System.nanoTime();
        System.out.println("总耗时:" + (endTime - startTime) / 1000000000.0 + "s");
    }

    public static void main(String[] args) {
        StackTest<Integer> stackTest = new StackTest<>();
        Stack_I<Integer> stack = new LinkedStack<>();
        List<Integer> list = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            int val = random.nextInt(1000);
            System.out.print(val + "---->");
            list.add(val);
        }

        stackTest.test(stack, list);
    }
}

二、队列

1、定义

队列也是一种线性的数据结构

规定只能从一端的队尾添加元素，从另一端的队首取出元素

·队列是一种先进先出的数据结构

2、队列的实现

public interface Queue_I<T> {

    //入队
    void offer(T ele);

    //出队
    T poll();

    //查看队首元素
    T peek();

    //队列中元素的个数
    int getSize();

    //队列是否为空
    boolean isEmpty();
}

3、数组队列的问题

        其中dequeue()操作的时间复杂度为O(n)，原因时在出队时，数组后面的元素都要进行前移。

删除队首元素a后，

为了解决前移的问题，可以使用front记录队首位置，使用tail记录队尾位置，这就是循环队列。

情况1：

情况2：

情况3：

4、循环队列的复杂度分析

5、数组队列结构的实现

public class ArrQueue<T> implements Queue_I<T> {

    //队列的容器
    private MyArr<T> data;

    public ArrQueue() {
        this.data = new MyArr<>(100);
    }

    @Override
    public void offer(T ele) {
        this.data.add(ele);
    }

    @Override
    public T poll() {
        if (isEmpty()) {
            return null;
        }
        return this.data.removeByIndex(0);
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            return null;
        }
        return this.data.getValueByIndex(0);
    }

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

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

6、测试

public class QueueTest<T> {

    public void test(Queue_I<T> queue, List<T> list) {
        //开始时间
        long startTime = System.nanoTime();
        //入队列
        for (int i = 0; i < list.size(); i++) {
            T temp = list.get(i);
            System.out.print(temp+"---");
            queue.offer(list.get(i));
        }
        System.out.println("\n队列中元素的个数：" + queue.getSize());
        //出队操作
        while (!queue.isEmpty()) {
            T ele = queue.poll();
            System.out.print(ele + "--->");
        }

        //结束时间
        long endTime = System.nanoTime();
        System.out.println("总耗时:" + (endTime - startTime) / 1000000000.0 + "s");
    }

    public static void main(String[] args) {
        QueueTest<Integer> queueTest = new QueueTest<>();
        //Queue_I<Integer> queue = new LoopQueue<>();
        Queue_I<Integer> queue = new LinkedQueue<>();
        List<Integer> list = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            int val = random.nextInt(1000);
            System.out.print(val + "---->");
            list.add(val);
        }

        queueTest.test(queue, list);
    }
}

7、补充

使用Stream的方式遍历

1、将数组转换为stream,有两种方式:

Stream.of(arr),Arrays.stream(arr)

2、使用Arrays.stream()转换时，如果是包装类，转换后的类型为Stream，基础类型，转换后为IntStream

3、使用Stream.of()转换时，如果是包装类，转换后的类型为Stream，基础类型，转换后为

Stream<int[ ]>

三、单调栈

单调栈实际上还是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内元素都保持单调。