一、队列：先进先出的线性数据结构

1.1 队列的基本概念与特性

队列（Queue）是一种先进先出（First-In-First-Out, FIFO）的线性数据结构，只允许在队尾（rear）进行插入操作，在队首（front）进行删除操作。这种特性使得队列在各种需要顺序处理的场景中有着广泛的应用。

队列的核心操作：

enqueue(入队)：将元素添加到队尾
dequeue(出队)：移除并返回队首元素
peek(查看)：返回队首元素但不移除
isEmpty：检查队列是否为空
size：返回队列中元素数量

1.2 队列的ADT（抽象数据类型）定义

public interface Queue<T> {
    void enqueue(T element);    // 入队操作
    T dequeue();                // 出队操作
    T peek();                   // 查看队首元素
    boolean isEmpty();          // 判断队列是否为空
    int size();                 // 获取队列大小
}

二、队列的实现方式

2.1 基于数组的实现（循环队列）

public class ArrayQueue<T> implements Queue<T> {
    private static final int DEFAULT_CAPACITY = 10;
    private T[] elements;
    private int front; // 队首指针
    private int rear;  // 队尾指针
    private int size;  // 元素数量
    
    public ArrayQueue() {
        this(DEFAULT_CAPACITY);
    }
    
    @SuppressWarnings("unchecked")
    public ArrayQueue(int capacity) {
        elements = (T[]) new Object[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }
    
    @Override
    public void enqueue(T element) {
        if (size == elements.length) {
            resize(2 * elements.length); // 动态扩容
        }
        
        rear = (rear + 1) % elements.length; // 循环队列
        elements[rear] = element;
        size++;
    }
    
    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        
        T element = elements[front];
        elements[front] = null; // 避免内存泄漏
        front = (front + 1) % elements.length; // 循环队列
        size--;
        
        // 缩容机制
        if (size > 0 && size == elements.length / 4) {
            resize(elements.length / 2);
        }
        
        return element;
    }
    
    @Override
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return elements[front];
    }
    
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
    
    @Override
    public int size() {
        return size;
    }
    
    private void resize(int newCapacity) {
        @SuppressWarnings("unchecked")
        T[] newElements = (T[]) new Object[newCapacity];
        
        for (int i = 0; i < size; i++) {
            int index = (front + i) % elements.length;
            newElements[i] = elements[index];
        }
        
        elements = newElements;
        front = 0;
        rear = size - 1;
    }
}

2.2 基于链表的实现

public class LinkedQueue<T> implements Queue<T> {
    private static class Node<T> {
        T data;
        Node<T> next;
        
        Node(T data) {
            this.data = data;
        }
    }
    
    private Node<T> front;
    private Node<T> rear;
    private int size;
    
    public LinkedQueue() {
        front = null;
        rear = null;
        size = 0;
    }
    
    @Override
    public void enqueue(T element) {
        Node<T> newNode = new Node<>(element);
        
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }
    
    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        
        T element = front.data;
        front = front.next;
        
        if (front == null) {
            rear = null;
        }
        
        size--;
        return element;
    }
    
    @Override
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return front.data;
    }
    
    @Override
    public boolean isEmpty() {
        return front == null;
    }
    
    @Override
    public int size() {
        return size;
    }
}

三、队列与栈的全面对比

3.1 基本特性对比

特性	队列 (Queue)	栈 (Stack)
基本原则	先进先出 (FIFO)	后进先出 (LIFO)
插入操作	在队尾 (rear) 进行	在栈顶 (top) 进行
删除操作	在队首 (front) 进行	在栈顶 (top) 进行
查看操作	查看队首元素	查看栈顶元素
典型应用	任务调度、消息传递	函数调用、撤销操作

3.2 时间复杂度对比

操作	队列	栈	说明
插入	O(1)	O(1)	两者都支持常数时间插入
删除	O(1)	O(1)	两者都支持常数时间删除
查看	O(1)	O(1)	查看队首/栈顶元素
随机访问	O(n)	O(n)	都不支持高效随机访问
搜索	O(n)	O(n)	都需要遍历查找元素

