队列

算法

队列是一种遵循先进先出(FIFO)原则的线性数据结构。只允许在队尾进行插入操作,在队首进行删除操作。适用于需要按照到达顺序处理的问题。

空间复杂度:O(n)

算法讲解

队列(Queue)

介绍

队列是一种特殊的线性数据结构,遵循先进先出(First-In-First-Out,FIFO)的原则。最先添加到队列中的元素将是第一个被移除的元素。可以将队列想象为排队购票的人群,先到的人先办理业务,后到的人排在队尾等待。

队列的操作通常在两端进行:一端(队尾)只用来添加元素,另一端(队头)只用来删除元素。

核心特性

  1. 先进先出(FIFO):最先入队的元素最先出队
  2. 两端操作:在队尾添加元素,在队头删除元素
  3. 快速访问首尾元素:O(1)时间复杂度访问队头和队尾元素
  4. 元素访问受限:无法直接访问队列中间元素

基本操作

1. 入队(enqueue)

  • 时间复杂度:O(1)
  • 描述:将元素添加到队列尾部

2. 出队(dequeue)

  • 时间复杂度:O(1)
  • 描述:移除并返回队列头部元素

3. 查看队头(peek/front)

  • 时间复杂度:O(1)
  • 描述:查看队头元素但不移除

4. 判断队列是否为空(isEmpty)

  • 时间复杂度:O(1)
  • 描述:检查队列中是否有元素

5. 获取队列大小(size)

  • 时间复杂度:O(1)
  • 描述:获取队列中元素的数量

基础实现

代码实现

Java 实现

▼
Java
复制代码
#### 使用Java内置的Queue接口 import java.util.LinkedList; import java.util.Queue; public class QueueExample { public static void main(String[] args) { // 创建队列(使用LinkedList实现) Queue<Integer> queue = new LinkedList<>(); // 入队 queue.offer(10); queue.offer(20); queue.offer(30); System.out.println("队列: " + queue); // 输出: [10, 20, 30] // 查看队头元素(不移除) int frontElement = queue.peek(); System.out.println("队头元素: " + frontElement); // 输出: 10 // 出队 int dequeuedElement = queue.poll(); System.out.println("出队的元素: " + dequeuedElement); // 输出: 10 // 检查队列是否为空 boolean isEmpty = queue.isEmpty(); System.out.println("队列是否为空: " + isEmpty); // 输出: false // 获取队列大小 int size = queue.size(); System.out.println("队列大小: " + size); // 输出: 2 System.out.println("最终队列: " + queue); // 输出: [20, 30] } }

使用数组实现队列

