七、栈(Stack)

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

• 往栈中元素的操作，一般叫做
• 从栈中元素的操作，一般叫做(只能移除栈顶元素，也叫做:弹出栈顶元素)
• 后进先出的原则，Last In First Out，LIFO

栈(Stack)

栈的接口设计

int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void push(E element); // 入栈
E pop(); // 出栈
E top(); // 获取栈顶元素

因为栈是从栈顶添加元素，那么我们可以直接利用之前实现的ArrayList或者LinkedList来实现栈，都是从最后添加元素。这里使用动态数组和双向链表来实现栈性能都是一样的，都是O(1),因为都是往最后添加元素。

直接继承ArrayList或者LinkedList

public class Stack<E> extends ArrayList<E>{

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


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


    public E top() {
        return get(size -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(size() -1);
    }

    public E top() {// 官方的是peek()
        return list.get(size() -1);
    }
    
    public void clear() {
        list.clear();
    }
}

代码链接

代码地址