栈的定义

先进后出的数据结构，先进去的数据在底部，最后取出，后进去的数据在顶部，最先被取出。（LIFO）类似于手枪的上膛操作，而与之相反的是队列。栈这种数据结构一般的使用场景有以下几种：

1. 编程语言中相关函数的调用
2. 操作系统中从用户态到内核态寄存器的保存
3. 网络消息的处理

栈的相关方法如下

栈的实现

package com.statck.demo;
/**
 * @author cherry
 * @version 1.0.0
 * @ClassName MyStack
 */
public class MyStack<T> {
    private T[] stack = (T[]) new Object[16];
    private int size;
    private final double LOAD_FACTOR = 2;
    public MyStack() {
        new MyStack(16);
    }
    public MyStack(int size) {
        this.size = size;
        this.stack = (T[]) new Object[size];
    }
    public void push(T item) {
        resize();
        stack[size++] = item;
    };
    public T pop() {
        if(isEmpty()) {
            return null;
        }
        resize();
        return stack[-- size];
    };
    public T peek() {
        if(isEmpty()) {
            return null;
        }
        return stack[size - 1];
    };
    public int size() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    private void resize() {
        T[] newStack = null;
        size = size == 0 ? 1 : size;
        if(size * LOAD_FACTOR >= stack.length) {
            newStack = (T[]) new Object[size * 2];
            for (int index = 0; index < stack.length; index++) {
                newStack[index] = stack[index];
            }
        }
        if (size * LOAD_FACTOR <= stack.length) {
            newStack = (T[]) new Object[stack.length / 2];
            for (int index = 0; index < newStack.length; index++) {
                newStack[index] = stack[index];
            }
        }
        stack = newStack;
    };
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder("[");
        for (int index = 0; index < size; index++) {
            builder.append(stack[index] + ",");
        }
        builder.setCharAt(builder.length() - 1, ']');
        return builder.toString();
    }
}

栈相关算法题

括号匹配问题

判断小括号是否完全匹配

给定一个字符串”()()((()())()”，让确定此字符串是否能够完全匹配，即一个”(“，对应一个”)”，能完全匹配返回true，不能则返回false。例如：”()” return true，”()(“ return false。
问题分析：

  1. 当字符串为空时则必定返回为false
  1. 当字符串个数为奇数个的时候，则必定有一个括号无法匹配，返回false
  1. 当一个"("进入时为压栈，而一个")"进入时为弹栈
  1. 需要注意第一个字符为")"，故这里将其排列后进行操作

public static boolean pattenBrackets(String brackets) {
    if(brackets == null || brackets.equalsIgnoreCase("")) {
        return false;
    }
    if(brackets.length() % 2 == 1) {
        return false;
    }

    String tempBrackets = "";
    for (int index = 0; index < brackets.length(); index++) {
        if(brackets.charAt(index) == ')') {
            tempBrackets += ")";
        }
    }
    brackets = brackets.replace(")", "") + tempBrackets;

    Stack<Character> bracketStack = new Stack<Character>();

    for (int index = 0; index < brackets.length(); index++) {
        char bracket = brackets.charAt(index);
        if(bracket == '(') {
            bracketStack.push(bracket);
        } else {
            if(bracketStack.isEmpty()) {
                return false;
            }
            bracketStack.pop();
        }
    }
    return bracketStack.isEmpty();
}

当然这里细心的你一定发现了，其实最后一步并不是特别需要使用栈来操作，这里只是为了让大家能够更好的清楚栈的特性，和使用方法，下面来看不使用栈的处理

public static boolean pattenBrackets(String brackets) {
    if(brackets == null || brackets.equalsIgnoreCase("")) {
        return false;
    }
    if(brackets.length() % 2 == 1) {
        return false;
    }

    String tempBrackets = "";
    for (int index = 0; index < brackets.length(); index++) {
        if(brackets.charAt(index) == ')') {
            tempBrackets += ")";
        }
    }
    brackets = brackets.replace(")", "") + tempBrackets;

    int leftBracketNumber = 0;

    for (int index = 0; index < brackets.length(); index++) {
        char bracket = brackets.charAt(index);
        if(bracket == '(') {
            leftBracketNumber ++;
        } else {
            if(leftBracketNumber <= 0) {
                return false;
            }
            leftBracketNumber --;
        }
    }
    return leftBracketNumber == 0;
}

判断括号是否完全匹配

给定一个只包括”()”, “[]”, “{}”，的字符串，判断字符串是否有效。有效字符串需满足：
1、左括号必须用相同类型的右括号闭合
2、左括号必须以正确的顺序闭合
3、注意空字符串可被认为是有效字符串

public static boolean pattenBrackets(String brackets) {
    Stack<Character> stack = new Stack<Character>();
    //for循环遍历栈
    for(int i=0;i<brackets.length();i++){
        char bracket = brackets.charAt(i);
        if(bracket == '('){
            stack.push(')');
        }else if(bracket == '{'){
            stack.push('}');
        }else if(bracket == '['){
            stack.push(']');
        }else if(stack.isEmpty() || bracket != stack.pop()){
            //判断是否匹配
            return false;
        }
    }
    return stack.isEmpty();
}

这里的关键点就是括号是成对出现的，当出了现了一个”(“则下一个必定是”)”，当出现顺序为”()[]{}”，第一个”(“进去后，则自己进去的元素为”)”，而第二个”)”，则走到了最后一个if，把”)”给弹了出来
对于”{[()]}”情况也是，则正好栈中的元素为：”}])”，而且正好满足了栈的先进后出的理念，对应的弹出顺序为”)”，”]”，”}”。