▼
Java
复制代码
public class ArrayQueue<T> { private static final int DEFAULT_CAPACITY = 10; private Object[] array; private int front; // 队头指针 private int rear; // 队尾指针 private int size; // 元素数量 public ArrayQueue() { array = new Object[DEFAULT_CAPACITY]; front = 0; rear = 0; size = 0; } // 入队 public void enqueue(T item) { if (size == array.length) { // 队列满,需要扩容 resize(); } array[rear] = item; rear = (rear + 1) % array.length; // 循环队列 size++; } // 出队 @SuppressWarnings("unchecked") public T dequeue() { if (isEmpty()) { throw new IllegalStateException("队列为空"); } T item = (T) array[front]; array[front] = null; // 避免内存泄漏 front = (front + 1) % array.length; // 循环队列 size--; return item; } // 查看队头 @SuppressWarnings("unchecked") public T peek() { if (isEmpty()) { throw new IllegalStateException("队列为空"); } return (T) array[front]; } // 检查队列是否为空 public boolean isEmpty() { return size == 0; } // 获取队列大小 public int size() { return size; } // 扩容 private void resize() { Object[] newArray = new Object[array.length * 2]; for (int i = 0; i < size; i++) { newArray[i] = array[(front + i) % array.length]; } array = newArray; front = 0; rear = size; } public static void main(String[] args) { ArrayQueue<Integer> queue = new ArrayQueue<>(); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); System.out.println("队头元素: " + queue.peek()); // 输出: 10 System.out.println("出队的元素: " + queue.dequeue()); // 输出: 10 System.out.println("队列大小: " + queue.size()); // 输出: 2 System.out.println("队列是否为空: " + queue.isEmpty()); // 输出: false } }

JavaScript 实现

▼
Javascript
复制代码
class Queue { constructor() { this.items = []; } // 入队 enqueue(element) { this.items.push(element); } // 出队 dequeue() { if (this.isEmpty()) { throw new Error("队列为空"); } return this.items.shift(); } // 查看队头 front() { if (this.isEmpty()) { throw new Error("队列为空"); } return this.items[0]; } // 判断队列是否为空 isEmpty() { return this.items.length === 0; } // 获取队列大小 size() { return this.items.length; } } // 使用示例 const queue = new Queue(); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); console.log("队头元素:", queue.front()); // 输出: 10 console.log("出队的元素:", queue.dequeue()); // 输出: 10 console.log("队列大小:", queue.size()); // 输出: 2 console.log("队列是否为空:", queue.isEmpty()); // 输出: false

Python 实现

▼
Python
复制代码
from collections import deque class Queue: def __init__(self): self.items = deque() # 入队 def enqueue(self, item): self.items.append(item) # 出队 def dequeue(self): if self.is_empty(): raise Exception("队列为空") return self.items.popleft() # 查看队头 def front(self): if self.is_empty(): raise Exception("队列为空") return self.items[0] # 判断队列是否为空 def is_empty(self): return len(self.items) == 0 # 获取队列大小 def size(self): return len(self.items) # 使用示例 if __name__ == "__main__": queue = Queue() queue.enqueue(10) queue.enqueue(20) queue.enqueue(30) print("队头元素:", queue.front()) # 输出: 10 print("出队的元素:", queue.dequeue()) # 输出: 10 print("队列大小:", queue.size()) # 输出: 2 print("队列是否为空:", queue.is_empty()) # 输出: False

Go 实现

▼
Go
复制代码
package main import ( "errors" "fmt" ) // Queue 结构体 type Queue struct { items []interface{} } // 创建新队列 func NewQueue() *Queue { return &Queue{ items: []interface{}{}, } } // Enqueue 入队 func (q *Queue) Enqueue(item interface{}) { q.items = append(q.items, item) } // Dequeue 出队 func (q *Queue) Dequeue() (interface{}, error) { if q.IsEmpty() { return nil, errors.New("队列为空") } item := q.items[0] q.items = q.items[1:] return item, nil } // Front 查看队头 func (q *Queue) Front() (interface{}, error) { if q.IsEmpty() { return nil, errors.New("队列为空") } return q.items[0], nil } // IsEmpty 判断队列是否为空 func (q *Queue) IsEmpty() bool { return len(q.items) == 0 } // Size 获取队列大小 func (q *Queue) Size() int { return len(q.items) } func main() { queue := NewQueue() queue.Enqueue(10) queue.Enqueue(20) queue.Enqueue(30) front, _ := queue.Front() fmt.Println("队头元素:", front) // 输出: 10 dequeued, _ := queue.Dequeue() fmt.Println("出队的元素:", dequeued) // 输出: 10 fmt.Println("队列大小:", queue.Size()) // 输出: 2 fmt.Println("队列是否为空:", queue.IsEmpty()) // 输出: false }

C 实现

▼
C
复制代码
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_SIZE 100 typedef struct { int items[MAX_SIZE]; int front; int rear; int size; } Queue; // 初始化队列 void initialize(Queue *queue) { queue->front = 0; queue->rear = 0; queue->size = 0; } // 判断队列是否为空 bool isEmpty(Queue *queue) { return queue->size == 0; } // 判断队列是否已满 bool isFull(Queue *queue) { return queue->size == MAX_SIZE; } // 获取队列大小 int size(Queue *queue) { return queue->size; } // 入队 void enqueue(Queue *queue, int item) { if (isFull(queue)) { printf("队列已满,无法入队\n"); return; } queue->items[queue->rear] = item; queue->rear = (queue->rear + 1) % MAX_SIZE; // 循环队列 queue->size++; } // 出队 int dequeue(Queue *queue) { if (isEmpty(queue)) { printf("队列为空,无法出队\n"); return -1; } int item = queue->items[queue->front]; queue->front = (queue->front + 1) % MAX_SIZE; // 循环队列 queue->size--; return item; } // 查看队头元素 int front(Queue *queue) { if (isEmpty(queue)) { printf("队列为空,无法查看队头\n"); return -1; } return queue->items[queue->front]; } int main() { Queue queue; initialize(&queue); enqueue(&queue, 10); enqueue(&queue, 20); enqueue(&queue, 30); printf("队头元素: %d\n", front(&queue)); // 输出: 10 printf("出队的元素: %d\n", dequeue(&queue)); // 输出: 10 printf("队列大小: %d\n", size(&queue)); // 输出: 2 printf("队列是否为空: %s\n", isEmpty(&queue) ? "是" : "否"); // 输出: 否 return 0; }

C++实现

使用STL的queue容器

▼
C++
复制代码
#include <iostream> #include <queue> int main() { // 创建队列 std::queue<int> queue; // 入队 queue.push(10); queue.push(20); queue.push(30); // 查看队头元素(不移除) std::cout << "队头元素: " << queue.front() << std::endl; // 输出: 10 // 出队 queue.pop(); std::cout << "出队后的队头: " << queue.front() << std::endl; // 输出: 20 // 检查队列是否为空 std::cout << "队列是否为空: " << (queue.empty() ? "是" : "否") << std::endl; // 输出: 否 // 获取队列大小 std::cout << "队列大小: " << queue.size() << std::endl; // 输出: 2 return 0; }

自定义队列实现

▼
C++
复制代码
#include <iostream> #include <vector> #include <stdexcept> template <typename T> class Queue { private: std::vector<T> items; public: // 入队 void enqueue(T item) { items.push_back(item); } // 出队 T dequeue() { if (isEmpty()) { throw std::runtime_error("队列为空"); } T item = items.front(); items.erase(items.begin()); return item; } // 查看队头 T front() { if (isEmpty()) { throw std::runtime_error("队列为空"); } return items.front(); } // 判断队列是否为空 bool isEmpty() { return items.empty(); } // 获取队列大小 size_t size() { return items.size(); } }; int main() { Queue<int> queue; queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); std::cout << "队头元素: " << queue.front() << std::endl; // 输出: 10 std::cout << "出队的元素: " << queue.dequeue() << std::endl; // 输出: 10 std::cout << "队列大小: " << queue.size() << std::endl; // 输出: 2 std::cout << "队列是否为空: " << (queue.isEmpty() ? "是" : "否") << std::endl; // 输出: 否 return 0; }

优缺点

优点

