一、栈 Stack

1.特点

（1）栈是一种线性数据结构

（2）规定只能从栈顶添加元素，从栈顶取出元素

（3）是一种先进后出的数据结构（Last First Out）LIFO

2.具体实现

Java中可以直接调用方法来实现栈

如何自己写代码来实现栈呢？

先定义一个接口，方便后边进行调用

package com.algo.lesson.lesson02.stack;

public interface Stack_I<T> {
    //入栈
    void push(T ele);
    //出栈
    T pop();
    //查看栈顶元素
    T peek();
    //判断是否为空
    boolean isEmpty();
    //后去栈中元素
    int getSize();
}

接下来来实现栈的方法，调用接口，完善方法：

package com.algo.lesson.lesson02.stack;

import com.algo.lesson.lesson01.MyArr;

//以数组作为栈顶的底层数据结构
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.removeBFromLast();
    }

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

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

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

以上就是方法的代码，接下来，写个main函数来调用，检查方法是否正确

package com.algo.lesson.lesson02.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

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.println(ele+"  ");
        }

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

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

注：其中long startTime=System.nanoTime();方法是获取一个时间（单位毫秒）

在程序运行前和运行后个添加一个，最后将两个时间相减，得到程序运行时间。

3.时间复杂度分析

二、队列

1.特点

（1）队列也是一种线性数据结构

（2）只能从一端添加元素，另一端取出元素

（3）是一种先进先出的数据结构（FIFO——fist in fist out ）

2.具体实现

Java中也可以直接调用队列的方法：

自己的实现：

接口：

package com.algo.lesson.lesson02.queue;

public interface Queue_I<T> {
    void offer(T ele);//入队
    T poll();//出队
    T peek();//查找队首元素
    int getSize();
    boolean isEmpty();


}

方法代码：

package com.algo.lesson.lesson02.queue;

import com.algo.lesson.lesson01.MyArr;

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

    private MyArr<T>data;

/*
    private int size;//队列中元素的个数
*/

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

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

3.出现的问题

入队列时间复杂度为O(n)，因为在出队时，元素要前移，会出现假溢出的情况。

所以就出现了循环队列来解决这个问题

循环队列：

front记录队首，tail记录队尾，队尾达到容积时，返回到队头，将空位置补上，可以继续存储数据。

package com.algo.lesson.lesson02.queue;

import java.util.Random;

/*
基于Java中的数组进行二次封装,制作一个可变数组
 */
//泛型:就是类型作为参数
public class LoopArr<T> {
    private T[] data;//保存数据

    private int size;//数组中实际存放元素的个数

    private int front;//队首

    private int tail;//队尾

    int capacity;//容积

    //构造函数
    public LoopArr(int capacity) {
        if (capacity <= 0) {
            this.capacity = 11;
        } else {
            this.capacity = capacity + 1;
        }
        this.size = 0;
        this.front = this.tail = 0;
        this.data = (T[]) (new Object[this.capacity]);
    }

    //获取数组中实际存放元素的个数
    public int getSize() {
        return this.size;
    }

    //获取数组的容积
    public int getCapacity() {
        return this.capacity;
    }

    //判断数组是否为空
    public boolean isEmpty() {
        return this.front == this.tail;
    }

    //向数组中添加元素(尾部)
    public void add(T item) {
        //判断数组是否满
        if ((this.tail + 1) % this.capacity == this.front) {
            //扩容
            resize((this.capacity-1)*2+1);
        }
        //从index位置开始元素需要进行后移
        this.data[this.tail] = item;
        this.tail = (this.tail + 1) % this.capacity;
        //更新this.size
        this.size++;
    }

    private void resize(int newCapacity) {
        System.out.println("resize:" + newCapacity);
        T[] newData = (T[]) (new Object[newCapacity]);
        //将原数组驾到新数组里

        for (int i = 0; i < this.size; i++) {
            newData[i] = this.data[(this.front+i)%this.capacity];
        }
        //改变容器
        this.data = newData;
        this.capacity = newCapacity;
        //将this.front置零
        this.front=0;
        this.tail=this.size;
    }

    //获取指定位置的值
    public T getValueByIndex() {
        if(isEmpty()){
            return null;
        }
        return this.data[this.front];
    }

    //移除队首元素
    public T remove() {
        if (isEmpty()) {
            return null;
        }
        //删除操作的核心
        /*
        1.找到删除的位置
        2.删除位置之后的元素要前移 arr[j-1]=arr[j]
         */
        T delValue = this.data[this.front];
        this.front = (this.front + 1) % this.capacity;
        this.size--;
        //判断是否缩容
        if (this.size < this.capacity / 4 && this.capacity / 2 > 0) {
            resize((this.capacity-1) / 2 +1);
        }
        return delValue;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < this.size; i++) {
            sb.append(this.data[i]);
            if (i != this.size - 1) {
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

package com.algo.lesson.lesson02.queue;

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

    private LoopArr<T>data;//容器

    public LoopQueue(){
        this.data=new LoopArr<>(100);
    }




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

    @Override
    public T poll() {
        return this.data.remove();
    }

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

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

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

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

三、栈和队列的互相实现

既然我们了解了栈和队列，知道了这两种数据结构十分相似，也就可以大胆假设以下，可不可以相互实现，不是用上面所写的以数组为底层，而是相互为底层存储。

1.用栈来实现队列

import java.util.Stack;

class MyQueue {
    private Stack<Integer> A;
    private Stack<Integer> B;

    public MyQueue() {
        A = new Stack<>();
        B = new Stack<>();
    }

    public void push(int x) {
        while (!B.isEmpty()) {
            A.push(B.pop());
        }
        A.push(x);
        while (!A.isEmpty()) {
            B.push(A.pop());
        }
    }

    public int pop() {
        return B.pop();
    }

    public int peek() {
        return B.peek();
    }

    public boolean empty() {
        return B.isEmpty();
    }
}

2.用队列实现栈

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue2.add(x);
        while (!queue1.isEmpty()) {
            queue2.add(queue1.remove());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    public int pop() {
        return queue1.remove();
    }

    public int top() {
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}

这就是这两种数据结构相互实现的代码

在LeetCode中也有相对应的题目：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台（栈实现队列）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台（队列实现栈）