Cấu trúc dữ liệu Stack trong Swift
Bài đăng này đã không được cập nhật trong 6 năm
1. Bắt đầu
Stack cũng giống như mảng, nhưng nó bị hạn chế về chức năng so với mảng. Stack chỉ có thể push ( thêm ) phần tử ở đầu, pop (lấy ra) để xóa phần tử ở đầu stack và peek để lấy phần tử ở đầu mà không xóa nó khỏi Stack.
Tại sao phải dùng đến Stack? Trong nhiều thuật toán, bạn muốn thêm đối tượng vào một danh sách tại một thời điểm nào đó và lấy nó ra khỏi danh sách trong một thời điểm khác. Thông thường, thứ tự bạn thêm và loại bỏ các phần tử rất là quan trọng.
Một Stack cho bạn một quy chế LIFO hay tức là theo thứ tự vào sau ra trước. Phần tử được thêm vào cuối cũng sẽ được lấy ra đầu tiên của ngăn xếp.
2. Cách hoạt động của Stack
Stack có một phạm vi chức năng nhỏ. Chúng ta có thể lấy ví dụ về 1 chồng sách để hiểu rõ về cách họat động của Stack. Sau đây là những gì mà Stack có thể làm được:
* Push
Khi bạn muốn thêm một phần tử vào ngăn xếp, bạn dùng push để đưa nó vào Stack. Điều này cũng tương tự như đặt một cuốn sách lên đầu của 1 chồng sách vậy!
* Peek
Theo như thiết kế Stack không cho phép bạn duyệt các phần tử ngoại trừ phần tử đầu tiên. Phương thức peek cho phép bạn biết được phần tử đầu của Stack là gì .
* Pop
Khi muốn xóa một phần tử của Stack ta dùng phương thức pop. Có thể hiểu một cách đơn giản về pop là lấy ra cuốn sách đầu tiên của chồng sách.
3. Thực thi Stack trong Swift
Đầu tiên bạn hãy mở một playground để tiến hành thực hiện Stack trong Swift.
Để bắt đầu, hãy viết đoạn mã code sau vào playground
- Phương thức push có một tham số truyền vào. element được thêm vào Stack.
- Lưu ý rằng các phần tử mới được them vào sẽ được đưa vào cuối của mảng. Việc chèn dữ liệu vào đầu của mảng làm cho độ phức tạp của thuật toán tăng lên rất nhiều o(n), bởi vì nó yêu cầu tất cả các phần tử của mảng cần được đưa vào bộ nhớ. Còn khi thêm vào cuối mảng thì mọi thứ trở nên dễ dàng hơn, độ phức tạp chỉ là O(1).
Pop
Xóa một phần tử của Stack cũng rất dễ dàng. Thêm đoạn code sau vào trong struct Stack
- Phưương thức Pop trả về một optinal String. Giá trị trả về là optinal để xử lý trường hợp ngăn xếp rỗng. Nếu như bạn cố gắng pop một stack rỗng thì nó sẽ trả về giá trị nil
- Mảng trong Swift có một phương thức rất hữu ích giúp viêc loại bỏ phần tử cuối của mảng, đó là phương thức popLast
Peek
Phương thức peek để kiểm tra phần tử đầu tiên của Stack. Nó tương đối là đơn giản. Mảng trong Swift có thuộc tính “last” để lấy được phần tử cuối của mảng. Hãy thử vòa code của bạn
Phương thức peek tương đối giống so với pop. Sự khác nhau duy nhất ở đây là peek tránh được sự biến đổi của mảng, vì thế không cần thiết sử dụng mutating trong trường hợp này
Demo
Tại thời điểm này, Stack của bạn đã sẵn sàng cho một số thử nghiệm. Thêm đoạn code sau vào cuối file playground của bạn:
Bên phía tay phải của playground bạn sẽ thấy kết quả trả về của từng dòng:
- Bạn đã khai báo một thuộc tính rwBookStack và khởi tạo nó bằng Stack. rwBookStack cần phải là một biến chứ không phải là một hằng vì bạn cần biến đổi các nội dung của ngăn xếp.
- Bạn thêm một String vào trong Stack .
- Phương thức peek được thực hiên, nó sẽ hiển thị ra “3D Games by Tutorials”. Đây chính là phần tử cuối cùng được đưa vào Stack
- Xóa một phần tử trong Stack.
- Sẽ trả về giá trị nil, vì trước đó không còn phần tử nào trong Stack
CustomStringConvertible
Hiện tại khá là khó để xác định được các phần tử có trong ngăn xếp. May mắn rằng Swift xây dựng 1 protocol có tên là CustomStringConvertible cho phép bạn xác định cách bạn muốn đại diện cho một đối tượng như một chuỗi. Bây giờ bạn thêm đoạn code sau vào phần dưới của phần thực thi Stack.
>
Điều này tương đối đơn giản:
- Để sử dụng CustomStringConvertible , bạn tạo 1 extension và thực thi protocol CustomStringConvertible
- Thực hiện tạo giá trị cho thuộc tính description
- Để tiện cho việc quan sát, chúng ta tạo ra 2 phân tách dòng .
- Để hiển thị các phần tử trong ngăn xếp, bạn sẽ xếp chồng lên các phần tử trong mảng đó. Vì bạn đã nối các phần tử vào phía sau của mảng, trước tiên bạn cần phải đảo ngược mảng. Sau đó phương thức joined(separator:) lấy các phần tử trong mảng và nối chúng lại với 1 khoảng phân cách giữa mỗi phần tử.
- Cuối cùng bạn cho stackElements vào giữa 2 khoảng ngăn cách và trả về kết quả.
Kết quả thu được
Generic
Hiện tại, stack của bạn chỉ có thể lưu trữ chuỗi. Nếu bạn muốn tạo ra một ngăn xếp để lưu trữ số nguyên, bạn sẽ phải thực hiện một ngăn xếp hoàn toàn mới với kiểu số nguyên.
Thật may vì swift sẽ hỗ trợ bạn việc đó.Đầu tiên, cần sửa lại phần khai báo như sau
Dấu ngoặc nhọn được dùng để khai báo kiểu generic, cho phép sử dụng Stack này với mọi kiểu dữ liệu của Swift.Tiếp theo, tìm và cập nhật tất cả các trường hợp của bạn đã viết “String” và thay thế nó bằng "Element". Stack của bạn nên như thế này:
Cuối cùng, bạn sẽ phải cập nhật thuộc tính description. Chỉ có một thay đổi mới xảy ra. Cập nhật dòng sau để phù hợp :
Ý tưởng ở đây là để biến đổi các phần tử trong mảng thành String trước khi kết hợp chúng với nhau. Vì stack của bạn là generic, bạn không thể chắc chắn rằng các giá trị bạn đang tham gia là các chuỗi.
Cuối cùng, tìm dòng nơi bạn đã khởi tạo ngăn xếp của mình và chỉ định stack để gõ String:
Bây giờ stack của bạn có thể được chuyên biệt cho tất cả các loại, cho dù đó là Chuỗi, Int, hoặc thậm chí tùy chỉnh các loại bạn tạo ra, chẳng hạn như các đối tượng Person!
Tổng kết
Có hai thuộc tính khác thường đi kèm với ngăn xếp. Thông thường, bạn muốn biết liệu ngăn xếp có rỗng hay không, và có bao nhiêu phần tử hiện đang nằm trong ngăn xếp. Thêm thuộc tính đã được tính toán sau trong Stack
Nguồn : https://www.raywenderlich.com/149213/swift-algorithm-club-swift-stack-data-structure
All rights reserved
