几道和「堆栈、队列」有关的面试算法题

题目一:有效的括号

问题描述

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

解题思路

这道题让我们验证输入的字符串是否为括号字符串,包括大括号,中括号和小括号。

这里我们使用

  • 遍历输入字符串
  • 如果当前字符为左半边括号时,则将其压入栈中
  • 如果遇到右半边括号时,分类讨论:
  • 1)如栈不为空且为对应的左半边括号,则取出栈顶元素,继续循环
  • 2)若此时栈为空,则直接返回 false
  • 3)若不为对应的左半边括号,反之返回 false

动画演示

20. Valid Parentheses

20. Valid Parentheses

代码实现

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            if (stack.size() == 0) {
                stack.push(aChar);
            } else if (isSym(stack.peek(), aChar)) {
                stack.pop();
            } else {
                stack.push(aChar);
            }
        }
        return stack.size() == 0;
    }

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

题目二:用两个栈实现队列

问题描述

用两个栈来实现一个队列,完成队列的 Push 和 Pop 操作。

解题思路

in 栈用来处理入栈(push)操作,out 栈用来处理出栈(pop)操作。一个元素进入 in 栈之后,出栈的顺序被反转。当元素要出栈时,需要先进入 out 栈,此时元素出栈顺序再一次被反转,因此出栈顺序就和最开始入栈顺序是相同的,先进入的元素先退出,这就是队列的顺序。

  • push 元素时,始终是进入栈,pop 和 peek 元素时始终是走出栈。
  • pop 和 peek 操作,如果出栈为空,则需要从入栈将所有元素移到出栈,也就是调换顺序,比如开始push的顺序是 3-2-1,1 是最先进入的元素,则到出栈的顺序是 1-2-3,那 pop 操作拿到的就是 1,满足了先进先出的特点。
  • pop 和 peek 操作,如果出栈不为空,则不需要从入栈中移到数据到出栈。

代码实现

```java
Stack in = new Stack();
Stack out = new Stack();

public void push(int node) {
in.push(node);
}

public int pop() throws Exception {
if (out.isEmpty())
while (!in.isEmpty())
out.push(in.pop());

if (out.isEmpty())
    throw new Exception("queue is empty");
top Created with Sketch.