3.3 内存布局对比

队列的内存布局：

[元素0][元素1][元素2][元素3][元素4]...
↑           ↑
front       rear
循环数组或链表实现，保持FIFO顺序

栈的内存布局：

[元素0][元素1][元素2][元素3][元素4]...
↑
top
数组或链表实现，保持LIFO顺序

3.4 优缺点总结

队列的优点：

保证处理顺序，先进先出
适合任务调度和消息传递场景
可以高效实现生产者-消费者模式

队列的缺点：

随机访问效率低
实现相对复杂（特别是循环队列）
不适合需要后进先出处理的场景

栈的优点：

实现简单，操作高效
适合递归、回溯等算法
内存管理效率高

栈的缺点：

访问受限，只能操作栈顶元素
不适合需要先进先出处理的场景
深度过大时可能栈溢出

四、队列的核心算法与应用

4.1 广度优先搜索（BFS）

public class GraphBFS {
    private Map<Integer, List<Integer>> graph;
    
    public GraphBFS() {
        graph = new HashMap<>();
    }
    
    public void addEdge(int u, int v) {
        graph.putIfAbsent(u, new ArrayList<>());
        graph.get(u).add(v);
    }
    
    public void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedQueue<>();
        
        queue.enqueue(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            int node = queue.dequeue();
            System.out.print(node + " ");
            
            if (graph.containsKey(node)) {
                for (int neighbor : graph.get(node)) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.enqueue(neighbor);
                    }
                }
            }
        }
    }
}
// 使用示例
GraphBFS graph = new GraphBFS();
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.bfs(0); // 输出: 0 1 2 3 4

4.2 二叉树层次遍历

public class BinaryTreeLevelOrder {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedQueue<>();
        queue.enqueue(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.dequeue();
                currentLevel.add(node.val);
                
                if (node.left != null) {
                    queue.enqueue(node.left);
                }
                if (node.right != null) {
                    queue.enqueue(node.right);
                }
            }
            
            result.add(currentLevel);
        }
        
        return result;
    }
}

五、队列的变种与高级实现

5.1 双端队列（Deque）

public interface Deque<T> {
    void addFirst(T element);
    void addLast(T element);
    T removeFirst();
    T removeLast();
    T getFirst();
    T getLast();
    boolean isEmpty();
    int size();
}
// 使用Java内置Deque
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);    // 前端添加
deque.addLast(2);     // 后端添加
int first = deque.removeFirst(); // 前端移除
int last = deque.removeLast();   // 后端移除

5.2 优先级队列（Priority Queue）

public class TaskScheduler {
    static class Task implements Comparable<Task> {
        String name;
        int priority;
        LocalDateTime scheduledTime;
        
        Task(String name, int priority, LocalDateTime scheduledTime) {
            this.name = name;
            this.priority = priority;
            this.scheduledTime = scheduledTime;
        }
        
        @Override
        public int compareTo(Task other) {
            // 先按优先级，再按时间排序
            if (this.priority != other.priority) {
                return Integer.compare(other.priority, this.priority); // 优先级高的在前
            }
            return this.scheduledTime.compareTo(other.scheduledTime);
        }
    }
    
    private PriorityQueue<Task> taskQueue;
    
    public TaskScheduler() {
        taskQueue = new PriorityQueue<>();
    }
    
    public void scheduleTask(Task task) {
        taskQueue.offer(task);
    }
    
    public Task getNextTask() {
        return taskQueue.poll();
    }
}

5.3 阻塞队列（Blocking Queue）

public class ProducerConsumerExample {
    private BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(10);
    
