Cấu trúc dữ liệu Queue trong Swift

Bắt đầu

Hàng đợi là một danh sách mà bạn chỉ có thể thêm các phần tử mới vào cuối danh sách và xóa các phần tử từ đầu danh sách. Điều này đảm bảo rằng phần tử đầu tiên của bạn là phần tử được thêm vào đầu tiên, cũng là phần tử được lấy ra đầu tiên. Đến trước thì phục vụ trước!

Tại sao bạn cần điều này? Trong nhiều thuật toán, bạn muốn thêm các phần tử tới một danh sách tạm thời và sau đó lấy chúng ra khỏi danh sách này vào một thời gian sau. Thông thường, thứ tự bạn thêm và xóa các phần tử này sẽ gặp vấn đề.

Một hàng đợi cung cấp cho bạn một cơ chế FIFO: first-in, first-out. Phần tử bạn thêm vào đầu tiên cũng là phần tử bạn lấy ra đầu tiên.

Ví dụ

Cách đơn giản nhất để hiểu hàng đợi được sử dụng như thế nào, hãy tưởng tượng bạn có 1 hàng đợi, bạn enqueue một số như sau:

Hàng đợi bây giờ sẽ là [10]. Sau đó, bạn có thể thêm số tiếp theo vào hàng đợi:

Hàng đợi bây giờ sẽ là [10, 3]. Bạn có thể thêm một số nữa:

Hàng đợi bây giờ sẽ là [10, 3, 57]. Bạn có thể dequeue để lấy phần tử đầu tiên ra khỏi hàng đợi:

Sẽ trả về 10 vì đó là số đầu tiên bạn thêm vào. Hàng đợi bây giờ sẽ là [3, 57].

Sẽ trả về 3, bạn dequeue tiếp sẽ trả về 57, ... Nếu hàng đợi rỗng, dequeue sẽ trả về nil

Triển khai Hàng đợi

Trong phần này, bạn sẽ triển khai một hàng đợi đơn giản mục đích là lưu các giá trị Int

Dowload project start: queue starter projectFile playground sẽ chứa một hàng đợi rỗng:

File playground cũng chứa code của một LinkedList (bạn có thể thấy bằng cách vào View\Project Navigators\Show Project Navigator và mở Sources\LinkedList.)

Enqueue

Một hàng đợi cần có một phương thức enqueue. Bạn sẽ sử dụng LinkedList đã bao gồm trong project start để triển khai hàng đợi của bạn. Thêm vào đoạn code sau:

1. Thêm một biến private LinkedList sẽ được sử dụng để lưu trữ các phần tử trong hàng đợi của bạn
2. Thêm một phương thức để enqueue phần tử. Phương thức này sẽ làm biến đổi LinkedList, do đó, bạn xác định rõ ràng rằng bằng cách thêm từ khóa mutaing vào đầu phương thức.

Dequeue

Một hàng đợi cũng cần một phương thức dequeue:

1. Thêm 1 phương thức dequeue trả về phần tử đầu tiên của hàng đợi, trả về nil nếu hàng đợi đang rỗng. Phương thức này sẽ biến đổi LinkedList nên bạn cần thêm từ khóa mutating ở đầu phương thức.
2. Sử dụng câu lệnh guard để xử lý hàng đợi đang rỗng. Nếu hàng đợi rỗng, guard sẽ thực hiện khối lệnh else

Peek

Một hàng đợi cũng cần một phương thức peek, phương thức này trả về phần tử đầu tiên của hàng đợi mà không cần xóa nó:

IsEmpty

Hàng đợi có thể rỗng:

In hàng đợi của bạn

Thêm đoạn code sau vào file playground của bạn:

In hàng đợi lên console:

Để hiển thị chuỗi đầu ra dễ đọc hơn, bạn có thể làm cho queue chấp nhận giao thức CustomStringConvertable như sau:

1. Khai báo một extension cho class Queue, và adopted protocol CustomStringConvertible
2. Định nghĩa thuộc tính description. Đây là thuộc tính computed, thuộc tính chỉ đọc và trả về 1 String

Bây giờ, khi bạn in hàng đợi ra, bạn sẽ nhận được một danh sách như thế này: