Ngăn xếp

Trở về Mục lục cuốn sách

Những kiểu dữ liệu trừu tượng

Đến giờ, các kiểu dữ liệu bạn đã từng gặp đều là cụ thể, theo nghĩa là chúng ta đã hoàn toàn chỉ định cách thiết lập chúng. Chẳng hạn, lớp Card để biểu diễn một lá bài bằng hai số nguyên. Như ta đã thảo luận lúc đó, đây không phải là cách duy nhất để biểu diễn một lá bài; còn nhiều cách thiết lập khác nữa.

Một kiểu dữ liệu trừu tượng, hay ADT (Abstract Data Type), quy định một tập hợp các phép tính (hoặc phương thức) và ngữ nghĩa của phép tính (cho biết chúng làm việc gì), nhưng không quy định cách thiết lập những phép tính đó. Đây chính là điều khiến cho chúng trở nên trừu tượng.

Vậy tại sao ADT lại có ích?

  • Vì nó đơn giản hóa nhiệm vụ quy định một thuật toán nếu bạn có thể kí hiệu những phép tính cần thiết mà cùng lúc không phải nghĩ đến cách thực hiện những phép tính đó.
  • Vì thường có nhiều cách thiết lập một ADT, nên có thể sẽ hữu ích nếu ta viết một thuật toán để dùng với bất kì cách thiết lập khả dĩ nào.
  • Các ADT, chẳng hạn như ngăn xếp trong chương này, thường được thiết lập trong những thư viện chuẩn để chúng có thể qua một lần viết mà những lập trình viên có thể dùng nhiều lần.
  • Các phép tính trên ADT cho ta một ngôn ngữ bậc cao thông dụng để quy định và trao đổi ý kiến về thuật toán.

Khi nói về ADT, ta thường phân biệt đoạn mã lệnh dùng đến ADT, được gọi là mã lệnh khách, với mã lệnh thiết lập ADT, gọi là mã lệnh cung cấp.

ADT kiểu ngăn xếp

Trong chương này, ta xét đến một ADT thông dụng, đó là ngăn xếp. Ngăn xếp là một tập hợp, theo nghĩa là nó chứa nhiều phần tử. Các tập hợp khác mà ta đã gặp bao gồm từ điển và danh sách.

Một ADT được định nghĩa bằng những phép thao tác có thể thực hiện với nó; đây được gọi là giao diện. Giao diện của một ngăn xxeesp gồm có những phép thao tác này:

__init__
Khởi tạo một ngăn xếp mới, trống rỗng.
push
Thêm một phần tử vào ngăn xếp.
pop
Gỡ bỏ đồng thời trả lại một phần tử từ ngăn xếp. Phần tử được trả lại luôn là phần tử mới được thêm gần đây nhất.
isEmpty
Kiểm tra xem liệu ngăn xếp có rỗng hay không.

Ngăn xếp đôi khi còn được gọi là cấu trúc dữ liệu “vào sau, ra trước” hay LIFO (last in, first out), bởi phần tử mới được đưa vào nhất chính là thứ sẽ được gỡ bỏ đầu tiên.

Thiết lập ngăn xếp dựa trên cơ sở danh sách Python

Các phép tính đối với danh sách có trong Python cũng giống như các phép thao tác để định nghĩa một ngăn xếp. Tuy rằng giao diện không được chính xác như ta đã dự tính, song ta có thể viết mã lệnh để chuyển từ ADT ngăn xếp sang các phép tính có sẵn.

Mã lệnh được gọi là một implementation của ADT ngăn xếp. Nói chung, implementation là một tập hợp các phương thức để thỏa mãn những yêu cầu cú pháp và ngữ nghĩa của một giao diện.

Sau đây là một implementation của ADT ngăn xếp trong đó dùng đến danh sách Python:

class Stack :
  def __init__(self) :
  self.items = []
  def push(self, item) :
    self.items.append(item)
  def pop(self) :
    return self.items.pop()
  def isEmpty(self) :
    return (self.items == [])

Một đối tượng Stack có chứa một thuộc tính mang tên items vốn là một danh sách các phần tử trong ngăn xếp. Phương thức khởi tạo sẽ đặt items bằng danh sách rỗng.

