04_栈

栈的初识

• 栈是一种特殊的线性表，只能在一端进行操作
• 往栈中添加元素的操作，一般叫做push，入栈
• 从栈中移除元素的操作，一般叫做pop，出栈（只能移除栈顶元素，也叫做：弹出栈顶元素）
• 后进先出的原则，Last In First Out ,LIFO

Snip20200914_23.png

栈的接口设计

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

代码实现

• 利用动态数组

package Stack;

import ListArray.LZArrayList;

public class LZStack<E> {
    private LZArrayList<E> list = new LZArrayList<>();

    public void push(E element){
        list.add(element);
    }
    public void pop(){
        list.remove(list.size()-1);
    }
    public E top(){
        return list.get(list.size()-1);
    }

    public void clear(){
        list.clear();
    }

    public int size(){
        return list.size();
    }

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

    @Override
    public String toString(){
        return list.toString();
    }

}

• 利用双向链表

package Stack;

import LinkedList.LZLinkedList;

public class LZStack2<E> {
    private LZLinkedList<E> list = new LZLinkedList<>();

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

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

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

    public void clear(){
        list.clear();
    }

    public int size(){
        return list.size();
    }

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

    @Override
    public String toString(){
        return list.toString();
    }
}