一、栈是什么？
二、栈的接口设计
三、栈的常用方法
四、栈的底层是什么？
五、栈的自实现（数组、单链表、双向链表）
六、栈的应用（浏览器的前进后退、根据逆波兰表达式求值）
七、栈、虚拟机栈、栈帧有什么区别呢？

一、栈是什么？

栈是一种特殊的线性表，只能在一端进行操作

往栈中添加元素的操作，一般叫做push，入栈

从栈中移除元素的操作，一般叫做pop，出栈（只能移除栈顶元素，也叫做弹出栈顶元素）

遵循先进后出，后进先出的原则

注意：这里所说的栈和栈空间是两个不同的概念，栈是一种数据结构，用来组织数据和存放数据的，而栈空间是内存的一种，是一种内存空间。

二、栈的接口设计

栈可以直接在链表的基础上去实现，运用组合的方式，让ArrayList成为栈的一部分，然后在此基础上实现栈的功能。

◼ int size(); // 元素的数量

◼ boolean isEmpty(); // 是否为空

◼ void push(E element); // 入栈

◼ E pop(); // 出栈

◼ E top(); // 获取栈顶元素

◼ void clear(); // 清空

public class Stack<E> {
	private List<E> list = new ArrayList<>();
	
	public void clear() {
		list.clear();
	}
	
	public int size() {
		return list.size();
	}

	public boolean isEmpty() {
		return list.isEmpty();
	}

	public void push(E element) {
		list.add(element);
	}


	public E pop() {
		return list.remove(list.size() - 1);
	}


	public E top() {
		return list.get(list.size() - 1);
	}
}

三、栈的常用方法

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

四、栈的底层是什么？

通过观察源码，我们可以发现，Stack继承了Vector。

Vector是用数组实现的，所以栈的底层是数组。

五、栈的自实现（数组、单链表、双向链表）

一：用数组自实现：

public class MyStack {
    int[] elem;
    int usesize;
    static final int DEFAULT_SIZE = 10;
    public MyStack(){
        this.elem = new int[DEFAULT_SIZE];
    }
    public int push(int val){
        if (isFull()){
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[usesize] = val;
        usesize++;
        return val;
    }
    public boolean isFull(){
        return usesize == elem.length;
    }
    public int pop(){
        if (empty()){
            throw new MyEmptyStackException("栈为空！");
        }
        return elem[--usesize];
    }
    public boolean empty(){
        return usesize == 0;
    }
    public int peek(){
        if (empty()){
            throw new MyEmptyStackException("栈为空！");
        }
        return elem[usesize-1];
    }
}

二：用单链表的也可以实现，其中入栈用头插，出栈也是在头部，时间复杂度为O(1)。当然双向链表也可以实现栈，而且头尾都可以作为出栈和入栈。