跳到主要内容

09、数据结构与算法 - 实战:栈

栈(stack)是一个有序线性表,只能在表的一端(成为栈顶,top)执行插入和删除操作。最后插入的元素是第一个被删除的。所以栈也称为后进先出(Last In First Out,LIFO)或先进后出(First In Last Out,FILO)线性表。
两个栈操作都有专用名称,一个称为入栈(push),表示在栈中插入一个元素;另一个称为出栈(pop),表示从栈中删除一个元素。
试图对一个空栈执行出栈操作称为下溢(underflow);试图对一个满栈执行插入操作称为溢出(overflow)。

常用的实现方式:
1、 基于简单数组的实现方式;
2、 基于动态数组的实现方式;
3、 基于链表的实现方式;

简单数组的实现有一个局限性,就是栈的最大空间必须预先声明且不能改变。一旦对满栈执行入栈操作将出现溢出异常。

/**
 * 简单数组实现栈
 */
public class ArrayStack {
   
     

    /**
     * 栈顶
     */
    private int top;

    /**
     * 栈的容量
     */
    private int capacity;

    /**
     * 实现栈的数组
     */
    private int[] array;

    /**
     * 无参构造方法
     */
    public ArrayStack() {
        this.capacity = 1;
        this.array = new int[this.capacity];
        this.top = -1;
    }

    /**
     * 有参构造方法
     * @param capacity 数组的大小
     */
    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.array = new int[this.capacity];
        this.top = -1;
    }

    /**
     * 判断栈是否为空
     * @return true 是空栈 false 不是空栈
     */
    public boolean isEmpty() {
        return (top == -1);
    }

    /**
     * 判断栈是否已满
     * @return true 是满栈 false 不是满栈
     */
    public boolean isFull() {
        return (top == (capacity - 1));
    }

    /**
     * 获取栈中元素个数
     * @return 栈中元素个数
     */
    public int size() {
        return (top + 1);
    }

    /**
     * 入栈
     * @param data 需要入栈的数据
     */
    public void push(int data) {
        if (isFull()) {
            System.out.println("栈溢出!");
        } else {
            top++;
            array[top] = data;
        }
    }

    /**
     * 出栈
     * @return 出栈数据
     */
    public int pop() {
        if (isEmpty()) {
            System.out.println("栈为空!");
            return -999;    // 栈为空时一般约定返回一个不常用的数
        } else {
            return array[top--];
        }
    }

    /**
     * 删除栈
     */
    public void deleteStack() {
        top = -1;
    }
}

动态数组的实现可以采用重复倍增技术提高性能。如果当前数组空间已满,就新建一个比原数组大一倍的新数组,然后复制元素。
注意:倍增太多可能导致内存溢出。

/**
 * 动态数组实现栈
 */
public class DynArrayStack {
   
     

    /**
     * 栈顶
     */
    private int top;

    /**
     * 栈的容量
     */
    private int capacity;

    /**
     * 实现栈的数组
     */
    private int[] array;

    /**
     * 无参构造方法
     */
    public DynArrayStack() {
        this.capacity = 1;
        this.array = new int[this.capacity];
        this.top = -1;
    }

    /**
     * 有参构造方法
     * @param capacity 数组的大小
     */
    public DynArrayStack(int capacity) {
        this.capacity = capacity;
        this.array = new int[this.capacity];
        this.top = -1;
    }

    /**
     * 判断栈是否为空
     * @return true 是空栈 false 不是空栈
     */
    public boolean isEmpty() {
        return (top == -1);
    }

    /**
     * 判断栈是否已满
     * @return true 是满栈 false 不是满栈
     */
    public boolean isFull() {
        return (top == (capacity - 1));
    }

    /**
     * 获取栈中元素个数
     * @return 栈中元素个数
     */
    public int size() {
        return (top + 1);
    }

    /**
     * 入栈
     * @param data 需要入栈的数据
     */
    public void push(int data) {
        if (isFull()) {
            // 如果栈满了就倍增扩容
            doubleStack();
        } 
        top++;
        array[top] = data;
    }

    /**
     * 数组动态扩容,采用重复倍增
     */
    private void doubleStack() {
        // 创建新的数组,大小为原来数组的两倍
        int[] newArray = new int[2 * capacity];
        // 复制原数组到新数组
        System.arraycopy(array, 0, newArray, 0, capacity);
        // 重置数组容量
        capacity = capacity * 2;
        // 复制给原数组,也就是使array指向新生成内存
        array = newArray;
    }

    /**
     * 出栈
     * @return 出栈数据
     */
    public int pop() {
        if (isEmpty()) {
            System.out.println("栈为空!");
            return -999;    // 栈为空时一般约定返回一个不常用的数
        } else {
            return array[top--];
        }
    }

    /**
     * 删除栈
     */
    public void deleteStack() {
        top = -1;
    }
}

通过在表头插入元素的方式实现push操作,删除表头元素实现pop操作。


/**
 * 链表实现栈(使用泛型)
 */
public class LinkedListStack<AnyType> {
   
     

    /**
     * 栈顶
     */
    private ListNode<AnyType> headNode;

    /**
     * 无参构造方法
     */
    public LinkedListStack() {
        headNode = null;
    }

    /**
     * 有参构造方法
     */
    public LinkedListStack(AnyType data) {
        this.headNode = new ListNode<AnyType>(data); 
    }

    /**
     * 判断栈是否为空
     * @return true 是空栈 false 不是空栈
     */
    public boolean isEmpty() {
        return (headNode == null);
    }

    /**
     * 获取栈中元素个数
     * @return 栈中元素个数
     */
    public int size() {
        int size = 0;
        ListNode<AnyType> currentNode = headNode;
        while (currentNode != null) {
            size++;
            currentNode = currentNode.getNext();
        }
        return size;
    }

    /**
     * 入栈
     * @param data 需要入栈的数据
     */
    public void push(AnyType data) {
        if (isEmpty()) {
            headNode = new ListNode<AnyType>(data);
        } else if (headNode.getData() == null){
            headNode.setData(data);
        } else {
            ListNode<AnyType> newNode = new ListNode<AnyType>(data);
            newNode.setNext(headNode);
            // 更新栈顶
            headNode = newNode;
        }
    }

    /**
     * 输出栈顶元素
     * @return 栈顶元素
     */
    public AnyType top() {
        if (isEmpty()) {
            return null;
        } else {
            return headNode.getData();
        }
    }

    /**
     * 出栈
     * @return 出栈数据
     */
    public AnyType pop() {
        if (isEmpty()) {
            System.out.println("栈为空!");
            return null;    
        } else {
            AnyType data = headNode.getData();
            headNode = headNode.getNext();
            return data;
        }
    }

    /**
     * 删除栈
     */
    public void deleteStack() {
        headNode = null;
    }
}