【每日一题】【栈和队列、双端队列】20. 有效的括号/NC52 有效括号序列-211127/220126

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

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

//stack不是抽象类

class Solution {

    public boolean isValid(String s) {

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

        for(Character c : s.toCharArray()) {

            if(c == '{') {

                stack.push('}');

            } else if(c == '(') {

                stack.push(')');

            } else if(c == '[') {

                stack.push(']');

            } else if(stack.isEmpty() || c != stack.pop()) {

                return false;

            }

        }

        return stack.isEmpty(); //不是直接return true，而是看栈是否为空

    }

}

同上解法

import java.util.*;

public class Solution {

    public boolean isValid (String s) {

        char[] arr = s.toCharArray();

        //栈的初始化，后进先出

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

        char str = ' ';

        for(char c : arr) {

            if (!stack.isEmpty()) {

                str = stack.peek();

            }

            if(c == '[') {

                stack.add(']');

            } else if(c == '{') {

                stack.add('}');

            } else if(c == '(') {

                stack.add(')');

            } else if(!stack.isEmpty() && c == stack.peek()) {

                stack.pop();

            } else {

                return false;

            }

        }

        return stack.isEmpty();

    }

}

注意：

1、栈

初始化：Stack<E> stack = new Stack<>();

出栈：stack.pop() 或 stack.remove(stack.size() - 1)

入栈：stack.push(2) 或 stack.add(1)

栈顶：stack.peek()

2、队列

初始化：Queue<E> queue = new LinkedList<>();

入队：queue.offer(2) 或 queue.add(3)

出队：queue.poll() 或 queue.remove()

查看队头元素：queue.peek()

3、双端队列

初始化：

Deque<Integer> deque = new ArrayDeque<>();
Deque<Integer> deque1 = new LinkedList<>();

入队：

deque1.addFirst(1);
deque1.addLast(2);
deque1.offerFirst(3);
deque1.offerLast(4);

出队：

deque1.removeFirst()

deque1.removeLast()

deque1.pollFirst()

deque1.pollLast()

查看队头元素：

deque1.peekFirst()

deque1.peekLast()

4、测试

public static void main(String[] args) {

        //System.out.println(isValid("([])"));

        //testQueue();

        testStack();

    }

    public static void testDeque() {

        //双端队列

        Deque<Integer> deque = new ArrayDeque<>();

        Deque<Integer> deque1 = new LinkedList<>();

        //入队

        deque1.addFirst(1);

        deque1.addLast(2);

        deque1.offerFirst(3);

        deque1.offerLast(4);

        System.out.println(deque1.peekFirst());

        System.out.println(deque1.peekLast());

        //出队

        System.out.println(deque1.removeFirst());

        System.out.println(deque1.removeLast());

        System.out.println(deque1.pollFirst());

        System.out.println(deque1.pollLast());

    }

    public static void testQueue() {

        Queue<Integer> queue = new LinkedList<>();

        queue.offer(1);

        queue.offer(2);

        queue.add(3);

        System.out.println(queue.peek());

        System.out.println(queue.poll());

        System.out.println(queue.peek());

        System.out.println(queue.remove());

        System.out.println(queue.peek());

    }

    public static void testStack() {

        Stack<Integer> stack = new Stack<>();

        stack.add(1);

        stack.push(2);

        stack.push(3);

        System.out.println(stack.peek());

        System.out.println(stack.pop());

        System.out.println(stack.peek());

        System.out.println(stack.remove(stack.size() - 1));

        System.out.println(stack.peek());

    }

public static void testDeque() {
    //双端队列
Deque<Integer> deque = new ArrayDeque<>();
    Deque<Integer> deque1 = new LinkedList<>();
    //入队
deque1.addFirst(1);
    deque1.addLast(2);
    deque1.offerFirst(3);
    deque1.offerLast(4);
    System.out.println(deque1.peekFirst());
    System.out.println(deque1.peekLast());
    //出队
System.out.println(deque1.removeFirst());
    System.out.println(deque1.removeLast());
    System.out.println(deque1.pollFirst());
    System.out.println(deque1.pollLast());

}

【每日一题】【栈和队列、双端队列】20. 有效的括号/NC52 有效括号序列-211127/220126的相关教程结束。