栈与队列应用 - 元素码农

发布时间: 2025-03-21 15:34

↑

# 栈与队列应用

栈和队列是两种基本的线性数据结构，它们在计算机科学中有着广泛的应用。本文将详细介绍栈和队列的实现原理、特性以及实际应用场景。

## 栈（Stack）

### 基本概念

栈是一种后进先出（LIFO - Last In First Out）的数据结构，只允许在一端（栈顶）进行操作：
1. 压栈（Push）：将元素添加到栈顶
2. 出栈（Pop）：从栈顶移除元素
3. 查看栈顶（Peek/Top）：查看栈顶元素但不移除

### 栈的实现

```go
// 基于切片实现的栈
type Stack struct {
    items []interface{}
}

// 创建新栈
func NewStack() *Stack {
    return &Stack{items: make([]interface{}, 0)}
}

// 压栈
func (s *Stack) Push(item interface{}) {
    s.items = append(s.items, item)
}

// 出栈
func (s *Stack) Pop() (interface{}, error) {
    if s.IsEmpty() {
        return nil, errors.New("stack is empty")
    }
    item := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return item, nil
}

// 查看栈顶
func (s *Stack) Peek() (interface{}, error) {
    if s.IsEmpty() {
        return nil, errors.New("stack is empty")
    }
    return s.items[len(s.items)-1], nil
}

// 判断栈是否为空
func (s *Stack) IsEmpty() bool {
    return len(s.items) == 0
}
```

### 栈的应用场景

1. 函数调用栈
   - 保存函数的返回地址
   - 局部变量的存储
   - 参数传递

2. 表达式求值
   ```go
   // 中缀表达式转后缀表达式
   func infixToPostfix(expr string) string {
       precedence := map[string]int{
           "+": 1,
           "-": 1,
           "*": 2,
           "/": 2,
       }
       
       stack := NewStack()
       result := ""
       
       for _, char := range expr {
           if unicode.IsDigit(char) {
               result += string(char)
           } else if char == '(' {
               stack.Push(string(char))
           } else if char == ')' {
               for {
                   top, _ := stack.Peek()
                   if top == "(" {
                       stack.Pop()
                       break
                   }
                   val, _ := stack.Pop()
                   result += val.(string)
               }
           } else {
               for !stack.IsEmpty() {
                   top, _ := stack.Peek()
                   if top == "(" || precedence[string(char)] > precedence[top.(string)] {
                       break
                   }
                   val, _ := stack.Pop()
                   result += val.(string)
               }
               stack.Push(string(char))
           }
       }
       
       for !stack.IsEmpty() {
           val, _ := stack.Pop()
           result += val.(string)
       }
       
       return result
   }
   ```

3. 括号匹配
   ```go
   func isValidParentheses(s string) bool {
       stack := NewStack()
       pairs := map[rune]rune{
           ')': '(',
           '}': '{',
           ']': '[',
       }
       
       for _, char := range s {
           if char == '(' || char == '{' || char == '[' {
               stack.Push(char)
           } else {
               if stack.IsEmpty() {
                   return false
               }
               top, _ := stack.Pop()
               if top.(rune) != pairs[char] {
                   return false
               }
           }
       }
       
       return stack.IsEmpty()
   }
   ```

4. 撤销操作
   - 编辑器的撤销/重做功能
   - 游戏状态的回退

## 队列（Queue）

### 基本概念

队列是一种先进先出（FIFO - First In First Out）的数据结构，只允许：
1. 入队（Enqueue）：在队尾添加元素
2. 出队（Dequeue）：从队首移除元素
3. 查看队首（Front）：查看队首元素但不移除

### 队列的实现

```go
// 基于切片实现的队列
type Queue struct {
    items []interface{}
}

// 创建新队列
func NewQueue() *Queue {
    return &Queue{items: make([]interface{}, 0)}
}

// 入队
func (q *Queue) Enqueue(item interface{}) {
    q.items = append(q.items, item)
}

// 出队
func (q *Queue) Dequeue() (interface{}, error) {
    if q.IsEmpty() {
        return nil, errors.New("queue is empty")
    }
    item := q.items[0]
    q.items = q.items[1:]
    return item, nil
}

// 查看队首
func (q *Queue) Front() (interface{}, error) {
    if q.IsEmpty() {
        return nil, errors.New("queue is empty")
    }
    return q.items[0], nil
}

// 判断队列是否为空
func (q *Queue) IsEmpty() bool {
    return len(q.items) == 0
}
```

