DS02:栈

基本特性

特性

栈的特性无非也就是后进先出（LIFO）。

其为操作受限的线性表，其主要特点就是栈的插入与删除只能在栈顶进行，分别对应进栈（push）与出栈（pop）两个操作。

用处

首先想到的当然就是系统栈、递归、深度优先搜索了，除此之外还有很多。

需要实现的基本内容

在Java语言中，实现一个栈的接口表示一个栈需要的基本方法，如下：

public interface Stack<E> {
    int getSize();	// 获取元素个数
    boolean isEmpty();	// 判断栈是否为空
    void push(E e);	// 入栈操作
    E pop();	// 出栈操作
    E peek();	// 获取栈顶元素
}

栈主要有两种存储方法，即线性存储（底层是动态数组）与链接存储（底层为链表），之后分别记录这两种栈的实现方法。

线性存储

存储实现如下，直接套用之前在《1、动态数组》实现的动态数组即可，之后按照类的定义进行实现，代码如下：

public class ArrayStack<E> implements Stack<E> {

    Array<E> array;

    public ArrayStack(int caoacity) {
        array = new Array<>(caoacity);
    }

    public ArrayStack() {
        array = new Array<>();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public void push(E e) {
        array.addLast(e);
    }

    @Override
    public E pop() {
        return array.removeLast();
    }

    @Override
    public E peek() {
        return array.getLast();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

}

链接存储

套用在《4、链表》中实现的链表作为底层数据结构即可进行实现，代码如下：

使用链接存储时栈顶为链表的头，这是由于删除链表的头元素的时间复杂度为O(1)，而要删除链表最后一个元素时间复杂度为O(n)。

public class LinkedListStack<E> implements Stack<E> {

    private LinkedList<E> list;

    public LinkedListStack() {
        list = new LinkedList<>();
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

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

    @Override
    public void push(E e) {
        list.addFirst(e);
    }

    @Override
    public E pop() {
        return list.removeFirst();
    }

    @Override
    public E peek() {
        return list.getFirst();
    }

}

Donate