题解 | #有效括号序列#

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        int sLen = s.length();
        if (sLen % 2 == 1) return false;
        // write code here
        LinkedListStack<Character> stack = new LinkedListStack<>();

        for (int i = 0; i < sLen; ++i) {
            Character top = stack.top();
            Character charAt = s.charAt(i);
            if (top != null && ((top == '(' && charAt == ')') || (top == '[' && charAt == ']') || (top == '{' && charAt == '}'))) {
                stack.pop();
            }
            else {
                if (charAt == ')' || charAt == ']' || charAt == '}') { return false; }
                stack.push(charAt);
            }
        }
        return stack.isEmpty();
    }
}

/////////////////////链表
/**
 * 栈的实现 -- 链表
 * 优点: 使用灵活方便, 只要有需要的时候才会申请空间
 * 缺点: 除了要存储元素外, 还需要额外存储指针(引用)信息
 * @param <T>
 */
class Node<T> {
    T data;
    Node<T> next;
}

class LinkedListStack<T> {
    private Node<T> pHead;

    public LinkedListStack() {
        pHead = new Node<T>();
        pHead.data = null;
        pHead.next = null;
    }

    public int size() {
        int size = 0;
        Node<T> cur = pHead.next;

        while (cur != null) {
            cur = cur.next;
            size++;
        }
        return size;
    }


    public T pop() {
        Node<T> popNode = pHead.next;
        if (popNode == null) return null;
        pHead.next = popNode.next;
        return popNode.data;
    }

    public T top() {
        Node<T> topNode = pHead.next;
        if (topNode == null) return null;
        return topNode.data;
    }

    public void push(T e) {
        Node<T> tlNode = new Node<>();
        tlNode.data = e;
        tlNode.next = pHead.next;
        pHead.next = tlNode;
    }

    public boolean isEmpty() {
        return pHead.next == null;
    }


}
/////////////////////链表