用栈实现队列

将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。

每次 pop 或 peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    //将元素 x 推到队列的末尾
    public void push(int x) {
        stackIn.push(x);
    }
    //int pop() 从队列的开头移除并返回元素
    public int pop() {
        in2out();
        return stackOut.pop();
    }

    //int peek() 返回队列开头的元素
    public int peek() {
        //如果为空，直接压栈，不为空，直接返回栈顶元素
        in2out();
        return stackOut.peek();
    }
    //boolean empty() 如果队列为空，返回 true ；否则，返回 false
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    //抽取公共方法
    private void in2out() {
        if (stackOut.isEmpty()){
            while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
        }
    }
}

用队列实现栈

/**
 * 使用两个队列实现栈的数据结构
 * 核心思想：通过队列的先进先出(FIFO)特性模拟栈的后进先出(LIFO)特性
 */
class MyStack {
    // 主队列，用于存储栈中的元素
    Queue<Integer> queue1;
    // 辅助队列，用于在push操作时临时存储元素
    Queue<Integer> queue2;

    /**
     * 初始化栈结构
     * 创建两个空队列
     */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    /**
     * 将元素x压入栈顶
     * 实现思路：
     * 1. 先将新元素放入辅助队列queue2
     * 2. 将主队列queue1中的所有元素依次出队并加入queue2
     * 3. 交换queue1和queue2的引用，使得queue1始终是主队列
     * @param x 要压入栈的元素
     */
    public void push(int x) {
        // 1. 先将新元素放入辅助队列
        queue2.offer(x);

        // 2. 将主队列中的所有元素转移到辅助队列
        // 这样新元素就会位于队列前端(相当于栈顶)
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll()); //队列1的元素到队列2
        }

        // 3. 交换两个队列的引用
        // 这样queue1始终保存当前栈的所有元素，且新元素在队列前端
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    /**
     * 弹出栈顶元素并返回
     * 由于push操作已经保证了新元素在队列前端，
     * 所以直接从queue1出队即可
     * @return 栈顶元素
     */
    public int pop() {
        return queue1.poll();
    }

    /**
     * 获取栈顶元素但不弹出
     * 直接返回queue1的队首元素
     * @return 栈顶元素
     */
    public int top() {
        return queue1.peek();
    }

    /**
     * 判断栈是否为空
     * 只需检查queue1是否为空
     * @return 如果栈为空返回true，否则返回false
     */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

有效的括号

class Solution {
    //字典
    Map<Character, Character> dict;

    public Solution() {
        dict = new HashMap<>();
        dict.put('(',')');
        dict.put('[',']');
        dict.put('{','}');
    }

    public boolean isValid(String s) {
        // 使用双端队列模拟栈（ArrayDeque 比 Stack 性能更好）
        Deque<Character> stack = new ArrayDeque<>();
        if (s.length() % 2 != 0 || s.isEmpty())return false;
        for (int i = 0; i < s.length(); i++){
            char  c = s.charAt(i);
            //// 如果是左括号，压入对应的右括号到栈中
            if (dict.containsKey(c)){
                stack.push(dict.get(c));
            //// 如果是右括号，检查是否与栈顶匹配
            }else if (dict.get(c)!=stack.pop()){
                return false;
            }
        }
        return stack.isEmpty();
    }
}

删除字符串中的所有相邻重复项

图解思路是一样的,但是注意题意好像是需要从前往后遍历，没有匹配的就丢进栈，和栈顶元素匹配就出栈，然后指针下移。

class Solution {
    Stack<Character> stack;
    StringBuilder sb;

    public Solution() {
        stack = new Stack<>();
        /// stack.toString();返回的是[a,b,c]这样的而不是[abc]，所以拼接一下
        sb = new StringBuilder();
    }

    public String removeDuplicates(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (!stack.isEmpty() && stack.peek().equals(s.charAt(i))) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }
        for (Character c : stack) {
            sb.append(c);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Solution().removeDuplicates("abbaca"));
    }
}