队列

问题描述

队列是一种先进先出(FIFO)的数据结构。
在C++中为queue，Java中为Queue接口，Python中为queue模块。
它提供了在一端插入另一端删除的操作能力。

基本概念

特点

1. 先进先出
2. 只能访问队首和队尾
3. 支持入队和出队
4. 可以检查队空
5. 可以查看队首元素

代码实现

1. C++ Queue

#include <iostream>
#include <queue>
using namespace std;

int main() {
    // 创建队列
    queue<int> q;
    
    // 入队
    q.push(1);
    q.push(2);
    q.push(3);
    
    // 查看队首元素
    cout << "Front: " << q.front() << endl;  // 输出：1
    
    // 查看队尾元素
    cout << "Back: " << q.back() << endl;   // 输出：3
    
    // 出队
    q.pop();
    cout << "After pop, front: " << q.front() << endl;  // 输出：2
    
    // 检查队空
    cout << "Is empty: " << (q.empty() ? "yes" : "no") << endl;
    
    // 获取队列大小
    cout << "Size: " << q.size() << endl;
    
    // 清空队列
    while (!q.empty()) {
        cout << q.front() << " ";  // 输出队列中元素
        q.pop();
    }
    cout << endl;
    
    return 0;
}

2. Java Queue

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        // 创建队列
        Queue<Integer> queue = new LinkedList<>();
        
        // 入队
        queue.offer(1);  // 或使用add()，但offer更安全
        queue.offer(2);
        queue.offer(3);
        
        // 查看队首元素
        System.out.println("Front: " + queue.peek());  // 输出：1
        
        // 出队
        queue.poll();  // 或使用remove()，但poll更安全
        System.out.println("After poll, front: " + queue.peek());  // 输出：2
        
        // 检查队空
        System.out.println("Is empty: " + queue.isEmpty());
        
        // 获取队列大小
        System.out.println("Size: " + queue.size());
        
        // 清空队列
        while (!queue.isEmpty()) {
            System.out.print(queue.poll() + " ");  // 输出队列中元素
        }
        System.out.println();
    }
}

3. Python Queue

from queue import Queue

# 创建队列
q = Queue()

# 入队
q.put(1)
q.put(2)
q.put(3)

# 查看队列大小
print("Size:", q.qsize())  # 注意：在某些系统上可能不可靠

# 检查队空
print("Is empty:", q.empty())

# 出队并打印元素
while not q.empty():
    print(q.get(), end=" ")  # 输出队列中元素
print()

# 也可以使用列表模拟队列
class Queue:
    def __init__(self):
        self.items = []
    
    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)  # 注意：这是O(n)操作
        raise IndexError("dequeue from empty queue")
    
    def front(self):
        if not self.is_empty():
            return self.items[0]
        raise IndexError("front from empty queue")
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

# 使用collections.deque更高效
from collections import deque

# 创建双端队列
dq = deque()

# 入队
dq.append(1)      # 从右端入队
dq.appendleft(2)  # 从左端入队

# 出队
dq.pop()      # 从右端出队
dq.popleft()  # 从左端出队

应用场景

1. 任务调度
2. 消息队列
3. 缓冲区管理
4. 广度优先搜索
5. 打印机队列

注意事项

1. 队列容量
2. 空队列操作
3. 内存管理
4. 性能考虑
5. 线程安全性

常见示例

1. 层序遍历

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int size = q.size();
        vector<int> level;
        
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(level);
    }
    return result;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

def level_order(root: TreeNode) -> List[List[int]]:
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level = []
        size = len(queue)
        
        for _ in range(size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result