栈与队列 part-1 (Go) | 232 用栈实现队列、225 用队列实现栈

一、背景与问题

在算法和数据结构中，栈（Stack）和队列（Queue）是两种基础且重要的线性结构。它们的特性决定了不同的应用场景，但有时我们需要通过它们的组合来实现更复杂的逻辑。例如：

• 232题：用两个栈实现队列（LeetCode 232）
• 225题：用两个队列实现栈（LeetCode 225）

这两个问题的核心在于：如何通过一种结构模拟另一种结构的特性。理解其原理不仅有助于通过算法题，更能帮助我们在实际开发中设计高效的解决方案。

二、基本原理

1. 栈与队列的特性对比

2. 核心思想

• 栈实现队列：利用两个栈模拟队列的先进先出特性。通过将元素压入一个栈，再按需弹出到另一个栈，实现队列的顺序。
• 队列实现栈：利用两个队列模拟栈的后进先出特性。通过在入队时调整顺序，确保最后一个元素始终在队列末尾。

3. 性能分析

摊还时间复杂度：虽然单次操作可能涉及多次数据转移，但总体来看均摊复杂度仍为O(1)。

三、环境准备

1. Go语言环境

确保已安装Go 1.18+，并配置好环境变量。可以通过以下命令验证：

go version

2. 开发工具

• IDE：VS Code / GoLand
• 单元测试：go test
• 代码调试：go run + fmt.Printf

四、核心实现

1. 用栈实现队列（LeetCode 232）

1.1 数据结构设计

type MyQueue struct {
    stack1, stack2 []int
}

1.2 关键方法实现

Push（入队）：

func (q *MyQueue) Push(value int) {
    q.stack1 = append(q.stack1, value)
}

Pop（出队）：

func (q *MyQueue) Pop() (int, bool) {
    if len(q.stack2) == 0 {
        // 将stack1的数据转移到stack2
        for len(q.stack1) > 0 {
            q.stack2 = append(q.stack2, q.stack1[len(q.stack1)-1])
            q.stack1 = q.stack1[:len(q.stack1)-1]
        }
    }
    if len(q.stack2) == 0 {
        return 0, false // 队列为空
    }
    val := q.stack2[len(q.stack2)-1]
    q.stack2 = q.stack2[:len(q.stack2)-1]
    return val, true
}

Peek（查看队首元素）：

func (q *MyQueue) Peek() (int, bool) {
    if len(q.stack2) == 0 {
        for len(q.stack1) > 0 {
            q.stack2 = append(q.stack2, q.stack1[len(q.stack1)-1])
            q.stack1 = q.stack1[:len(q.stack1)-1]
        }
    }
    if len(q.stack2) == 0 {
        return 0, false
    }
    return q.stack2[len(q.stack2)-1], true
}

IsEmpty（判断是否为空）：

func (q *MyQueue) IsEmpty() bool {
    return len(q.stack1) == 0 && len(q.stack2) == 0
}

1.3 关键代码解释

• 栈转移逻辑：当stack2为空时，将stack1的元素全部弹出并压入stack2，实现队列的顺序。
• 时间复杂度：每次出队操作可能触发一次完整的栈转移，但每个元素最多被转移两次（stack1→stack2，stack2→stack1），因此摊还时间复杂度为O(1)。

1.4 常见错误

错误示例：直接弹出stack1的元素而不转移

func (q *MyQueue) Pop() (int, bool) {
    if len(q.stack1) == 0 {
        return 0, false
    }
    val := q.stack1[len(q.stack1)-1]
    q.stack1 = q.stack1[:len(q.stack1)-1]
    return val, true
}

错误原因：未处理stack2的空状态，导致队列顺序错误。

2. 用队列实现栈（LeetCode 225）

2.1 数据结构设计

type MyStack struct {
    queue1, queue2 []int
}

2.2 关键方法实现

Push（入栈）：

func (s *MyStack) Push(value int) {
    s.queue1 = append(s.queue1, value)
}

Pop（出栈）：

func (s *MyStack) Pop() (int, bool) {
    if len(s.queue1) == 0 {
        return 0, false // 栈为空
    }
    // 将除最后一个元素外的所有元素转移到 queue2
    for len(s.queue1) > 1 {
        s.queue2 = append(s.queue2, s.queue1[0])
        s.queue1 = s.queue1[1:]
    }
    val := s.queue1[0]
    s.queue1 = s.queue1[1:]
    s.queue2 = append(s.queue2, val)
    // 交换队列顺序
    s.queue1, s.queue2 = s.queue2, s.queue1
    return val, true
}

Peek（查看栈顶元素）：

func (s *MyStack) Peek() (int, bool) {
    if len(s.queue1) == 0 {
        return 0, false
    }
    // 将除最后一个元素外的所有元素转移到 queue2
    for len(s.queue1) > 1 {
        s.queue2 = append(s.queue2, s.queue1[0])
        s.queue1 = s.queue1[1:]
    }
    return s.queue1[0], true
}

IsEmpty（判断是否为空）：

func (s *MyStack) IsEmpty() bool {
    return len(s.queue1) == 0
}

2.3 关键代码解释

