数据结构之栈

定义：

栈是一种线性集合，栈的元素是按照后进先出(LIFO)(Last in, first out)的方法进行处理的，最后进入栈中的元素最先被移出。

栈的抽象数据类型

package cn.iisheng.stack;

/**
 * @author iisheng
 * @date 2019/07/29 23:17:46
 */
public interface StackADT<T> {
    /**
     * 添加一个元素
     */
    void push(T element);

    /**
     * 移除并返回栈顶元素
     */
    T pop();

    /**
     * 返回且不移除栈顶元素
     */
    T peek();

    /**
     * 如果栈里面没有元素返回true
     */
    boolean isEmpty();

    /**
     * 返回栈中元素的总数
     */
    int size();

    /**
     * 返回一个代表当前栈的字符串
     */
    String toString();
}

用数组实现栈

栈的数组实现可以通过4个假设来设计：

• 该数组是一个对象引用的数组（其数据类型在栈实例化的时候确定）
• 栈底总是在数组的索引0处
• 栈的元素是按照顺序并连续地存储在数组中
• 有一个整数变量top，该变量保存了紧跟栈顶元素后的数组索引号

package cn.iisheng.stack;

import java.util.Arrays;

/**
 * @author iisheng
 * @date 2019/07/29 23:18:52
 */
public class ArrayStack<T> implements StackADT<T> {

    /**
     * 默认容量
     */
    private final int DEFAULT_CAPACITY = 100;

    /**
     * 栈顶元素下一个位置
     */
    private int top;

    /**
     * 存储栈元素的数组
     */
    private T[] stack;

    /**
     * 使用默认容量创建一个空栈
     */
    public ArrayStack() {
        top = 0;
        stack = (T[]) (new Object[DEFAULT_CAPACITY]);
    }

    /**
     * 使用指定容量创建一个空栈
     */
    public ArrayStack(int initialCapacity) {
        top = 0;
        stack = (T[]) (new Object[initialCapacity]);
    }

    /**
     * 添加一个元素
     * 确保 该数组不是满的
     * 把数组的top引用设置为要加入到栈中的对象
     * 增加top的值
     */
    @Override
    public void push(T element) {
        if (size() == stack.length) {
            expandCapacity();
        }
        stack[top] = element;
        top++;
    }

    private void expandCapacity() {
        stack = Arrays.copyOf(stack, stack.length * 2);
    }

    /**
     * 移除并返回栈顶元素
     * 确保 栈不为空
     * 减小top计数器
     * 设置一个临时引用等于stack[top]的元素
     * 设置stack[top]为空
     * 返回该临时引用
     */
    @Override
    public T pop() throws RuntimeException {
        if (isEmpty()) {
            throw new RuntimeException("The stack is empty.");
        }
        top--;
        T result = stack[top];
        stack[top] = null;

        return result;
    }

    /**
     * 返回且不移除栈顶元素
     */
    @Override
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("The stack is empty.");
        }
        return stack[top - 1];
    }

    /**
     * 如果栈为空返回true
     */
    @Override
    public boolean isEmpty() {
        return top == 0;
    }

    /**
     * 返回栈中元素数量
     */
    @Override
    public int size() {
        return top;
    }

    /**
     * 返回代表栈的字符串
     */
    @Override
    public String toString() {
        return Arrays.toString(stack);
    }
}

用链表实现栈

LinearNode<T>是链表一个节点的实现，点击查看源码

import cn.iisheng.common.LinearNode;

/**
 * @author iisheng
 * @date 2019/07/29 23:32:13
 */
public class LinkedStack<T> implements StackADT<T> {

    /**
     * 在栈中存储元素的数量
     */
    private int count;

    /**
     * 指向栈顶的指针
     */
    private LinearNode<T> top;

    public LinkedStack() {
        count = 0;
        top = null;
    }


    @Override
    public void push(T element) {
        LinearNode<T> temp = new LinearNode<>(element);

        temp.setNext(top);
        top = temp;
        count++;
    }

    @Override
    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty.");
        }

        T result = top.getElement();
        top = top.getNext();
        count--;

        return result;
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("The stack is empty.");
        }
        return top.getElement();
    }

    @Override
    public boolean isEmpty() {
        return count == 0;
    }

    @Override
    public int size() {
        return count;
    }
}

使用栈来计算后缀表达式

leetcode 224. Basic Calculator