    class Producer implements Runnable {
        public void run() {
            try {
                for (int i = 0; i < 100; i++) {
                    queue.put(i); // 队列满时阻塞
                    System.out.println("Produced: " + i);
                    Thread.sleep(100);
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }
    
    class Consumer implements Runnable {
        public void run() {
            try {
                while (true) {
                    Integer value = queue.take(); // 队列空时阻塞
                    System.out.println("Consumed: " + value);
                    Thread.sleep(200);
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }
}

六、队列与栈的实际应用场景

6.1 队列的典型应用场景

场景1：消息队列系统

public class MessageQueue {
    private Queue<String> queue;
    private final Object lock = new Object();
    
    public MessageQueue() {
        queue = new LinkedQueue<>();
    }
    
    public void produce(String message) throws InterruptedException {
        synchronized (lock) {
            queue.enqueue(message);
            lock.notifyAll(); // 通知消费者
        }
    }
    
    public String consume() throws InterruptedException {
        synchronized (lock) {
            while (queue.isEmpty()) {
                lock.wait(); // 等待消息
            }
            return queue.dequeue();
        }
    }
}

场景2：线程池任务调度

public class SimpleThreadPool {
    private BlockingQueue<Runnable> taskQueue;
    private List<WorkerThread> workers;
    
    public SimpleThreadPool(int poolSize) {
        taskQueue = new LinkedBlockingQueue<>();
        workers = new ArrayList<>();
        
        for (int i = 0; i < poolSize; i++) {
            WorkerThread worker = new WorkerThread(taskQueue);
            workers.add(worker);
            worker.start();
        }
    }
    
    public void execute(Runnable task) {
        taskQueue.offer(task);
    }
    
    class WorkerThread extends Thread {
        private BlockingQueue<Runnable> queue;
        
        WorkerThread(BlockingQueue<Runnable> queue) {
            this.queue = queue;
        }
        
        public void run() {
            while (!isInterrupted()) {
                try {
                    Runnable task = queue.take();
                    task.run();
                } catch (InterruptedException e) {
                    interrupt();
                }
            }
        }
    }
}

6.2 栈的典型应用场景

场景1：函数调用栈

public class FunctionCallExample {
    public void functionA() {
        System.out.println("Entering functionA");
        functionB();
        System.out.println("Exiting functionA");
    }
    
    public void functionB() {
        System.out.println("Entering functionB");
        functionC();
        System.out.println("Exiting functionB");
    }
    
    public void functionC() {
        System.out.println("Entering functionC");
        // 执行操作
        System.out.println("Exiting functionC");
    }
}

场景2：浏览器前进后退功能

public class BrowserHistory {
    private Stack<String> backStack;
    private Stack<String> forwardStack;
    private String currentPage;
    
    public BrowserHistory(String homepage) {
        backStack = new ArrayStack<>();
        forwardStack = new ArrayStack<>();
        currentPage = homepage;
    }
    
    public void visit(String url) {
        backStack.push(currentPage);
        currentPage = url;
        forwardStack.clear();
    }
    
    public String back() {
        if (!backStack.isEmpty()) {
            forwardStack.push(currentPage);
            currentPage = backStack.pop();
        }
        return currentPage;
    }
    
    public String forward() {
        if (!forwardStack.isEmpty()) {
            backStack.push(currentPage);
            currentPage = forwardStack.pop();
        }
        return currentPage;
    }
}

6.3 队列与栈结合使用的场景

场景：用队列实现栈，用栈实现队列

// 用队列实现栈
class StackUsingQueues<T> {
    private Queue<T> queue1;
    private Queue<T> queue2;
    
    public StackUsingQueues() {
        queue1 = new LinkedQueue<>();
        queue2 = new LinkedQueue<>();
    }
    
    public void push(T element) {
        queue2.enqueue(element);
        while (!queue1.isEmpty()) {
            queue2.enqueue(queue1.dequeue());
        }
        // 交换queue1和queue2
        Queue<T> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    public T pop() {
        if (queue1.isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }
        return queue1.dequeue();
    }
}
// 用栈实现队列
class QueueUsingStacks<T> {
    private Stack<T> stack1;
    private Stack<T> stack2;
    
    public QueueUsingStacks() {
        stack1 = new ArrayStack<>();
        stack2 = new ArrayStack<>();
    }
    
    public void enqueue(T element) {
        stack1.push(element);
    }
    
    public T dequeue() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        if (stack2.isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return stack2.pop();
    }
}

七、总结与选择指南

7.1 如何选择队列还是栈？

选择队列的情况：

需要保证先进先出的处理顺序
实现任务调度、消息传递系统
广度优先搜索（BFS）算法
生产者-消费者模式
缓存系统（如LRU缓存）

选择栈的情况：

需要后进先出的处理顺序
函数调用、递归实现
深度优先搜索（DFS）算法
括号匹配、表达式求值
撤销/重做功能

7.2 性能优化建议

队列优化：
使用循环队列避免数据迁移
根据场景选择合适的队列实现（普通队列、双端队列、优先级队列）
多线程环境使用线程安全队列
栈优化：
使用数组实现提高缓存性能
避免过深的递归调用，使用迭代+显式栈
注意栈溢出问题，合理设置栈大小

7.3 Java集合框架中的实现

// Java内置队列实现
Queue<Integer> queue1 = new LinkedList<>();      // 普通队列
Deque<Integer> deque = new ArrayDeque<>();       // 双端队列
Queue<Integer> priorityQueue = new PriorityQueue<>(); // 优先级队列
// Java内置栈实现
Stack<Integer> stack1 = new Stack<>();           // 传统栈
Deque<Integer> stack2 = new ArrayDeque<>();      // 推荐使用的栈（更高效）

通过本文的学习，你应该已经掌握了队列的原理、实现方式以及与栈的对比选择。在实际开发中，根据具体需求选择合适的数据结构，是编写高效Java程序的关键技能之一。队列和栈作为基础数据结构，在算法设计、系统开发中都有着不可替代的作用。

《数据之美》：队列的世界与算法实践

一、队列：先进先出的线性数据结构

1.1 队列的基本概念与特性

1.2 队列的ADT（抽象数据类型）定义

二、队列的实现方式

2.1 基于数组的实现（循环队列）

2.2 基于链表的实现

三、队列与栈的全面对比

3.1 基本特性对比

3.2 时间复杂度对比

3.3 内存布局对比

3.4 优缺点总结

四、队列的核心算法与应用

4.1 广度优先搜索（BFS）

4.2 二叉树层次遍历

五、队列的变种与高级实现

5.1 双端队列（Deque）

5.2 优先级队列（Priority Queue）

5.3 阻塞队列（Blocking Queue）

六、队列与栈的实际应用场景

6.1 队列的典型应用场景

6.2 栈的典型应用场景

6.3 队列与栈结合使用的场景

七、总结与选择指南

7.1 如何选择队列还是栈？

7.2 性能优化建议

7.3 Java集合框架中的实现

热门文章

最新文章

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

《数据之美》：队列的世界与算法实践

一、队列：先进先出的线性数据结构

1.1 队列的基本概念与特性

1.2 队列的ADT（抽象数据类型）定义

二、队列的实现方式

2.1 基于数组的实现（循环队列）

2.2 基于链表的实现

三、队列与栈的全面对比

3.1 基本特性对比

3.2 时间复杂度对比

3.3 内存布局对比

3.4 优缺点总结

四、队列的核心算法与应用

4.1 广度优先搜索（BFS）

4.2 二叉树层次遍历

五、队列的变种与高级实现

5.1 双端队列（Deque）

5.2 优先级队列（Priority Queue）

5.3 阻塞队列（Blocking Queue）

六、队列与栈的实际应用场景

6.1 队列的典型应用场景

6.2 栈的典型应用场景

6.3 队列与栈结合使用的场景

七、总结与选择指南

7.1 如何选择队列还是栈？

7.2 性能优化建议

7.3 Java集合框架中的实现

热门文章

最新文章

相关电子书