LeetCode刷题Day10——栈和队列（栈和队列的实现，栈的使用）

/**
 * <pre>
 * 首先我们可以想到的方式就是维护两个栈一个存储，一个作为临时移动
 * 每次插入新的元素时，直接入存储的栈，当出队列时，首先把存储栈的所有元素依次移动到临时栈，移动完后临时栈的栈顶元素就是要出队列的元素
 * 此时将其弹出，随后再把元素依次移动回存储栈
 * 这样每次取出元素需要O(n)的时间复杂度
 * 仔细一想我们会发现元素出队列后其实没有必要再把临时栈的所有元素再返回存储栈，只要有元素出栈就从该栈取出即可，因为顺序都是正确的
 * 也就是维护一个插入栈和一个输出栈，每次输出的时候如果输出栈空就把输入栈的元素移动到输出栈，不空就直接输出输出栈的栈顶元素
 * 这样均摊的时间复杂度就是O(1)
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/11 12:18
 */
public class 用栈实现队列232 {
}
class MyQueue {
    Stack<Integer> inStack;
    Stack<Integer> outStack;
    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }
    public void push(int x) {
        inStack.push(x);
    }
    public int pop() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }
    public int peek() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }
    public boolean empty() {
        return inStack.empty() && outStack.empty();
    }
}

/**
 * <pre>
 * 两个队列模拟栈不能和两个栈模拟队列一样实现，因为栈的进出顺序是相反（先入后出）的，所以移动到输出栈后输出就是队列的顺序
 * 而队列的进出顺序是一致（先入先出），所以如果按栈的方法搬移到另一个队列，实质上两个队列顺序都是一样的，没有效果
 * 所以选择将一个队列作为临时队列辅助存储，以保证输入的元素在队列的头部
 * 我们只需要输入前先把队列中的元素移动到另一个队列保存，然后新元素入到原队列后再把临时队列元素重新加回原队列
 * 这样的话插入元素的时间复杂度就是O(n)
 * 
 * 也可以使用一个队列实现，记录下当前元素数量，将新元素入队之后，让队列不断将元素出队再入队，使得前面的元素移动到队列后免去，循环的次数为原本队列的元素数量
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/11 13:29
 */
public class 用队列实现栈225 {
}
class MyStack {
    Queue<Integer> queue;
    Queue<Integer> tmpQueue;
    public MyStack() {
        queue = new LinkedList<>();
        tmpQueue = new LinkedList<>();
    }
    public void push(int x) {
        while (!queue.isEmpty()) {
            tmpQueue.add(queue.remove());
        }
        queue.add(x);
        while (!tmpQueue.isEmpty()) {
            queue.add(tmpQueue.remove());
        }
    }
    public int pop() {
        return queue.remove();
    }
    public int top() {
        return queue.element();
    }
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * <pre>
 * 用栈维护
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/11 13:53
 */
public class 有效的括号20 {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        if (s.length() % 2 == 1) { // 奇数一定不满足
            return false;
        }
        for (int i=0; i<s.length(); i++) {
            if (stack.size() > s.length() - i) { // 剩下的括号数小于当前已存在的括号数一定不满足
                return false;
            }
            if (stack.empty()) {
                stack.push(s.charAt(i));
                continue;
            }
            Character peek = stack.peek();
            char c = s.charAt(i);
            if (peek == '(' && c == ')' || peek == '[' && c == ']' || peek == '{' && c == '}') {
                stack.pop();
            } else if (c == ')' || c == ']' || c == '}') { // 当前是右括号且不与上一个左括号匹配，则一定不满足
                return false;
            } else {
                stack.push(c);
            } 
        }
        return stack.empty();
    }
}

/**
 * <pre>
 * 用StringBuilder模拟栈，以方便最终转换为字符串
 * 也可以采用数组模拟，核心是利用指针指向栈顶元素，维护栈的思想
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/11 14:10
 */
public class 删除字符串中的所有相邻重复项1047 {
    public String removeDuplicates(String s) {
        StringBuilder stack = new StringBuilder();
        int top = -1;
        for (int i=0; i<s.length(); i++) {
            if (top == -1) {
                stack.append(s.charAt(i));
                top++;
            } else {
                if (stack.charAt(top) == s.charAt(i)) {
                    stack.deleteCharAt(top--);
                } else {
                    stack.append(s.charAt(i));
                    top++;
                } 
            }
        }
        return stack.toString();
    }
}