大鱼吃小鱼问题

在水中有许多的鱼，可以认为这些鱼停放在x轴上。再给定两个数组Size，Dir，Size[i]表示第i条鱼的大小。Dir[i]表示鱼的方向(0表示向左游，1表示向右游)。这两个数组分别表示鱼的大小和游动的方向，并且这两个数组的长度相等。这些鱼的行为都符合以下几个条件：
1、所有的鱼都同时开始游动，每次按照鱼的方向，都游动一个单位距离
2、当方向相对时，大鱼会吃掉小鱼
3、鱼的大小都不一样
例如：

size：[4, 2, 5, 3, 1] dir: [1, 1, 0, 0, 0] 输出：3

size：[5, 6, 8, 0, 4, 3, 1, 6] dir: [1, 1, 0, 1, 1, 1, 1, 0] 输出：2

private static int fishRemove01(int[] fishes, int[] fishesDirection) {
    // 警戒值判断
    int fishNum = fishes.length;
    if (fishes.length != fishesDirection.length) {
        return 0;
    }
    if(fishNum <= 1) {
        return fishNum;
    }

    // 定义鱼的游向
    int left = 0;
    int right = 1;

    Stack<Integer> fishesPool = new Stack<Integer>();
    Stack<Integer> fishesDirectionPool = new Stack<Integer>();

    for (int index = 0; index < fishNum; index++) {
        // 获取当前鱼的游向和大小
        int curFishSize = fishes[index];
        int curFishDirection = fishesDirection[index];

        // 是否能吃 对于能吃的鱼不入栈
        boolean hasEat = false;

        // 循环条件为，鱼池不为空且游向是对立的
        while (!fishesPool.isEmpty() && fishesDirectionPool.peek() == right && curFishDirection == left) {
            // 当池中鱼能吃进来的鱼则循环退出，否则进来的鱼一直吃下去
            if(fishesPool.peek() > curFishSize) {
                hasEat = true;
                break;
            }
            fishesPool.pop();
            fishesDirectionPool.pop();
        }
        if (!hasEat) {
            fishesPool.push(curFishSize);
            fishesDirectionPool.push(curFishDirection);
        }
    }
    return fishesPool.size();
}

单调栈

单调栈指栈中的元素必须是按照升序排列的栈或者是降序排列的栈，对于这两种单调栈，还有对应的别名，升序排列的栈为递增栈，降序排列的栈为递减栈
以下是递增栈：小数在栈顶，大数在栈底

以下是递减栈：小数在栈底，大数在栈顶

单调栈相关算法题

找出数组中右边比我小的元素

一个整数数组A，找到每个元素：右边第一个比我小的下标位置，没有则用-1表示，

例如： 输入：[5, 2] 输出：[1, -1] 解释：因为元素5的右边离我最近且比我小的位置应该是A[1]，而元素2没有比他小的元素则用-1表示

private static int[] findRightSmall(int[] numbers) {
    int[] numbersResult = new int[numbers.length];
    if(numbers == null || numbers.length <= 1) {
        numbersResult[0] = -1;
        return numbersResult;
    }
    // 用于存放每个每个数字的索引
    Stack<Integer> numbersIndex = new Stack<Integer>();
    for (int index = 0; index < numbers.length; index++) {
        int number = numbers[index];
        // 当栈不为空且左边数字大于右边数字，则记录右边的索引，并且弹出左边的索引
        while (!numbersIndex.isEmpty() && numbers[numbersIndex.peek()] > number) {
            numbersResult[numbersIndex.peek()] = index;
            numbersIndex.pop();
        }
        // 不满足条件则压栈
        numbersIndex.push(index);
    }
    // 对于没有找到右边比他小的数字记-1
    while (!numbersIndex.isEmpty()) {
        numbersResult[numbersIndex.peek()] = -1;
        numbersIndex.pop();
    }
    return numbersResult;
}