Giới thiệu

Đã bao giờ bạn phải chờ đợi để xin chữ ký của một nghệ sĩ chưa? Nếu có, bạn sẽ hiểu tôi đang nói về điều gì. Bạn dậy sớm để xếp hàng đầu tiên và nhận chữ ký cho đĩa nhạc, poster hoặc sách yêu thích của mình.

Đó chính là nguyên tắc FIFO (First In First Out) trong hành động. Và cấu trúc dữ liệu mà chúng ta sẽ khám phá tuần này cũng tuân theo nguyên tắc này. Chúng ta sẽ học cách triển khai Hàng Đợi (Queue).

FIFO - First In First Out

Hàng đợi (Queue) thực hiện thứ tự FIFO, tức là các mục được loại bỏ khỏi hàng đợi theo cùng thứ tự mà chúng được thêm vào. Khác với cấu trúc dữ liệu ngăn xếp (Stack), hàng đợi hoạt động như việc chờ gặp thần tượng của bạn. Vị trí bạn đứng trong hàng sẽ quyết định thứ tự bạn được gặp gỡ.

Triển Khai Hàng Đợi

Tuần này, chúng ta sẽ triển khai một Hàng Đợi. Giống như ngăn xếp, nó có thể được triển khai bằng danh sách liên kết, vì thực chất chúng là những cấu trúc tương tự—chỉ khác nhau ở chỗ các mục được thêm vào và loại bỏ từ hai đầu đối lập.

Chúng ta sẽ tái sử dụng lớp Node mà chúng ta đã tạo ra trong bài viết về ngăn xếp:

export class Node<T> {
    value: T;
    next: Node<T> | null;

    constructor(value: T) {
        this.value = value;
        this.next = null;
    }
}

Lớp Node này sẽ lưu trữ mỗi mục trong hàng đợi, giữ giá trị thực tế cùng với tham chiếu đến mục tiếp theo.

Bây giờ, cho lớp Hàng Đợi, chúng ta sẽ làm theo cách tương tự, tận dụng Generics của TypeScript. Tuy nhiên, khác với ngăn xếp, chúng ta sẽ theo dõi cả hai mục đầu tiên và cuối cùng trong hàng đợi của mình.

export class Queue<T> {
    first: Node<T> | null;
    last: Node<T> | null;
    size: number;
}

Trong constructor, chúng ta cần khởi tạo các tham chiếu đến nút đầu tiên và cuối cùng. Điều này đảm bảo rằng mỗi khi một Hàng Đợi mới được khởi tạo, chúng ta có các giá trị mặc định cho các mục đầu tiên và cuối cùng trong hàng đợi.

constructor(value: T) {
  this.first = new Node(value);
  this.last = this.first;
  this.size = 1;
}

Thêm Mục Vào Hàng Đợi (Enqueue)

Phép toán enqueue thêm một mục vào cuối hàng đợi. Bước đầu tiên là tạo một nút mới.

const newNode = new Node(value);

Vì nút mới này sẽ trở thành mục cuối cùng trong hàng đợi (vì nó vừa gia nhập), chúng ta cần kiểm tra nếu biến last không phải là null. Nếu có giá trị, chúng ta kết nối con trỏ next của nó đến nút mới này.

if(this.last !== null) this.last.next = newNode;

Tiếp theo, chúng ta cập nhật con trỏ last để tham chiếu đến nút mới được tạo.

this.last = newNode;

Chúng ta cũng cần đảm bảo rằng biến first có giá trị. Nếu nó là null, điều đó có nghĩa là nút mới này là phần tử đầu tiên trong hàng đợi.

if(this.first === null) this.first = this.last;

Cuối cùng, chúng ta tăng kích thước của hàng đợi. Và voilà! Hàng đợi của chúng ta giờ có khả năng thêm các mục mới.

Xóa Mục Khỏi Hàng Đợi (Dequeue)

Phép toán này loại bỏ mục đầu tiên trong hàng đợi. Bước đầu tiên là xác minh rằng biến first không phải là null. Nếu nó là null, chúng ta chỉ cần trả về null vì không có mục nào trong hàng đợi.

if(this.first === null) return null;

Bây giờ, chúng ta đã xác minh rằng biến first có giá trị, chúng ta gán giá trị này cho một hằng số mới gọi là nodeToDequeue để theo dõi nút mà chúng ta sẽ loại bỏ.

