27 C
Ho Chi Minh
Sunday, February 26, 2017
Cấu trúc dữ liệu và giải thuật: Ngăn xếp (Stack) trong Swift

Cấu trúc dữ liệu và giải thuật: Ngăn xếp (Stack) trong Swift

Stack Swift

1. Ngăn xếp(stack) là gì

  • Ngăn xếp là 1 dạng đặc biệt của danh sách liên kết mà việc bổ sung hay loại bỏ 1 phần tử đều thực hiện ở 1 đầu của danh sách gọi là đỉnh.
  • Ngăn xếp có 2 thao tác cơ bản: thêm phần tử vào được gọi là push và loại bỏ phần tử được gọi là pop.
  • Việc loại bỏ phần tử sẽ tiến hành loại bỏ phần tử mới nhất được đưa vào danh sách, chính vì tính chất này mà ngăn xếp còn được gọi là kiểu dữ liệu LIFO(last in first out – Vào sau ra trước)

2. Khởi tạo stack

2.1 . Định nghĩa kiểu dữ liệu stack

  • Vì stack là 1 dạng đặc biệt của danh sách liên kết nên ta có thể dùng kiểu dữ liệu Node đã trình bày ở bài danh sách liên kết để biểu diễn kiểu dữ liệu của stack

  • Định nghĩa 1 class Stack với kiểu dữ liệu generic T và 1 node trên cùng gọi là top

2.2. Thêm 1 phần tử vào ngăn xếp (push)

  • Kiểm tra xem ngăn xếp có nil không, nếu nil thì gán đỉnh ngăn xếp vào phần tử muốn thêm vào.
  • Nếu đỉnh ngăn xếp không nil, tạo 1 nút mới, gán phần tử muốn thêm vào nút đó, gán đỉnh ngăn xếp vào nút vừa tạo.

2.3. Lấy 1 phần tử ra khỏi danh sách(pop)

  • Kiểm tra danh sách đỉnh có rỗng không, nếu rỗng thì kết thúc.
  • Nếu đỉnh danh sách không rỗng, kiểm tra nút đỉnh trỏ đến có rỗng không nếu rỗng thì gán đỉnh danh sách bằng nil( trường hợp danh sách chỉ có 1 phần sau khi lấy 1 phần tử ra thì danh sách trở thành rỗng), còn không gán đỉnh của danh sách vào nút tiếp theo.

2.4. Xem phần tử đầu danh sách

  • Kiểm tra xem đỉnh của danh sách có rỗng không, nếu rỗng thì trả về nil còn không trả về giá trị của đỉnh danh sách.

2.5. Test thử danh sách

2.5.1. Test build stack

2.5.2. Test push stack

2.5.3 Test pop stack

3. Một số ứng dụng của ngăn xếp

3.1. Đảo ngược xâu ký tự

  • Bài toán đảo ngược xâu ký tự yêu cầu hiển thị các ký tự của 1 xâu ký tự theo chiều ngược lại.
  • Ký tự cuối cùng của xâu sẽ được hiển thị trước, tiếp theo là ký tự sát ký tự cuối … và ký tự đầu tiên sẽ được hiển thị đầu tiên.
  • Để giải quyết bài toán, ta chỉ cần duyệt từ đầu đến cuối xâu, lần lượt cho các ký tự vào ngăn xếp.
  • Khi đó, các ký tự đầu tiên sẽ vào trước, tiếp theo đến ký tự thứ 2 … ký tự cuối cùng vào sau cùng. Sau khi đã cho toàn bộ ký tự của xâu vào ngăn xếp, lần lượt lấy các phần tử ra khỏi ngăn xếp và hiển thị lên màn hình.

3.2. Tính giá trị biểu thức dạng hậu tố

3.2.1. Bài toán

  • Một biểu thức toán học thông thường bao gồm các toán tử: + – * / , các toàn hạng và dấu ngoặc cho biết thứ tụ tính toán.
  • Chẳng hạn 1 biểu thức toán học: (3 * (((5 – 2) * (7 + 1)) – 6)) Như chúng ta đã thấy trong biểu thức trên , các toán tử bao h cũng nằm giữa 2 toàn hạng. Do vậy, cách viết trên được gọi là cách viết trung tố (infix). Để tính toán giá trị biểu thức trên, ta phải tính toán giá trị các phép toán trong ngoặc trước. Đôi khi ta cần lưu các kết quả tính toán này như 1 kết quả trung gian, sau đó sử dụng chúng như toán hạng tiếp theo. Ví dụ ở biểu thức trên, đầu tiên ta tính 5 – 2 = 3, lưu kết quả này lại. Trong các biểu thức dạng này, vị trí dấu ngoặc rất quan trọng. Nếu vị trí các dấu ngoặc thay đổi thì giá trị biểu thức cũng thay đổi theo. Đối với con người, cách trình bày biểu thức toán học theo dạng này có vẻ như là hợp lý nhất, nhưng đối với máy tính, việc tính toán nhũng biểu thức như vậy là tương đối phức tạp. Để dễ dạng cho máy tính trong việc tính toán các biểu thức, người ta đưa ra 1 cách trình bày khác cho biểu thức toán học, đó là dạng hậu tố (postfix).
  • Theo cách trình bày nay, toán tử không nằm giữa 2 toán hạng mà nằm ở ngay phía sau 2 toán hạng. Chẳng hạn ở biểu thức trên ta có thể viết dưới dạng hậu tố như sau: 3 5 2 – 7 1 + * 6 – * Toán tử – nằm ngay sau 2 toán hạng 5 và 2 nên lấy 5 – 2 = 3, lưu kết quả 3. Toán tử + nằm ngay sau 2 toán hạng 7 và 1 nên lấy 7 + 1 = 8, lưu kết quả 8. Toán tử * nằm ngay sau 2 kết quả vừa lưu nên lấy 3 * 8 = 24, lưu kết quả 24. Toán tử – nằm ngay sau kết quả vừa lưu và 6 nên lấy 24 – 6 = 18 Toán tử * nằm ngay sau kết quả vừa lưu và 3 nên lấy 3 * 18 = 54 là kết quả cuối cùng của biểu thức.

3.2.2. Cách thực hiện

Chuyển đổi biểu thức tiền tố sang hậu tố:

  • Duyệt từ trái qua phải.
  • Nếu gặp dấu mở ngoặc thì bỏ qua.
  • Nếu gặp số thì đưa vào biểu thức mới.
  • Nếu gặp toán tử thì đưa vào ngăn xếp.
  • Nếu gặp dấu đóng ngoặc thì lấy toán tử ra đưa vào biểu thức mới.

Tính toán biểu thức hậu tố:

  • Duyệt biểu thức từ trái qua phải.
  • Nếu gặp toán hạng thì đưa vào ngăn xếp.
  • Nếu gặp toán tử, lấy ra 2 toán hạng từ ngăn xếp, sử dụng toán tử để tính, sau đó đưa kết quả vào ngăn xếp.

4. Demo

SHARE

LEAVE A REPLY