• 队列转移逻辑：每次出栈时，将queue1中除最后一个元素外的所有元素转移到queue2，确保最后一个元素始终在queue1的末尾。
• 时间复杂度：每次出栈操作可能触发一次完整的队列转移，但每个元素最多被转移两次（queue1→queue2，queue2→queue1），摊还时间复杂度为O(1)。

2.4 常见错误

错误示例：直接弹出队列的头部元素

func (s *MyStack) Pop() (int, bool) {
    if len(s.queue1) == 0 {
        return 0, false
    }
    val := s.queue1[0]
    s.queue1 = s.queue1[1:]
    return val, true
}

错误原因：未处理栈顶元素的顺序，导致弹出顺序错误。

五、完整案例

1. 任务调度系统（栈实现队列）

package main

import (
    "fmt"
)

type MyQueue struct {
    stack1, stack2 []int
}

func (q *MyQueue) Push(value int) {
    q.stack1 = append(q.stack1, value)
}

func (q *MyQueue) Pop() (int, bool) {
    if len(q.stack2) == 0 {
        for len(q.stack1) > 0 {
            q.stack2 = append(q.stack2, q.stack1[len(q.stack1)-1])
            q.stack1 = q.stack1[:len(q.stack1)-1]
        }
    }
    if len(q.stack2) == 0 {
        return 0, false
    }
    val := q.stack2[len(q.stack2)-1]
    q.stack2 = q.stack2[:len(q.stack2)-1]
    return val, true
}

func main() {
    q := &MyQueue{}
    q.Push(1)
    q.Push(2)
    q.Push(3)

    fmt.Println(q.Pop()) // 输出 1
    fmt.Println(q.Pop()) // 输出 2
    fmt.Println(q.Pop()) // 输出 3
}

2. 简单的计算器（队列实现栈）

package main

import (
    "fmt"
)

type MyStack struct {
    queue1, queue2 []int
}

func (s *MyStack) Push(value int) {
    s.queue1 = append(s.queue1, value)
}

func (s *MyStack) Pop() (int, bool) {
    if len(s.queue1) == 0 {
        return 0, false
    }
    for len(s.queue1) > 1 {
        s.queue2 = append(s.queue2, s.queue1[0])
        s.queue1 = s.queue1[1:]
    }
    val := s.queue1[0]
    s.queue1 = s.queue1[1:]
    s.queue2 = append(s.queue2, val)
    s.queue1, s.queue2 = s.queue2, s.queue1
    return val, true
}

func main() {
    s := &MyStack{}
    s.Push(3)
    s.Push(4)
    s.Push(5)

    fmt.Println(s.Pop()) // 输出 5
    fmt.Println(s.Pop()) // 输出 4
    fmt.Println(s.Pop()) // 输出 3
}

六、源码解析

1. 栈实现队列的源码分析

• 关键点：通过栈的后进先出特性，模拟队列的先进先出。
• 性能优化：避免重复转移，例如在Pop时只在stack2为空时转移元素。

2. 队列实现栈的源码分析

• 关键点：通过队列的先进先出特性，模拟栈的后进先出。
• 性能优化：每次出栈时仅处理最后一个元素，其余元素转移到另一个队列。

七、进阶使用

1. 多线程环境下的并发控制

在并发场景中，需要为每个结构添加锁：

type MyQueue struct {
    stack1, stack2 []int
    mu             sync.Mutex
}

2. 动态扩容与内存管理

对于大规模数据，可以引入动态扩容机制，例如：

func (q *MyQueue) Push(value int) {
    q.mu.Lock()
    defer q.mu.Unlock()
    q.stack1 = append(q.stack1, value)
    if len(q.stack1) > 1024 {
        q.stack1 = make([]int, 0, 1024)
    }
}

八、性能与工程实践

1. 性能优化策略

• 惰性删除：仅在需要时进行栈/队列转移，避免频繁操作。
• 预分配内存：使用make预分配内存，减少内存碎片。

2. 异常处理

• 空指针检查：在Pop和Peek时确保队列/栈不为空。
• 并发安全：在多线程环境中使用锁或原子操作。

3. 安全风险

• 数据竞争：多线程环境下未加锁会导致数据不一致。
• 内存泄漏：未正确释放不再使用的队列/栈内存。

九、常见问题与踩坑

1. 常见错误

• 顺序错误：未正确处理栈/队列的顺序，导致数据错乱。
• 性能瓶颈：频繁的栈/队列转移导致时间复杂度升高。

2. 解决办法

• 代码审查：确保每次操作都维护正确的顺序。
• 性能测试：使用压力测试工具验证性能表现。

十、最佳实践

1. 使用场景

• 栈实现队列：适合需要先进先出但无法直接使用队列的场景，如任务调度系统。
• 队列实现栈：适合需要后进先出但无法直接使用栈的场景，如缓存系统。

2. 避免使用场景

• 频繁随机访问：栈/队列不支持随机访问，可能需要其他数据结构（如数组）。
• 大数据量：大规模数据可能需要更高效的结构（如环形缓冲区）。

十一、总结

栈与队列的互换实现是算法中经典的思维训练，其核心在于理解两种结构的特性差异，并通过合理的数据转移策略模拟对方的行为。在实际开发中，这种设计常用于需要受限访问的数据处理场景。通过本篇文章，我们深入解析了两种实现方式的原理、代码实现、性能优化以及常见问题，为实际应用提供了可靠的指导。