public static int calculate(String s) {

       Stack<Integer> stack = new Stack<>();
       int operand = 0;
       int result = 0; // For the on-going result
       int sign = 1;  // 1 means positive, -1 means negative

       for (int i = 0; i < s.length(); i++) {

           char ch = s.charAt(i);
           if (Character.isDigit(ch)) {

               // Forming operand, since it could be more than one digit
               operand = 10 * operand + (int) (ch - '0');

           } else if (ch == '+') {

               // Evaluate the expression to the left,
               // with result, sign, operand
               result += sign * operand;

               // Save the recently encountered '+' sign
               sign = 1;

               // Reset operand
               operand = 0;

           } else if (ch == '-') {

               result += sign * operand;
               sign = -1;
               operand = 0;

           } else if (ch == '(') {

               // Push the result and sign on to the stack, for later
               // We push the result first, then sign
               stack.push(result);
               stack.push(sign);

               // Reset operand and result, as if new evaluation begins for the new sub-expression
               sign = 1;
               result = 0;

           } else if (ch == ')') {

               // Evaluate the expression to the left
               // with result, sign and operand
               result += sign * operand;

               // ')' marks end of expression within a set of parenthesis
               // Its result is multiplied with sign on top of stack
               // as stack.pop() is the sign before the parenthesis
               result *= stack.pop();

               // Then add to the next operand on the top.
               // as stack.pop() is the result calculated before this parenthesis
               // (operand on stack) + (sign on stack * (result from parenthesis))
               result += stack.pop();

               // Reset the operand
               operand = 0;
           }
       }
       return result + (sign * operand);
   }

使用栈来遍历树

二叉树的前序遍历（preorder travelsal）

从根节点开始，访问每一个节点及其孩子。（根 -> 左 -> 右）

leetcode 144. Binary Tree Preorder Traversal

List<Integer> result = new ArrayList<>();
       if (root == null) {
           return result;
       }
       Stack<TreeNode> stack = new Stack();
       // 根节点 最先入栈
       stack.push(root);
       while (!stack.isEmpty()) {
           root = stack.pop();
           // 遍历 根节点
           result.add(root.val);
           // 右节点先入栈 后遍历
           if (root.right != null) {
               stack.push(root.right);
           }
           // 左节点后入栈 先遍历
           if (root.left != null) {
               stack.push(root.left);
           }
       }
       return result;

二叉树的中序遍历（inorder travelsal）

从根节点开始，访问节点的左孩子，然后是该节点，再然后是任何剩余节点。（左 -> 根 -> 右）

leetcode 94. Binary Tree Inorder Traversal

public List<Integer> inorderTraversalWithStack(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                // 根先进 左孩子后进 左孩子先出 根后出
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            result.add(root.val);
            // 根 出  右孩子 进
            root = root.right;
        }
        return result;
    }

二叉树的后序遍历（inorder travelsal）

从根节点开始，访问节点的孩子，然后是该节点。（左 -> 右 -> 根）

leetcode 145. Binary Tree Postorder Traversal

public List<Integer> postorderTraversalWithStack(TreeNode root) {
      List<Integer> result = new ArrayList<>();
      if (root == null) {
          return result;
      }
      Stack<TreeNode> stack = new Stack();
      // 根先进
      stack.push(root);
      while (!stack.isEmpty()) {
          root = stack.pop();
          // 插在list第0位
          result.add(0, root.val);
          // 左孩子 先进 后出 最后插在 第0位
          if (root.left != null) {
              stack.push(root.left);
          }
          // 右孩子 后进 先出 先插在第0位
          if (root.right != null) {
              stack.push(root.right);
          }
      }
      return result;
  }

使用栈计算直方图最大面积

leetcode 84. Largest Rectangle in Histogram

public int largestRectangleArea(int[] heights) {
       Stack<Integer> st = new Stack<>();
       int maxArea = 0, n = heights.length;
       for (int i = 0; i < heights.length; i++) {
           while (!st.isEmpty() && heights[st.peek()] >= heights[i]) {
               int area = heights[st.pop()] * (st.isEmpty() ? i : i - st.peek() - 1);
               maxArea = Math.max(maxArea, area);
           }
           st.push(i);
       }

       while (!st.isEmpty()) {
           int area = heights[st.pop()] * (st.isEmpty() ? n : n - st.peek() - 1);
           maxArea = Math.max(maxArea, area);
       }
       return maxArea;
   }