Sự khác nhau giữa Stack và Queue

Stack và Queue là hai cấu trúc dữ liệu quan trọng với các đặc điểm riêng biệt.

1. Cấu trúc dữ liệu tuyến tính: Cả Stack và Queue đều là cấu trúc dữ liệu tuyến tính, trong đó các phần tử được sắp xếp theo một trình tự nhất định.

2. Nguyên tắc hoạt động: Cả hai đều hoạt động dựa trên nguyên tắc quản lý truy cập và loại bỏ phần tử dựa trên thứ tự chèn vào.

   • Stack hoạt động theo nguyên tắc LIFO (Last In, First Out): phần tử được thêm vào sau cùng sẽ được lấy ra trước.
   • Queue hoạt động theo nguyên tắc FIFO (First In, First Out): phần tử được thêm vào đầu tiên sẽ được lấy ra trước.

Bảng so sánh sự khác nhau

Để làm rõ hơn về sự giống và khác nhau giữa ngăn xếp và hàng đợi, chúng ta cài đặt và xét ví dụ sau:

Cài đặt ngăn xếp

Cài đặt ngăn xếp bằng danh sách liên kết đơn sử dụng Swift

class Node {
    var data: Any
    var next: Node?

    init(data: Any) {
        self.data = data
        self.next = nil
    }
}

class LinkedList {
    private var head: Node?

    func pushFront(_ data: Any) {
        let newNode = Node(data: data)
        newNode.next = head
        head = newNode
    }

    func popFront() -> Any {
        guard let headNode = head else {
            fatalError("popFront from empty list")
        }
        head = headNode.next
        return headNode.data
    }

    func front() -> Any {
        guard let headNode = head else {
            fatalError("front from empty list")
        }
        return headNode.data
    }
} 

Các thao tác chính của ngăn xếp

Push khi một phần tử mới được thêm vào đầu ngăn xếp được gọi là hoạt động Push. Gọi thao tác pushFront(e) của DSLK đơn.

Pop: khi một phần tử bị xóa khỏi đầu ngăn xếp được gọi là hoạt động Pop. Gọi đến thao tác popFront của DSLK đơn.

Top/Peek: khi trả về một phần tử ở đỉnh hoạt động đó được gọi là Top/Peek. Gọi đến thao tác front của DSLK đơn.

Lưu ý: Pop và Top/Peek có thể được kết hợp thành một thao tác nếu cần thiết.

class Stack {
    private let list = LinkedList()
    
    // Thêm phần tử vào đỉnh ngăn xếp
    func push(_ e: Any) {
        list.pushFront(e)
    }
    
    // Loại bỏ phần tử từ đỉnh ngăn xếp và trả về giá trị của nó
    func pop() -> Any {
        return list.popFront()
    }

   // Trả về phần tử ở đỉnh ngăn xếp mà không loại bỏ
    func top() -> Any {
        return list.front()
    }
}

Ví dụ về ngăn xếp

Để minh họa cho cách hoạt động của ngăn xếp, chúng ta sẽ lấy ví dụ về việc định giá một biểu thức hậu tố.

• Giả sử, chúng ta cần định giá biểu thức trung tố sau:

Máy tính khoa học sẽ cho kết quả 288 → đúng.
Máy tính giản đơn (tính tuần tự từ trái sang phải, bỏ qua ngoặc đơn)sẽ cho kết quả 283 → sai.

• Nếu viết lại biểu thức trên dưới dạng hậu tố (toán tử nằm sau các toán hạng của nó) rồi áp dụng ngăn xếp, ta chỉ cần tính tuần tự từ trái sang phải mà không cần quan tâm đến độ ưu tiên của các toán tử:

Chúng ta sẽ cùng thử định giá biểu thức hậu tố này bằng ngăn xếp xem kết quả như thế nào nhé.

• Đặt bốn toán hạng đầu tiên vào ngăn xếp.

• Đọc “+”, lấy 3 và 2 ra, cộng lại được 5, đặt 5 vào ngăn xếp.

• Đặt 8 vào ngăn xếp.

• Đọc “∗”, lấy 8 và 5 ra, nhân vào được 40, đặt 40 vào ngăn xếp.

• Đọc “+”, lấy 40 và 5 ra, cộng lại được 45, đặt 45 vào ngăn xếp.

• Đặt 3 vào ngăn xếp.

• Đọc “+”, lấy 3 và 45 ra, cộng lại được 48, đặt 48 vào ngăn xếp.

• Đọc “∗”, lấy 48 và 6 ra, nhân vào được 288, đặt 288 vào ngăn xếp.

• Khi đã quét hết biểu thức, giá trị duy nhất còn lại trong ngăn xếp (288) chính là giá trị tính được của biểu thức.

Cài đặt hàng đợi

Như trường hợp ngăn xếp, ta có thể dùng mảng hoặc danh sách liên kết đơn để cài đặt hàng đợi
Ở đây, ta chỉ xem xét cách cài đây dùng mảng:

• theArray là mảng chứ các phần tử.
• currentSize là số phần tử hiện có trong hàng đợi.
• front và back giữa ví trí của phần tử đầu và cuối hàng đợi, vị trí nằm trong khoảng từ 0 đến chiều dài của mảng trừ đi 1.

• enqueue(e): back++, theArray[back] = e, currentSize++

• dequeue: front++, currentSize–

• Hàng đợi này chỉ chứa được 10 phần tử, vì vậy nó có thể nhanh chóng đầy khi thêm đủ số lượng phần tử.

• Trên thực tế, hàng đợi thường chỉ cần nhỏ vì thao tác dequeue sẽ diễn ra đều đặn để loại bỏ các phần tử khỏi hàng đợi sau khi chúng đã được xử lý.

• Tuy nhiên, trong ví dụ trên, sau 10 lần enqueue, nếu back đã ở vị trí cuối cùng của mảng thì sẽ không thể thêm phần tử mới bằng enqueue.

=> Giải pháp để khắc phục giới hạn này là sử dụng mảng vòng tròn (circular array).

Mảng vòng tròn

Chú ý: Vì front có thể nằm trước hoặc sau back, nên không thể biết khi nào hàng đợi rỗng nếu chỉ căn cứ vào front và back → phải kiểm tra currentSize!

Kết luận

Mặc dù đều là cấu trúc dữ liệu tuyến tính, Stack và Queue có những khác biệt quan trọng về cơ chế hoạt động, cấu trúc, và cách triển khai. Dù vậy, cả hai đều cung cấp những phương thức mạnh mẽ để quản lý và thao tác trên các phần tử trong danh sách, đặc biệt trong việc thêm và xóa phần tử.

Hy vọng rằng qua đây, bạn đã có cái nhìn sâu sắc hơn về sự khác biệt giữa Stack và Queue, cũng như tầm quan trọng của chúng trong lập trình.