  1. 实现简单:队列的概念和实现都很简单直观
  2. 操作高效:基本操作的时间复杂度都是O(1)
  3. 有序处理:保证元素按照添加的顺序处理
  4. 适合数据流处理:适用于需要按顺序处理数据的场景

缺点

  1. 访问限制:只能访问队头和队尾元素,无法直接访问中间元素
  2. 移除元素受限:只能按先进先出的顺序移除元素
  3. 不适合随机访问:获取中间元素需要先出队前面所有元素

应用场景

  1. 任务调度:操作系统中的进程调度
  2. 消息队列:分布式系统中的消息传递
  3. 缓冲区管理:I/O操作中的数据缓冲
  4. 广度优先搜索(BFS):图算法中使用队列存储待访问的节点
  5. 打印任务管理:打印机任务队列
  6. 网络数据包处理:网络设备中数据包的处理顺序

测验

  1. 队列的主要特点是什么?
  2. 队列的enqueue和dequeue操作的时间复杂度是多少?
  3. 与栈相比,队列的主要区别是什么?

测验答案

  1. 队列的主要特点是先进先出(FIFO),即最先入队的元素最先出队。
  2. 都是O(1)。在使用链表或正确实现的数组(循环队列)的情况下,这些操作都是常数时间的。
  3. 队列遵循先进先出(FIFO)原则,而栈遵循后进先出(LIFO)原则。队列在两端操作(一端入队,另一端出队),而栈只在一端(栈顶)操作。

相关的LeetCode热门题目

  1. 232. 用栈实现队列 - 使用两个栈实现队列的功能。
  2. 622. 设计循环队列 - 设计实现一个循环队列数据结构。
  3. 933. 最近的请求次数 - 使用队列跟踪最近的请求。
  4. 225. 用队列实现栈 - 使用队列实现栈的功能。
  5. 239. 滑动窗口最大值 - 使用双端队列优化滑动窗口问题。