Để đưa một phần tử mới vào ngăn xếppush có nhiệm vụ bổ sung phần tử này vào items. Để gỡ một phần tử khỏi danh sách,  pop dùng phương thức danh sách cùng tên * Note để gỡ bỏ và trả lại phần tử thuộc danh sách.

Sau cùng, để kiểm tra xem ngăn xếp có rỗng hay không, isEmpty được lập ra để so sánh items với danh sách rỗng.

Một implementation như thế này, trong đó các phương thức có chứa những lời gọi đơn giản đến những phương thức sẵn có, được gọi là véc-ni. Ngoài đời, véc-ni là lớp phủ mỏng bằng gỗ tốt để bọc ngoài gỗ xấu của đồ đạc trong nhà. Hình ảnh ẩn dụ này được dùng trong khoa học máy tính để chỉ một đoạn mã lệnh ngắn để che giấu chi tiết implementation và cung cấp một giao diện đơn giản hoặc giống tiêu chuẩn hơn.

Thêm vào và gỡ bỏ

Ngăn xếp là một cấu trúc dữ liệu tổng quát, theo nghĩa ta có thể bổ sung bất kì kiểu dữ liệu nào vào nó. Ví dụ sau đây thêm hai số nguyên và một chuỗi vào danh sách:

>>> s = Stack()
>>> s.push(54)
>>> s.push(45)
>>> s.push("+")

Ta có thể dùng isEmpty và pop để gỡ bỏ rồi in ra tất cả những phần tử trên ngăn xếp:

while not s.isEmpty() :
  print s.pop(),

Kết quả là + 45 54. Nói cách khác, ta vừa mới dùng một ngăn xếp để in ra các phần tử theo chiều ngược lại! Công nhận rằng đây không phải là cách chuẩn mực để in ra danh sách, nhưng bằng cách dùng ngăn xếp, điều này thật dễ thực hiện.

Bạn cần so sánh đoạn mã này với implementation của printBackward trong Chương “Danh sách liên kết“. Tự nó có một sự đối chiếu giữa dạng đệ quy của printBackward và thuật toán ngăn xếp ở đây. Sự khác biệt là printBackward dùng ngăn xếp lúc thực thi để theo dõi các nút trong quá trình duyệt danh sách, rồi in ra các nút này trên đường trở lại sau đệ quy. Thuật toán ngăn xếp cũng làm điều này, song khác là nó dùng đối tượng Stack chứ không phải là một ngăn xếp hình thành nên khi thực thi chương trình.

Dùng ngăn xếp để lượng giá biểu thức hậu tố

Với đa số ngôn ngữ lập trình, các biểu thức toán được viết bằng cách đặt toán tử vào giữa hai toán hạng, như là 1+2. Hình thức này được gọi là trung tố. Một cách khác được một số máy tính tay sử dụng, đó là hình thức hậu tố. Với hình thức này, toán tử đi theo sau các toán hạng, như 1 2 +.

Dạng hậu tố đôi khi hữu ích là bởi có một cách tự nhiên để lượng giá một biểu thức hậu tố bằng một ngăn xếp:

  • Đọc biểu thức từ trái qua phải, mỗi lúc chỉ lấy một thứ (toán hạng hoặc toán tử).
    • Nếu đó là toán hạng, hãy đẩy vào ngăn xếp.
    • Nếu đó là toán tử, hãy gỡ hai toán hạng khỏi ngăn xếp, rồi thực hiện phép toán đối với chúng, sau đó đẩy kết quả trở lại ngăn xếp.
  • Khi đọc đến cuối biểu thức, sẽ có đúng một toán hạng còn lại trong ngăn xếp. Toán hạng này chính là kết quả.

Bài tập: Hãy áp dụng thuật toán này cho biểu thức 1 2 + 3 *.

Ví dụ này cho thấy ưu điểm của hình thức hậu tố     không cần dùng cặp ngoặc đơn để kiểm soát thứ tự của phép tính. Muốn thu được cùng kết quả bằng việc sử dụng hình thức trung tố, ta phải viết thành (1 + 2) * 3.

Bài tập: Hãy viết dạng biểu thức trung tố tương đương với 1 + 2 * 3.

Phân tách

Để thực hiện thuật toán trên, ta cần phải duyệt được một chuỗi và phá vỡ nó thành những toán hạng và toán tử riêng. Quá trình này là một ví dụ của việc phân tách, và những kết quả     từng phân đoạn của chuỗi     được gọi là nguyên tố. Có thể bạn còn nhớ hai thuật ngữ này từ Chương 1.

