Hàng đợi (Queue)

Queue là gì?

Queue là cấu trúc dữ liệu hoạt động theo nguyên tắc FIFO (First In, First Out) - phần tử vào trước sẽ được lấy ra trước.


Enqueue                                      Dequeue
   │                                            │
   ▼                                            ▼
┌─────┬─────┬─────┬─────┬─────┐
│ 50  │ 40  │ 30  │ 20  │ 10  │ ───▶ Ra
└─────┴─────┴─────┴─────┴─────┘
  Back                   Front

💡

Queue giống như hàng đợi mua vé - ai đến trước được phục vụ trước!

Các thao tác cơ bản

Thao tác	Mô tả	Độ phức tạp
`enqueue(x)`	Thêm x vào cuối	O(1)
`dequeue()`	Lấy phần tử ở đầu	O(1)
`front()`/`peek()`	Xem phần tử đầu	O(1)
`isEmpty()`	Kiểm tra queue rỗng	O(1)

Sử dụng Queue

Python


from collections import deque
 
queue = deque()
queue.append(10)     # enqueue
queue.append(20)
queue.append(30)
 
print(queue[0])       # front: 10
print(queue.popleft()) # dequeue: 10
print(len(queue))     # size: 2

Kotlin


val queue = ArrayDeque<Int>()
queue.addLast(10)    // enqueue
queue.addLast(20)
queue.addLast(30)
 
println(queue.first())       // front: 10
println(queue.removeFirst()) // dequeue: 10
println(queue.size)          // size: 2

Dart


import 'dart:collection';
 
Queue<int> queue = Queue();
queue.add(10);       // enqueue
queue.add(20);
queue.add(30);
 
print(queue.first);       // front: 10
print(queue.removeFirst()); // dequeue: 10
print(queue.length);      // size: 2

Swift


var queue = [Int]()
queue.append(10)     // enqueue
queue.append(20)
queue.append(30)
 
print(queue.first!)       // front: 10
print(queue.removeFirst()) // dequeue: 10
print(queue.count)        // size: 2

Java


Queue<Integer> queue = new LinkedList<>();
queue.offer(10);     // enqueue
queue.offer(20);
queue.offer(30);
 
System.out.println(queue.peek()); // front: 10
System.out.println(queue.poll()); // dequeue: 10
System.out.println(queue.size()); // size: 2

⚠️

Python: Không nên dùng list.pop(0) vì có độ phức tạp O(n). Dùng deque.popleft() thay thế!

BFS với Queue

Python


from collections import deque
 
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

Kotlin


fun bfs(graph: Map<Int, List<Int>>, start: Int): List<Int> {
    val visited = mutableSetOf(start)
    val queue = ArrayDeque<Int>()
    queue.addLast(start)
    val result = mutableListOf<Int>()
    
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        result.add(node)
        
        for (neighbor in graph[node] ?: emptyList()) {
            if (neighbor !in visited) {
                visited.add(neighbor)
                queue.addLast(neighbor)
            }
        }
    }
    return result
}

Dart


List<int> bfs(Map<int, List<int>> graph, int start) {
  Set<int> visited = {start};
  Queue<int> queue = Queue()..add(start);
  List<int> result = [];
  
  while (queue.isNotEmpty) {
    int node = queue.removeFirst();
    result.add(node);
    
    for (int neighbor in graph[node] ?? []) {
      if (!visited.contains(neighbor)) {
        visited.add(neighbor);
        queue.add(neighbor);
      }
    }
  }
  return result;
}

Swift


func bfs(_ graph: [Int: [Int]], _ start: Int) -> [Int] {
    var visited = Set([start])
    var queue = [start]
    var result = [Int]()
    
    while !queue.isEmpty {
        let node = queue.removeFirst()
        result.append(node)
        
        for neighbor in graph[node] ?? [] {
            if !visited.contains(neighbor) {
                visited.insert(neighbor)
                queue.append(neighbor)
            }
        }
    }
    return result
}

Java


List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    List<Integer> result = new ArrayList<>();
    
    visited.add(start);
    queue.offer(start);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);
        
        for (int neighbor : graph.getOrDefault(node, List.of())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
    return result;
}

So sánh Stack vs Queue

	Stack	Queue
Nguyên tắc	LIFO	FIFO
Thêm	push (đỉnh)	enqueue (cuối)
Lấy	pop (đỉnh)	dequeue (đầu)
Duyệt đồ thị	DFS	BFS

Tiếp theo: Bảng băm (Hash Table)