Lưu trữ Stack bằng Python List

Ngăn xếp (Stack) là một trong những cấu trúc dữ liệu cơ bản nhất mà chắc chắn sinh viên ngành Công nghệ thông tin nào cũng phải học. Ngăn xếp được ứng dụng trong nhiều giải thuật của các ngành khác nhau. Trong bài viết này, mình sẽ đồng hành cũng với các bạn tìm hiểu Ngăn xếp là gì, cách thức cài đặt Ngăn xếp với Python và một vài những ứng dụng đơn giản nhé. Chúng ta hãy cùng bắt đầu thôi nào! Let’s get started!

1. Định nghĩa ngăn xếp

Ngăn xếp (Stack) là một kiểu danh sách tuyến tính đặc biệt mà phép bổ sung và phép loại bỏ được thực hiện ở một đầu, đầu đó gọi là đỉnh (Top).
Trong đó, danh sách (List) được xem như một tập có thứ tự nhưng bao gồm một số biến động các phần tử. Hai phép bổ sung và loại bỏ được thực hiện thường xuyên. Điều này sẽ khác biệt so với mảng (Array), không có phép bổ sung phần tử hay phép loại bỏ phần tử. Danh sách tuyến tính là danh sách mà quan hệ lân cận giữa các phần tử được xác định ra.
Ta có thể hình dung Ngăn xếp như một hộp bánh chỉ có một đầu hở. Ban đầu, hộp bánh rỗng, giá trị chỉ số đỉnh (Top) mang giá trị bằng 0. Khi ta bỏ một cái bánh vào trong hộp thì giá trị đỉnh tăng lên giá trị là 1. Nếu bỏ ra ngoài một cái bánh thì giá trị đỉnh giảm đi 1 đơn vị. Nói một cách khác, chỉ số đỉnh này sẽ tăng lên hay giảm đi thì phản ánh Ngăn xếp có hoạt động hay không.

Mô tả hoạt động của Ngăn xếp

Nhận thấy rằng, những cái bánh càng ở trên cao thì khi lấy bánh ra thì nó sẽ được lấy ra sớm hơn. Như vậy, nguyên tắc hoạt động của Ngăn xếp là “Vào sau – Ra trước” hay Last in – First out (LIFO).

2. Mô tả hoạt động của Ngăn xếp

Cấu trúc dữ liệu Ngăn xếp có cấu trúc đơn giản nhất, nhưng Ngăn xếp được sử dụng trong nhiều các ứng dụng khác nhau và là công cụ cho nhiều cấu trúc dữ liệu và các thuật toán phức tạp. Ta đặt S là đại diện cho Ngăn xếp (Stack), khi đó S phải hỗ trợ tối thiểu hai phương thức sau:

• S.push(x): Bổ sung thêm một phần tử x vào đỉnh của Ngăn xếp S.
• S.pop(): Loại bỏ và trả về giá trị của phần tử đỉnh của Ngăn xếp S. Nếu S rỗng thì trả về thông báo Ngăn xếp rỗng.

Ngoài ra, Ngăn xếp S còn có thêm những phương thức sau để thuận tiện trong quá trình làm việc:

• S.top(): Trả về giá trị của phần tử đỉnh Ngăn xếp, nhưng không loại bỏ phần tử này. Nếu S rỗng thì trả về thông báo Ngăn xếp rỗng.
• S.is_empty(): Trả về giá trị True nếu S không chứa phần tử nào.
• len(S): Trả về số lượng các phần tử trong Ngăn xếp S. Trong Python, ta triển khai phương thức này với phương thức __len__.

3. Lưu trữ Ngăn xếp bằng Python List

Kiểu List trong Python được sử dụng để mô tả cách thức lưu trữ cũng như hoạt động của Stack. Khi sử dụng phương thức append để bổ sung một phần tử vào biến List, phần tử mới đó được chèn vào ngay sau phần tử cuối cùng của biến. Phương thức pop trong List được dùng để xóa phần tử cuối cùng của biến List. Ngăn xếp rỗng thì biến List rỗng.

Sử dụng List để lưu trữ như Stack

4. Bài tập

Bài 1: Cài đặt cấu trúc dữ liệu ngăn xếp sử dụng cấu trúc lưu trữ kế tiếp với phần tử dữ liệu là số nguyên. Sử dụng ngăn xếp chuyển một số nguyên dương hệ 10 sang hệ 2. Yêu cầu: trong chương trình có tạo và sử dụng lớp Stack.

# Xay dung lop
class Stack:

    # Ham khoi tao
    def __init__(self):
        self.s = []

    # Ham bo sung
    def push(self, x):
        self.s.append(x)

    # Ham loai bo
    def pop(self):
        if len(self.s) == 0:
            return "stack is empty"
        return self.s.pop()

    # Ham kiem tra Ngan xep rong
    def is_empty(self):
        return len(self.s) == 0

    # Ham tra ve gia tri dinh
    def top(self):
        if len(self.s) == 0:
            return "stack is empty"
        return self.s[-1]

    # Ham tinh do dai Ngan xep
    def __len__(self):
        return len(self.s)

    # Ham hien thi cac phan tu trong Ngan xep
    def __str__(self):
        return "Stack is " + str(self.s)


# Ham main
if __name__ == "__main__":
    # Khai bao doi tuong
    S = Stack()

    # Nhap so nguyen
    n = int(input("Nhap vao so nguyen duong n = "))

    # Chuyen doi sang he 2
    thuong = n
    while thuong:
        S.push(thuong % 2)
        thuong //= 2

    # Hien thi ket qua
    print("He nhi phan cua", n, "la: ", end="")
    while not S.is_empty():
        print(S.pop(), end="")

Tài liệu tham khảo:

1. Data Structures and Algorithms in Python, Michael T. Goodrich & Roberto Tamassia & Michael H. Goldwasser
2. Giáo trình cấu trúc dữ liệu, Đỗ Xuân Lôi