### 队列的应用场景

1. 任务调度
   ```go
   // 简单的任务调度器
   type Task struct {
       ID int
       Priority int
       Execute func()
   }
   
   type TaskScheduler struct {
       queue *Queue
   }
   
   func (ts *TaskScheduler) AddTask(task Task) {
       ts.queue.Enqueue(task)
   }
   
   func (ts *TaskScheduler) ProcessTasks() {
       for !ts.queue.IsEmpty() {
           task, _ := ts.queue.Dequeue()
           task.(Task).Execute()
       }
   }
   ```

2. 广度优先搜索
   ```go
   // 二叉树层序遍历
   type TreeNode struct {
       Val int
       Left *TreeNode
       Right *TreeNode
   }
   
   func levelOrder(root *TreeNode) [][]int {
       if root == nil {
           return nil
       }
       
       result := make([][]int, 0)
       queue := NewQueue()
       queue.Enqueue(root)
       
       for !queue.IsEmpty() {
           size := len(queue.items)
           level := make([]int, 0)
           
           for i := 0; i < size; i++ {
               node, _ := queue.Dequeue()
               current := node.(*TreeNode)
               level = append(level, current.Val)
               
               if current.Left != nil {
                   queue.Enqueue(current.Left)
               }
               if current.Right != nil {
                   queue.Enqueue(current.Right)
               }
           }
           
           result = append(result, level)
       }
       
       return result
   }
   ```

3. 缓冲区管理
   - 打印机队列
   - 网络数据包队列
   - 文件上传/下载队列

4. 消息队列
   - 异步处理
   - 解耦系统组件
   - 流量削峰

## 高级队列结构

### 1. 双端队列（Deque）

允许在两端进行插入和删除操作的队列：

```go
type Deque struct {
    items []interface{}
}

func (d *Deque) PushFront(item interface{}) {
    d.items = append([]interface{}{item}, d.items...)
}

func (d *Deque) PushBack(item interface{}) {
    d.items = append(d.items, item)
}

func (d *Deque) PopFront() (interface{}, error) {
    if d.IsEmpty() {
        return nil, errors.New("deque is empty")
    }
    item := d.items[0]
    d.items = d.items[1:]
    return item, nil
}

func (d *Deque) PopBack() (interface{}, error) {
    if d.IsEmpty() {
        return nil, errors.New("deque is empty")
    }
    item := d.items[len(d.items)-1]
    d.items = d.items[:len(d.items)-1]
    return item, nil
}
```

### 2. 优先队列

根据优先级进行出队的特殊队列，通常使用堆实现：

```go
type PriorityQueue struct {
    items []*Task
}

func (pq *PriorityQueue) Enqueue(task *Task) {
    pq.items = append(pq.items, task)
    pq.upHeapify(len(pq.items) - 1)
}

func (pq *PriorityQueue) Dequeue() (*Task, error) {
    if len(pq.items) == 0 {
        return nil, errors.New("queue is empty")
    }
    
    task := pq.items[0]
    pq.items[0] = pq.items[len(pq.items)-1]
    pq.items = pq.items[:len(pq.items)-1]
    pq.downHeapify(0)
    
    return task, nil
}
```

## 性能优化

1. 循环队列
   - 避免频繁的内存移动
   - 适用于固定大小的场景

2. 内存池
   - 减少内存分配
   - 提高性能

3. 批处理
   - 减少操作次数
   - 提高吞吐量

## 注意事项

1. 边界条件
   - 空栈/队列检查
   - 满栈/队列处理

2. 内存管理
   - 及时释放不需要的元素
   - 避免内存泄漏

3. 并发安全
   - 使用互斥锁
   - 考虑无锁实现

## 总结

栈和队列是两种重要的基础数据结构，它们在实际应用中有着广泛的用途。栈的后进先出特性使其适合处理具有回溯性质的问题，而队列的先进先出特性则适合处理需要按序处理的场景。理解这两种数据结构的原理和应用场景，对于设计高效的算法和系统架构都有重要帮助。在实际使用中，要根据具体需求选择合适的实现方式，并注意性能优化和安全性考虑。