精选算法面试-栈

一.简介

栈是一种特殊操作规则的数据结构-后进先出（FIFO）,这也是栈的最重要的一个特点，栈又叫堆栈（Stack）,栈有两个操作一个进栈（Push）,另一个出栈（Pop）。

二.示例

2.1 有效的括号

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

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 空字符串可被认为是有效字符串。

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        //标记匹配成对的字符串
        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        //存储括号前缀
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            //
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch))              {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

2.2 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）

实现 MyQueue 类

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明

• 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

public class MyQueue {
    //存储压栈的
    Stack<Integer> s1= new Stack<>();
    //处理弹栈
    Stack<Integer> s2= new Stack<>();
    int front = 0;
    //
    public void push(int x) {
        if(s1.isEmpty()) front = x;
        s1.push(x);
    }
    //把存储在s1数据都取出，压人获取队列的顺序
    public int pop() {
        if(s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        //弹栈并移除数据
        return s2.pop();
    }
    //弹栈数据，不移除
    public int peek() {
        if(!s2.isEmpty()){
            return s2.peek();
        }
        return front;
    }
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

参考

https://leetcode-cn.com/problems/implement-queue-using-stacks/

https://leetcode-cn.com/problems/valid-parentheses/