数据结构(六)-栈

参考文献

栈

• 先进后出(FILO)

package com.holelin.stack;
/**
 * 栈
 * @param <E> 元素类型
 */
public interface Stack<E> {
    /**
     * 入栈 -- 将元素放入栈顶
     * @param e 入栈的元素
     */
    void push(E e);

    /**
     * 出栈 -- 将栈顶元素出栈
     * @return 栈顶元素的值
     */
    E pop();

    /**
     * 获取栈顶元素,但不出栈
     * @return 栈顶元素的值
     */
    E peek();

    /**
     * 获取栈中元素的个数
     * @return 栈中元素的个数
     */
    int getSize();

    /**
     * 判断栈是否为空
     * @return 栈为空返回true;栈不为空返回false
     */
    boolean isEmpty();

}

顺序栈:数组实现栈

package com.holelin.stack;

import com.holelin.array.Array;

/**
 * ClassName: ArrayStack
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/21
 */

public class ArrayStack<E> implements Stack<E> {
    private Array<E> mArray;

    /**
     * 创建指定栈的容量
     *
     * @param capacity
     */
    public ArrayStack(int capacity) {
        mArray = new Array<>(capacity);
    }

    /**
     * 创建使用默认容量的栈
     */
    public ArrayStack() {
        mArray = new Array<>();
    }

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

    @Override
    public void push(E e) {
        // 放入数组的末尾
        mArray.addLast(e);
    }

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

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

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

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

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Stack: size = %d, capacity = %d\n", mArray.getSize(),mArray.getCapacity()));

        res.append('[');
        for (int i = 0; i < mArray.getSize(); i++) {
            res.append(mArray.get(i));
            if (i != mArray.getSize() - 1) {
                res.append(",");
            }
        }
        res.append("] top");
        return res.toString();
    }
}

测试用例

package com.holelin.stack;

/**
 * ClassName: ArrayStackTest
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/21
 */

public class ArrayStackTest {
    public static void main(String[] args) {
        ArrayStack<Integer> arrayStack = new ArrayStack<>();
        for (int i = 0; i < 21; i++) {
            arrayStack.push(i);
            System.out.println(arrayStack);
        }
        arrayStack.pop();
        System.out.println(arrayStack);
    }
}

链式栈:链表实现栈

package com.holelin.stack;

import com.holelin.linkedlist.LinkedList;

/**
 * ClassName: LinkedListStack
 * 链表实现栈 -- 链栈
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/30
 */

public class LinkedListStack<E> implements Stack<E> {
    private LinkedList<E> list;

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

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

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

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

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

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

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append("Stack: top ");
        res.append(list);
        return res.toString();
    }
}

测试用例

package com.holelin.stack;

/**
 * ClassName: LinkedListStackTest
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/30
 */

public class LinkedListStackTest {
    public static void main(String[] args) {
        LinkedListStack<Integer> linkedList = new LinkedListStack<>();
        for (int i = 0; i <10; i++) {
            linkedList.push(i);
            System.out.println(linkedList);
        }
        linkedList.pop();
        System.out.println(linkedList);
    }
}

ArrayStack与LinkedListStack效率对比

package com.holelin.stack;

import java.util.Random;

/**
 * ClassName: QueueEfficiencyTest
 * 测试ArrayStack和LinkedListStack的效率
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/30
 */

public class StackEfficiencyTest {
    public static void main(String[] args) {
        int opCount = 100000;
        ArrayStack<Integer> arrayStack = new ArrayStack<>();
        double time1 = testStack(arrayStack, opCount);
        System.out.println("ArrayStack time is " + time1 + " s");
        LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
        double time2 = testStack(linkedListStack, opCount);
        System.out.println("LinkedListStack time is " + time2 + " s");
    }

    private static double testStack(Stack<Integer> q, int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0; i < opCount; i++) {
            q.push(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0; i < opCount; i++) {
            q.pop();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }


}

应用场景

调用栈

表达式求值

括号匹配