Python có một phương thức split trong cả hai modlule string và re (biểu thức chính quy). Hàm string.split phân tách một chuỗi thành danh sách, bằng những kí tự gọi là dấu phân cách. Chẳng hạn:

>>> import string
>>> string.split("Now is the time"," ")
  ['Now''is''the''time']

Trong trường hợp này, dấu phân cách chính là dấu trống (dấu cách), bởi vậy chuỗi được chia thành các từ đơn riêng biệt.

Hàm re.split thì mạnh hơn; nó cho ta dùng một biểu thức chính quy thay vì một dấu phân cách. Biểu thức chính quy là cách quy định một tập hợp các chuỗi. Chẳng hạn, [A-z] là tập hợp các chữ cái còn [0-9] là tập hợp các chữ số. Toán tử ^ phủ định một tập hợp, vì vậy [^0-9] là tập hợp của tất cả những kí tự không phải là chữ số; đây chính là tập hợp màm ta muốn dùng để phân tách biểu thức hậu tố:

>>> import re
>>> re.split("([^0-9])""123+456*/")
  ['123''+''456''*''''/'''] 

Có thể nhận thấy rằng thứ tự các đối số đã khác đi so với string.split; ở đây dấu phân cách đứng trước chuỗi.

Danh sách thu được bao gồm các toán hạng 123 và 456 cùng các toán tử * và /. Nó cũng gồm hai chuỗi rỗng được đưa vào với vai trò “phantom operands,” mỗi khi có một toán tử xuất hiện mà trước và sau nó không có con số nào.

Lượng giá biểu thức hậu tố

Để lượng giá một biểu thức hậu tố, ta sẽ dùng chương trình phân tách từ mục trên và thuật toán ở mục trước đó nữa. Để đơn giản, ta sẽ bắt đầu bằng một hàm lượng giá trong đó có xử lý các phép + và *:

def evalPostfix(expr):
  import re
  tokenList = re.split("([^0-9])", expr)
  stack = Stack()
  for token in tokenList:
    if  token == '' or token == ' ':
      continue
    if  token == '+':
      sum = stack.pop() + stack.pop()
      stack.push(sum)
    elif token == '*':
      product = stack.pop() * stack.pop()
      stack.push(product)
    else:
      stack.push(int(token))
  return stack.pop()

Điều kiện đầu xử lý các dấu cách và chuỗi rỗng. Hai điều kiện tiếp theo xử lý các toán tử. Hiện giờ, ta giả thiết rằng mọi thứ khác ngoài những trường hợp trên thì đều là toán hạng. Dĩ nhiên, tốt hơn là cần phải kiểm tra điều kiện đầu vào bị lỗi hay không, và báo cáo một thông báo lỗi, song ta sẽ đến phần đó sau.

Hãy thử kiểm tra đoạn mã lệnh trên bằng cách lượng giá biểu thức hậu tố của (56+47)*2:

>>> print evalPostfix ("56 47 + 2 *")
  206

Kết quả này là chính xác.

Khách và chủ

Một trong những mục tiêu cơ bản của ADT là nhằm tách riêng những mối quan tâm của phía chủ, người viết mã lệnh dựng nên ADT, và phía khách, người sử dụng ADT. Phía chủ chỉ cần lo xem liệu rằng implementation có đúng không     so với quy định của ADT     chứ không cần biết nó sẽ được dùng như thế nào.

Ngược lại, phía khách giả sử rằng  implementation của ADT là đúng và không để ý gì đến chi tiết. Khi bạn dùng các kiểu dữ liệu có sẵn trong Python thì bạn được ưu tiên đối xử như phía khách.

Dĩ nhiên, khi bạn dựng nên một ADT, bạn cũng phải viết mã lệnh phía khách để kiểm tra nó. Trong trường hợp này, bạn đóng cả hai vai trò; điều này có thể gây nhầm lẫn. Bạn cũng cần cố gắng theo dõi vai trò mình đang đảm nhiệm trong mọi thời điểm.

1 Phản hồi

Filed under Think Python

One response to “Ngăn xếp

  1. Pingback: Cách nghĩ như nhà khoa học máy tính | Blog của Chiến

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s