41. Queue from Two Stacks

Origin: HackerRank Prep Kit #41

题目描述

用两个栈实现一个队列，支持 enqueue、dequeue、peek、size 操作，要求均摊 O(1) 时间。保持 FIFO 顺序。

示例

Example

Input:

Q = 6
operations = ['enqueue', 'enqueue', 'peek', 'dequeue', 'size', 'dequeue']
values = [5, 3, 0, 0, 0, 0]

Output: [5, 5, 1, 3]

Explanation:

• enqueue(5): inStack = [5]
• enqueue(3): inStack = [5, 3]
• peek(): outStack 空了，把 inStack 全部倒入 outStack → outStack = [3, 5]。front = 5。记录 5
• dequeue(): pop outStack → 5。记录 5
• size(): 0 + 1 = 1。记录 1
• dequeue(): pop outStack → 3。记录 3

非 enqueue 操作的结果按顺序返回：[5, 5, 1, 3]

约束

• 0 <= Q <= 100000
• operations[i] ∈ {‘enqueue’, ‘dequeue’, ‘peek’, ‘size’}
• 0 <= values[i] <= 10
• dequeue 和 peek 只在队列非空时出现

关键信息

• 两个栈：inStack（入队用）+ outStack（出队用）
• enqueue → push inStack
• dequeue/peek → outStack 空了就把 inStack 全部倒入 outStack，再操作
• size → inStack.length + outStack.length
• 均摊 O(1)：每个元素最多被 push/pop 各两次

Resolution

我的解法

function processRequestQueueOperations(operations: string[], values: number[]): number[] {
    const inStack: number[] = []
    const outStack: number[] = []
    const result: number[] = []
    const funcMap: { [k: string]: (v: number) => void } = {
        'enqueue': (v: number) => {
            inStack.push(v)
        },
        'dequeue': () => {
            if (outStack.length === 0) {
                while (inStack.length) {
                    outStack.push(inStack.pop()!)
                }
            }
            result.push(outStack.pop()!)
        },
        'peek': () => {
            if (outStack.length === 0) {
                while (inStack.length) {
                    outStack.push(inStack.pop()!)
                }
            }
            result.push(outStack[outStack.length - 1])
        },
        'size': () => {
            result.push(inStack.length + outStack.length)
        }
    }
    for (let i = 0; i < operations.length; i++) {
        const v = values[i]
        const op = operations[i]
        funcMap[op](v)
    }
    return result
}

解题思路

双栈实现队列（LeetCode 232）。两个栈配合：

• inStack：enqueue 时 push
• outStack：dequeue/peek 时，如果 outStack 空了就把 inStack 全部倒入 outStack（倒序变正序），再操作
• size：inStack.length + outStack.length

均摊 O(1)：每个元素最多被 push/pop 各两次（inStack 一次 + outStack 一次），所以 N 次操作总共 O(N)，均摊每次 O(1)。

踩坑

• 第一版取巧用数组 + shift 直接 AC，但 shift 是 O(n)，大数据量会超时
• 双栈版 bug：每次 dequeue/peek 都把 inStack 倒入 outStack，但 outStack 还有元素时不需要倒——只在 outStack 空了才倒

复杂度

• 时间：均摊 O(1) 每次操作
• 空间：O(n)，两个栈