Stack là gì

Stack (ngăn xếp) là một cấu trúc dữ liệu mà bạn có thể sử dụng nó như là một "to-do" list. Bạn có thể thêm phần tử vào hoặc lấy ra từng phần tử của stack và xử lý, thao tác với chúng tới khi stack rỗng (không còn phần tử nào nữa). Sau đây là một ví dụ đơn giản của stack

Push 5 into an empty stack: 5

Push 3 into the stack: 3 5

Push 9 into the stack: 9 3 5

Take one item from the stack: 3 5

Điểm đặc trưng và cần chú ý nhất của stack là những phần tử mới sẽ được thêm vào đầu của stack, được gọi là top. Hoạt động của stack còn được gọi là "Last-In First-Out" (LIFO). Điều đó có nghĩa là phần tử cuối cùng được đưa vào ngăn xếp sẽ là phần tử đầu tiên được lấy ra. Thao tác đẩy vào và lấy ra trong ngăn xếp được gọi là push và pop Thực tế hơn, bạn có thể hiểu stack như một chồng đĩa. Khi bạn đặt một chiếc đĩa vào chồng đĩa thì chiếc đĩa bạn lấy ra đầu tiên phải là chiếc đĩa cuối cùng bạn đặt vào. Tất cả những gì khi bạn thao tác với stack chỉ đơn giản là push và pop

Để hiểu rõ hơn về cách hoạt động cũng như tác dụng của stack thì chúng ta hãy cùng thực hiện một vài ví dụ sau

Ví dụ 1: Convert mảng đa chiều thành mảng một chiều

Ví dụ điển hình và đơn giản nhất chính là việc convert một mảng nhiều chiều thành mảng một chiều.

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

Trong Ruby thì chúng ta đã có sẵn method flatten để thực hiện nhiệm vụ này. Tuy nhiên để hiểu hơn về stack cũng như method flatten hoạt động như thế nào thì chúng ta sẽ dùng stack để giải quyết vấn đề này. Ruby đã cung cấp sẵn method push và pop cho array nên chúng ta có thể sử dụng như là với stack. Ý tưởng ở đây là chúng ta sẽ duyệt từng phần tử của mảng ban đầu. Với một phần tử, chúng ta sẽ kiểm tra xem nó có phải là một mảng hay không. Nếu là một mảng thì chúng ta sẽ push từng phần tử của mảng đó vào phía sau mảng ban đầu, còn nếu nó không phải là một array thì ta sẽ push nó vào mảng kết quả. Quá trình này sẽ được thực hiện đến khi ta duyệt hết các phần tử trên mảng ban đầu.

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

Trong đoạn code này, bạn có thể thấy là tôi không sử dụng method pop. Đó là bởi vì tôi đã sử dụng method each để thực hiện việc lấy từng phần tử của stack để duyệt. Một điều chú ý nữa đó là với thuật toán này, thứ tự các phần tử của mảng ban đầu sẽ bị thay đổi. Và nếu bạn thắc mắc là nếu sử dụng pop thay vì each sẽ như thế này thì đây là câu trả lời cho bạn

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ới việc sử dụng pop thay cho each, chúng ta đã có được mảng kết quả theo đúng thứ tự nhưng lại theo chiều ngược lại. Điều này cũng chính là một điểm đặc trưng của stack như đã nói ở trên: Last-In First-Out

Ví dụ 2: Biểu thức ngoặc hợp lệ

Bài toán ở đây là cho một chuỗi kí tự chứa các dấu ngoặc và nhiệm vụ của bạn là hãy xác định xem các dấu ngoặc đó có hợp lệ hay không. Hay nói một cách khác, bạn phải xác định xem chuỗi kí tự đó có phải là một biểu thức hợp lệ hay không. Ví dụ về input hợp lệ:

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

Ví dụ về input không hợp lệ:

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

Ý tưởng ở đây sẽ duyệt từng ký tự của xâu. Với mỗi một ký tự, nếu nó là dấu ngoặc mở thì ta sẽ push vào stack. Trong trường hợp nó là dấu ngoặc đóng, ta sẽ check xem nó có khớp với dấu ngoặc mở ở top của stack không, nếu khớp thì ta sẽ pop dấu ngoặc ở top của stack, nếu không khớp nghĩa là xâu input không hợp lệ. Sau khi quá trình duyệt kết thúc, nếu stack của chúng ta rỗng thì xâu input sẽ là hợp lệ và ngược lại.

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

Ví dụ 3: Tối ưu hóa đường đi

Bài toán cuối cùng được đặt ra khá thú vị. Bạn được cung cấp một danh sách các địa điểm đến theo hướng (Đông, Tây, Nam, Bắc) và nhiệm vụ của bạn đó là phải tối ưu các bước đi sao cho số lần di chuyển là ít nhất mà vẫn đến được điểm cuối cùng sau khi đã kết thúc hành trình. Ví dụ về input:

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

Bạn có thể nhận ra rằng nếu bạn đi về hướng bắc, sau đó lại đi về hướng nam thì bạn sẽ quay lại vị trí ban đầu, và nhiệm vụ của chúng ta là phải lược bớt những bước di chuyển thừa như trên. Hãy cùng theo dõi đoạn code sau để biết được stack sẽ giúp chúng ta giải quyết bài toán này như thế nào

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

Bài về về stack của tôi đến đây là kết thúc, cảm ơn các bạn đã theo dõi. Hi vọng bài viết sẽ giúp các bạn hiểu hơn cũng như sử dụng hiệu quả Stack.

Reference

http://www.blackbytes.info/2017/03/computer-science-in-ruby-stacks/