/ 数据结构与算法 / 0 条评论 / 264浏览

栈(stack)是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)。

栈又称为后进先出(LIFO)的数据结构。

栈有两种基本实现: 顺序结构链式结构

栈的顺序结构实现

这里基于动态数组实现栈:

代码

这里我使用自己封装的泛型动态数组来实现顺序结构的栈。

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

    private Array<E> array;

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

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

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

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

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

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

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

复杂度分析

顺序结构是基于数组实现栈的,所以我为数组类添加了一个扩容方法(resize),入栈可能触发数组扩容,所以均摊复杂度为 O(n)

出栈和获取栈顶元素可以通过 size 快速访问,所以复杂度均为 O(1)

栈的链式结构实现

这里基于链表实现栈:

代码

这里我使用自己封装的链表类实现链式结构的栈。

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

    private LinkedList<E> list;

    public LinkedListStack(LinkedList<E> list) {
        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();
    }
}

复杂度分析

只对链表头的元素进行操作时间复杂度为O(1)

链式结构对比顺序结构

import datastruct.queue.LoopQueue;
import java.util.Random;

public class CompareStackTest {
    public static double testStack(Stack<Integer> stack, int opCount) {
        Random random = new Random();
        long startTime = System.nanoTime();

        // enqueue and dequeue
        for (int i = 0; i < opCount; i++) {
            stack.push(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0; i < opCount; i++) {
            stack.pop();
        }

        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {
        int opCount = 100000;

        ArrayStack<Integer> arrayStack = new ArrayStack<>();
        System.out.println("ArrayQueue time: " + testStack(arrayStack, opCount) + "s");
        LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
        System.out.println("LoopQueue time: " + testStack(linkedListStack, opCount) + "s");
    }
}

ArrayStack time: 0.01505259s
LinkedListStack time: 0.015638983s

顺序结构和链式结构在入栈和出栈的时间复杂度接近,所以时间上是接近的。

栈的应用

Undo

例如 Word 之类编辑器的撤销操作

程序调用的系统栈

子函数的调用

空号匹配 - 编译器

例如编译器对于 Java 函数的 {} 匹配

这里使用 leetcode 上一道题:

题目:
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

有效字符串需满足:

    1. 左括号必须用相同类型的右括号闭合。
    2.左括号必须以正确的顺序闭合。
        
注意空字符串可被认为是有效字符串。

示例:
输入: "()[]{}"
输出: true

code:

import java.util.Stack;

public class Solution {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // put character into stack which is left bracket
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                // get chars from top of stack judge matching or not
                Character top = stack.pop();
                if (c == ')' && top != '(') {
                    return false;
                }
                if (c == ']' && top != '[') {
                    return false;
                }
                if (c == '}' && top != '{') {
                    return false;
                }
            }
        }
        // return true if stack is empty
        return stack.isEmpty();
    }
}

Java中的Stack是种不良设计?

“Java 中的 Stack 是通过 Vector 来实现的,这种设计被认为是不良的设计,说说你的看法?”

前段时间在网上看到了这样一个问题,今天就来探讨一下 Java 类库中的 Stack.

先来阅读一下 Stack 官方文档

源码概述

/**
 * The <code>Stack</code> class represents a last-in-first-out
 * (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
 * operations that allow a vector to be treated as a stack. The usual
 * <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
 * method to <tt>peek</tt> at the top item on the stack, a method to test
 * for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
 * the stack for an item and discover how far it is from the top.
 * <p>
 * When a stack is first created, it contains no items.
 *
 * <p>A more complete and consistent set of LIFO stack operations is
 * provided by the {@link Deque} interface and its implementations, which
 * should be used in preference to this class.  For example:
 * <pre>   {@code
 *   Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>
 *
 * @author  Jonathan Payne
 * @since   JDK1.0
 */

Stack 类代表了一个后进先出(LIFO)的对象。

它继承自 Vector ,下面五个方法都是基于 vector 实现:

  1. push(进栈) 操作,
  /**
     * Pushes an item onto the top of this stack. This has exactly
     * the same effect as:
     * <blockquote><pre>
     * addElement(item)</pre></blockquote>
     *
     * @param   item   the item to be pushed onto this stack.
     * @return  the <code>item</code> argument.
     * @see     java.util.Vector#addElement
     */
    public E push(E item) {
        addElement(item);

        return item;
    }
  1. pop(出栈) 操作,
 /**
     * Removes the object at the top of this stack and returns that
     * object as the value of this function.
     *
     * @return  The object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }
  1. 得到栈顶元素的 peek() 方法,
/**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     *
     * @return  the object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
  1. empty() 方法,
 /**
     * Tests if this stack is empty.
     *
     * @return  <code>true</code> if and only if this stack contains
     *          no items; <code>false</code> otherwise.
     */
    public boolean empty() {
        return size() == 0;
    }
  1. 一种在栈中搜索元素的方法,并发现它离顶部有多远的 search() 方法。
/**
     * Returns the 1-based position where an object is on this stack.
     * If the object <tt>o</tt> occurs as an item in this stack, this
     * method returns the distance from the top of the stack of the
     * occurrence nearest the top of the stack; the topmost item on the
     * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
     * method is used to compare <tt>o</tt> to the
     * items in this stack.
     *
     * @param   o   the desired object.
     * @return  the 1-based position from the top of the stack where
     *          the object is located; the return value <code>-1</code>
     *          indicates that the object is not on the stack.
     */
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

最后文档中还提到一种更加完整和一致的 Stack 顺序结构实现:

Deque<Integer> stack = new ArrayDeque<Integer>();

由于 LinkedList 继承自 AbstractSequentialList ,我们可以将 LinkedList 用做 stack 的链式结构实现:

LinkedList<Integer> stack = new LinkedList<>();

提示 : 完整代码放在了我的 gitee 上面