栈

栈

栈的理解

1. 一种操作受限的线性表结构，只允许在一端插入删除数据
2. 数组和链表可以在功能上代替栈，但是数组和链表过于灵活，暴露了太多操作接口，使用时比较不可控
3. 当一个数据集合只涉及在一端插入删除数据，且满足先进后出特性，应该首选栈这种数据结构
4. 入栈出栈的时间复杂度、空间复杂度都为 O(1)

空间复杂度是指除了原本的数据存储空间外，算法运行还需要的额外存储空间

栈的实现

顺序栈

1. 基于数组实现，可以自动扩容

2. 分析入栈操作

   • 时间复杂度最好为 O(1)，最坏为 O(n)
   • 每 k 次入栈，需要一次扩容，均摊时间复杂度为 O(1)

public class MyArrayStack
{
    Object[] baseArray;
    int count;//元素个数
    int depth;//数组大小

    public MyArrayStack(int depth)
    {
        this.depth = depth;
        baseArray = new Object[depth];
    }

    /**
     * 入栈，自动扩容
     *
     * @param o
     * @return
     */
    public boolean push(Object o)
    {
        if (count == depth)
        {//扩容
            depth *= 2;
            Object[] tempArray = new Object[depth];
            System.arraycopy(baseArray, 0, tempArray, 0, count);
            baseArray = tempArray;
        }
        baseArray[count] = o;
        count++;
        return true;
    }

    /**
     * 出栈
     *
     * @return
     */
    public Object pop()
    {
        if (count == 0)
        {
            return null;
        }
        Object o = baseArray[count - 1];
        count--;
        return o;
    }
}

链式栈

用链表实现，基于 java LinkedList 类

public class StackByLinkedList
{
    LinkedList baseList = new LinkedList();

    public void push(Object o)
    {
        baseList.addLast(o);
    }

    public Object pop()
    {
        return baseList.removeLast();
    }
}

栈的应用

函数调用栈

1. 操作系统给每个线程划分一块独立的内存空间，这个内存被组织成栈的形式，用来存储函数调用时的临时变量
2. 每进入一个函数就会将临时变量作为栈帧入栈，函数执行完成之后返回对应栈帧，先进后出

表达式求值

1. 操作数栈存放操作数，遇到数字压入操作数栈
2. 运算符栈存放运算符，遇到运算符时
   • 如果比栈顶运算符优先级高，则存入栈中
   • 如果比栈顶优先级相同或更低，则取出栈顶运算符，取出两个操作数，计算后将结果压入操作数栈，继续比较

括号匹配

1. 表达式包含三种括号，可以相互嵌套，两两对应为合法形式，类似{[}()]这种是不合法形式，使用栈来判断是否合法

2. 用栈来保存未匹配的的左括号，从左到右扫描，遇到右括号，与栈顶左括号比较，如果不匹配则不合法，如果匹配则继续

   public boolean isValid(String s)
   {
       Stack stack = new Stack();
       HashMap map = new HashMap();
       map.put(')', '(');
       map.put(']', '[');
       map.put('}', '{'); 
       Set left = map.keySet();
       Collection right = map.values();
       char[] chars = s.toCharArray();
       for (char c : chars)
       {
           if (stack.empty() && left.contains(c))
           {
               return false;
           }
           else if (!stack.empty() && left.contains(c))
           {
               if ((char) map.get(c) == (char) stack.peek())
               {
                   stack.pop();
               }
               else
               {
                   return false;
               }
           }
           else
           {
               stack.push(c);
           }
       }
       if (!stack.empty())
       {
           return false;
       }
       else
       {
           return true;
       }
   }