栈&队列.md

# 栈 / 队列

- 栈（stack）又名堆栈：

它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

![栈](https://user-gold-cdn.xitu.io/2019/10/13/16dc2f407ab8c3de?w=663&h=592&f=png&s=11155)

- 队列是一种特殊的线性表

特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

![队列](https://user-gold-cdn.xitu.io/2019/10/13/16dc2f407bb06dea?w=553&h=184&f=gif&s=5879)



### 带最小值操作的栈

这道面试题主要考察我们对于辅助栈的使用。

常见的辅助栈包括两种：

1. 辅助栈和数据栈同步

2. 辅助栈和数据栈不同步

我们这里采用辅助栈和数据栈同步的方式：
> 特点：编码简单，不用考虑一些边界情况，就有一点不好：辅助栈可能会存一些“不必要”的元素。

1. 辅助栈为空的时候，必须放入新进来的数；

2. 新来的数小于或者等于辅助栈栈顶元素的时候，才放入，特别注意这里“等于”要考虑进去，因为出栈的时候，连续的、相等的并且是最小值的元素要同步出栈；

3. 出栈的时候，辅助栈的栈顶元素等于数据栈的栈顶元素，才出栈。

> 总结一下：出栈时，最小值出栈才同步；入栈时，最小值入栈才同步。

```java
public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack; // 维护一个辅助栈，传入当前栈的最小值
    
    public MinStack() {
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }

    public void push(int number) {
        stack.push(number);
        if (minStack.isEmpty()) {
            minStack.push(number);
        } else {
            minStack.push(Math.min(number, minStack.peek()));
        }
    }

    public int pop() {
        minStack.pop();
        return stack.pop();
    }

    public int min() {
        return minStack.peek();
    }
}
```


### 有效括号

##### 思路：

1. 初始化栈 S。

2. 一次处理表达式的每个括号。

3. 如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处4理它，让我们简单地转到前面的 子表达式。

4. 如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。

5. 如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。

![有效括号](https://user-gold-cdn.xitu.io/2019/10/13/16dc2c162a48a203?w=2148&h=1072&f=png&s=121864)

```java
public boolean isValidParentheses(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (Character c : s.toCharArray()) {
        if ("({[".contains(String.valueOf(c))) {
            stack.push(c);
        } else {
            if (!stack.isEmpty() && isValid(stack.peek(), c)) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

private boolean isValid(char c1, char c2) {
    return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')
        || (c1 == '[' && c2 == ']');
}
```


### 用栈实现队列

##### 思路：

1. 思路是有两个栈，一个用来放数据（数据栈），一个用来辅助（辅助栈）。

2. 数据添加时，会依次压人栈，取数据时肯定会取栈顶元素，但我们想模拟队列的先进先出，所以就得取栈底元素，那么辅助栈就派上用场了

3. 把数据栈的元素依次弹出到辅助栈，但保留最后一个元素，最后数据栈就剩下了最后一个元素，直接把元素返回，这时数据栈已经没有了数据。

4. 最后呢，把辅助栈的元素依次压人数据栈，这样，我们成功取到了栈底元素。


```java
public class MyQueue {
    private Stack<Integer> outStack;
    private Stack<Integer> inStack;

    public MyQueue() {
       outStack = new Stack<Integer>();
       inStack = new Stack<Integer>();
    }
    
    private void in2OutStack(){
        while(!inStack.isEmpty()){
            outStack.push(inStack.pop());
        }
    }
    
    public void push(int element) {
        inStack.push(element);
    }

    public int pop() {
        if(outStack.isEmpty()){
            this.in2OutStack();
        }
        return outStack.pop();
    }

    public int top() {
        if(outStack.isEmpty()){
            this.in2OutStack();
        }
        return outStack.peek();
    }
}
```

### 逆波兰表达式求值 (后缀)

##### 思路：

1. 逆波兰表达式求解,定义一个栈辅助计算

2. 当遇到运算符"+"、"-"、"*"、"/"时,从栈中pop出两个数字计算,否则将数字入栈;

```java
public int evalRPN(String[] tokens) {
    Stack<Integer> s = new Stack<Integer>();
    String operators = "+-*/";
    for (String token : tokens) {
        if (!operators.contains(token)) {
            s.push(Integer.valueOf(token));
            continue;
        }
		// 这里有个坑
        int a = s.pop();
        int b = s.pop();
        // 先出的在运算符后
        // 后出的在运算符前
        if (token.equals("+")) {
            s.push(b + a);
        } else if(token.equals("-")) {
            s.push(b - a);
        } else if(token.equals("*")) {
            s.push(b * a);
        } else {
            s.push(b / a);
        }
    }
    return s.pop();
}
```


<br>
<br>

----