Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Ruby

Làm chủ Stack trong Ruby: Kỹ thuật Cấu trúc Dữ liệu Thực hành cho Người mới bắt đầu

Nếu bạn không có bằng CS (Khoa học Máy tính), bạn có thể cảm thấy như đang bỏ lỡ điều gì...

Hoặc bạn có thể cảm thấy CS quá trừu tượng để hữu ích...

Hoặc Ruby đã làm tất cả công việc khó cho bạn...

Dù sao...

Việc hiểu cơ bản về cấu trúc dữ liệu như hash, stack và queue là hữu ích.

Trong bài này:

Bạn sẽ khám phá cách dùng stack trong Ruby.

Một khái niệm khoa học máy tính thực hành bạn có thể bắt đầu áp dụng ngay bây giờ!

Hiểu Stack trong Ruby

Stack trong Ruby là gì?

Stack là cấu trúc dữ liệu bạn có thể dùng như danh sách "cần làm". Bạn liên tục lấy phần tử từ stack và xử lý chúng cho đến khi stack rỗng.

Đây là biểu diễn trực quan.

Push 5 vào stack rỗng:

5

Push 3 vào stack:

3
5

Push 9 vào stack:

9
3
5

Lấy một mục từ stack:

3
5

Điều lớn cần nhận ra ở đây là mục mới được thêm vào đỉnh stack. Theo kiểu "Last-In First-Out" (LIFO). Nghĩa là khi bạn lấy (pop) một mục từ stack, đó sẽ là mục cuối cùng được push vào.

Cách khác hình dung cách này hoạt động là nghĩ về chồng đĩa. Nếu bạn đặt đĩa này lên trên đĩa kia, bạn không thể lấy đĩa dưới nếu không lấy đĩa trên trước.

Đó là tất cả bạn làm với stack, push thứ lên đỉnh hoặc pop thứ ra. Không có chỉ mục.

Hãy xem vài ví dụ mã cách này có thể dùng.

Cách Làm phẳng Mảng dùng Stack

Ví dụ kinh điển của stack là dùng chúng để làm phẳng mảng. Nói cách khác, chuyển mảng đa chiều thành mảng một chiều.

Đây là ví dụ:

arr = [1,2,3,[4,5],6] arr.flatten

Trong Ruby chúng ta có phương thức flatten làm điều này cho bạn. Nhưng nếu bạn không có phương thức này thì sao? Và phương thức này hoạt động như thế nào?

Đây là nơi stack xuất hiện!

Ruby triển khai phương thức push và pop, vì vậy chúng ta có thể đối xử mảng như stack.

Lưu ý: Cả push và << là cùng phương thức. Tôi sẽ dùng << trong ví dụ mã.

Ý tưởng là đi qua mỗi phần tử và kiểm tra nó là mảng hay thứ khác. Nếu là mảng thì chúng ta sẽ push các phần tử bên trong mảng này trở lại stack.

Điều xảy ra là chúng ta liên tục gỡ bỏ các lớp mảng (như bóc hành) cho đến khi không còn lớp nào. Điều này sẽ để lại mảng đã làm phẳng.

Đây là mã:

arr = [1,2,3,[4,5],6] flat = [] arr.each do |thing| if thing.is_a? Array thing.each { |i| arr << i } else flat << thing end end p flat # [1, 2, 3, 6, 4, 5]

Bạn sẽ nhận ra không có lời gọi phương thức pop trong mã này.

Điều này là vì tôi để each làm việc khó khăn lấy mục từ stack và cung cấp cho thuật toán của tôi. Cũng lưu ý thứ tự phần tử không được giữ khi làm cách này.

Phiên bản khác dùng until và empty?:

until arr.empty? thing = arr.pop if thing.is_a? Array thing.each { |i| arr << i } else flat << thing end end p flat # [6, 5, 4, 3, 2, 1]

Vì chúng ta dùng pop giờ, thay vì để each làm việc, chúng ta nhận mảng làm phẳng theo đúng thứ tự... Nhưng ngược lại.

Điều này tiết lộ tính chất thú vị của stack:

Danh sách thứ gì bạn cho vào, nó sẽ trả về theo cùng thứ tự nhưng ngược lại.

Mẹo: Phương thức Array#flatten nhận đối số, cho phép bạn định nghĩa số lớp lồng nhau bạn muốn gỡ (mặc định là tất cả).

Giải quyết Vấn đề Dấu ngoặc Cân bằng

Đây là ví dụ khác và không có phương thức Ruby tương đương làm điều này cho bạn!

Đây cũng là bài toán kinh điển khác trong khoa học máy tính...

Tên là:

Khớp dấu ngoặc cân bằng.

Ý tưởng là bạn được cho một chuỗi và cần xác thực dấu ngoặc có hợp lệ không.

Ví dụ, giả sử bạn đang viết chương trình đánh giá toán học. Bạn muốn chắc chắn đầu vào hợp lệ trước khi xử lý.

Ví dụ (Đầu vào Hợp lệ):

input = "1 + (4 + 6) * 2"

Ví dụ (Đầu vào Không hợp lệ):

input = "1 + (4 + 6 * 2"

Bạn có thể dùng stack theo dõi dấu ngoặc bạn tìm thấy trong đầu vào và khi tìm thấy dấu ngoặc mới, kiểm tra đỉnh stack để chắc chắn nó khớp với dấu ngoặc đóng.

Nếu không khớp, nghĩa là bạn có đầu vào không hợp lệ.

Ví dụ:

PARENS = { "(" => ")", "{" => "}", "[" => "]" } OPENING_PARENS = PARENS.keys CLOSING_PARENS = PARENS.values def valid_parentheses(string) stack = [] string.each_char do |ch| if OPENING_PARENS.include?(ch) stack << ch elsif CLOSING_PARENS.include?(ch) ch == PARENS[stack.last] ? stack.pop : (return false) end end stack.empty? end p valid_parentheses("(){}[]") # true p valid_parentheses("[(])") # false

Điều khác bạn sẽ nhận ra là tôi kết thúc phương thức valid_parentheses với stack.empty?. Đó là để chắc chắn chúng ta không kết thúc với dấu ngoặc chưa đóng.

Nếu tất cả dấu ngoặc được đóng đúng cách thì stack nên rỗng 🙂

Ví dụ 3 (hướng dẫn)

Một ví dụ nữa để chắc chắn bạn hiểu cách áp dụng điều này.

Trong trường hợp này, chúng ta được cho một tập hướng dẫn và được nói rằng cần tối ưu hóa để tiết kiệm thời gian cho người đi đường.

Đây là tập ví dụ:

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]

Bạn sẽ nhận ra nếu bạn đi bắc thì nam, bạn sẽ kết thúc ở cùng nơi (giả sử cùng khoảng cách cả hai hướng). Đó là điều chúng ta cần tối ưu và chúng ta có thể làm đó dùng stack.

Ví dụ:

input = ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"] directions = [] opposites = { "NORTH" => "SOUTH", "SOUTH" => "NORTH", "EAST" => "WEST", "WEST" => "EAST" } input.each do |dir| opposites[dir] == directions.last ? directions.pop : directions << dir end p directions

Kết luận

Tôi hy vọng bạn học được điều gì đó mới và bạn bắt đầu tìm cách dùng stack để giải quyết thách thức lập trình.

Đừng quên chia sẻ bài viết này để nhiều người hơn đọc được!