const nodeToDequeue = this.first;

Tiếp theo, chúng ta cần gán biến first để trỏ đến mục tiếp theo (nút) trong hàng đợi, vì điều này sẽ trở thành phần tử đầu tiên mới của chúng ta.

this.first = this.first.next;

Tiếp theo, chúng ta cần kiểm tra xem có còn nút nào trong hàng đợi không. Nếu con trỏ first giờ là null, điều đó có nghĩa là hàng đợi của chúng ta rỗng và chúng ta cũng phải xóa con trỏ last.

if(this.first === null) this.last = null;

Cuối cùng, chúng ta giảm kích thước của hàng đợi và trả về giá trị của nút đã bị xóa.

this.size--;
return nodeToDequeue.value;

Và voilà! Hàng đợi của chúng ta giờ đã có khả năng xóa các phần tử của nó. Thật đơn giản, phải không?

Nhìn Vào Mục Đầu Tiên (Peek)

Phép toán này trả về mục đầu tiên trong hàng đợi, đồng thời đảm bảo nó có giá trị. Điều này rất đơn giản vì chúng ta đã tạo ra biến first—chúng ta chỉ cần trả về giá trị của nó nếu nó tồn tại, hoặc null nếu không.

return this.first ? this.first.value : null;

Như bạn thấy, chúng ta đã giải quyết điều này với một dòng mã duy nhất. Phép toán đơn giản này cho phép chúng ta nhìn vào mục đầu tiên trong hàng đợi mà không cần xóa nó.

Kiểm Tra Hàng Đợi Có Rỗng Hay Không

Phép toán này kiểm tra xem hàng đợi của chúng ta có rỗng không bằng cách xem kích thước của nó. Nếu kích thước bằng 0, điều đó có nghĩa là không có mục nào trong hàng đợi, cho thấy nó rỗng. Phương thức đơn giản chỉ cần trả về kết quả đánh giá này.

return this.size === 0;

Triển Khai Hoàn Chỉnh Trong TypeScript

export class Queue<T> {
    first: Node<T> | null;
    last: Node<T> | null;
    size: number;

    constructor(value: T) {
        this.first = new Node(value);
        this.last = this.first;
        this.size = 1;
    }

    enqueue(value: T): void {
        const newNode = new Node(value);
        if(this.last !== null) this.last.next = newNode;
        this.last = newNode;
        if(this.first === null) this.first = this.last;
        this.size++;
    }

    dequeue(): T | null {
        if(this.first === null) return null;
        const nodeToDequeue = this.first;
        this.first = this.first.next;
        if(this.first === null) this.last = null;
        this.size--;
        return nodeToDequeue.value;
    }

    peek(): T | null {
        return this.first ? this.first.value : null;
    }

    isEmpty(): boolean {
        return this.size === 0;
    }
}

Lời Kết

Trong bài viết này, chúng ta đã khám phá cấu trúc dữ liệu Hàng Đợi và nguyên tắc FIFO (First In, First Out) của nó. Chúng ta đã xem xét cách triển khai một Hàng Đợi trong TypeScript, sử dụng các nút liên kết tương tự như những gì chúng ta đã sử dụng trong ngăn xếp, nhưng với sự khác biệt quan trọng là thêm các phần tử vào cuối và loại bỏ chúng từ đầu.

Chúng ta đã triển khai bốn phép toán cơ bản: enqueue để thêm các phần tử, dequeue để loại bỏ chúng, peek để kiểm tra phần tử đầu tiên mà không cần loại bỏ nó, và isEmpty để xác minh xem hàng đợi có rỗng hay không. Những phép toán này cho phép chúng ta thao tác hàng đợi một cách hiệu quả, luôn duy trì thứ tự tiếp nhận.

Hàng đợi là những cấu trúc dữ liệu cơ bản xuất hiện trong nhiều ngữ cảnh lập trình và trong các tình huống hàng ngày, như chờ đợi để xin chữ ký của nghệ sĩ yêu thích. Hiểu cách hoạt động và triển khai của chúng mang đến cho chúng ta công cụ mạnh mẽ để giải quyết các vấn đề cần xử lý các phần tử theo cùng một thứ tự mà chúng được nhận.

Như thường lệ, bạn có thể tìm thấy mã nguồn trong kho lưu trữ Cấu trúc Dữ liệu của tôi: GitHub Repository

Hẹn gặp lại trong bài viết tiếp theo!