队列是一种遵循先进先出(FIFO)原则的线性数据结构。只允许在队尾进行插入操作,在队首进行删除操作。适用于需要按照到达顺序处理的问题。
队列是一种特殊的线性数据结构,遵循先进先出(First-In-First-Out,FIFO)的原则。最先添加到队列中的元素将是第一个被移除的元素。可以将队列想象为排队购票的人群,先到的人先办理业务,后到的人排在队尾等待。

队列的操作通常在两端进行:一端(队尾)只用来添加元素,另一端(队头)只用来删除元素。
▼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复制代码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复制代码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复制代码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复制代码#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++复制代码#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; }
测验答案
- 队列的主要特点是先进先出(FIFO),即最先入队的元素最先出队。
- 都是O(1)。在使用链表或正确实现的数组(循环队列)的情况下,这些操作都是常数时间的。
- 队列遵循先进先出(FIFO)原则,而栈遵循后进先出(LIFO)原则。队列在两端操作(一端入队,另一端出队),而栈只在一端(栈顶)操作。