线性表之栈

1、简介

栈是一种特殊的线性表，只能在一端进行操作。栈有以下特征：

• 1、向栈中添加元素的操作，一般叫push，入栈。
• 2、从栈中删除元素的操作，一般叫pop，出栈（只能移除栈顶元素，也叫弹出栈顶元素。）
• 3、后进先出的原则，LIFO。
  image.png

2、栈的接口设计

根据栈的特性，在栈中可以定义如下方法

public int size(); //元素的数量
    
public boolean isEmpty() ; //是否为空

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

public E pop();//出栈

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

public void clear();//清空元素

根据栈的特性，我们在栈的内部可以使用数组或链表来实现。根据栈的特性可知，一直操作的都是尾部的元素，所以使用数组或链表来实现其复杂度都是O(1)，下面看下内部使用数组来实现。

public class Stack<E> {
    private List<E> list = new ArrayList<>();

    // 元素的数量
    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);
    }

    // 清空元素
    public void clear() {
        list.clear();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size=" + size()+" ");
        while (!isEmpty()) {
            sb.append(pop()).append(",");
        }
        return sb.toString();
    }

}