Java中的Deque

这个东西叫双端队列,很特殊,既可以当队列也可以当栈

public class NewTechTest {
    public static void main(String[] args) {
        Deque<Character> deque = new ArrayDeque<>();
        //栈的操作,压入栈
        deque.push('a');
        deque.push('b');
        deque.push('c');
        //输出栈顶和栈底
        System.out.println(deque.peek());
        System.out.println(deque.peekLast());
        //对于队列的操作,在队列的头部加入d,即栈底
        deque.add('d');
        deque.push('g');
        System.out.println(deque.peekLast());
        System.out.println(deque.peekFirst());
        //在栈底去掉
        deque.removeLast();
        System.out.println(deque.peekLast());
    }
}

运算结果:

c
a
d
g
a

相关应用:

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

有效字符串需满足：

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

示例 1:

输入: "()"
输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码:

public class IsValid {
    public static boolean isValid(String s) {
        Deque<Character> deque = new ArrayDeque<>();
        int n = s.length();
        for (int i=0;i<n;i++) {
            //System.out.println(s.charAt(i));
            if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
                deque.push(s.charAt(i));
            } else {
                if (deque.isEmpty()) {
                    //右括号在左括号前面
                    return false;
                } else if (s.charAt(i) == ')' && deque.peek() != '(') {
                    return false;
                } else if (s.charAt(i) == '}' && deque.peek() != '{') {
                    return false;
                } else if (s.charAt(i) == ']' && deque.peek() != '[') {
                    return false;
                }
                deque.pop();
            }
        }

        //System.out.println(deque.peek());
        return deque.isEmpty();
    }
}