Theo em dùng danh sách liên kết để biểu diễn ngăn xếp được hay không?

Có, bạn hoàn toàn có thể sử dụng danh sách liên kết (linked list) để biểu diễn ngăn xếp. Thực tế, danh sách liên kết cung cấp một số lợi thế nhất định so với mảng, đặc biệt khi bạn cần thực hiện các thao tác thêm (push) và xóa (pop) phần tử ở đầu ngăn xếp một cách hiệu quả.

Ưu điểm của việc sử dụng danh sách liên kết để biểu diễn ngăn xếp:

1. Kích thước linh hoạt: Danh sách liên kết không có giới hạn về kích thước cố định như mảng. Bạn có thể thêm hoặc xóa phần tử mà không cần lo lắng về việc tràn ngăn xếp.

2. Hiệu suất cao cho các thao tác thêm/xóa: Thao tác thêm hoặc xóa một phần tử ở đầu danh sách liên kết có độ phức tạp thời gian là O(1)O(1)O(1), trong khi đối với mảng, thao tác thêm/xóa phần tử ở đầu có thể có độ phức tạp thời gian là O(n)O(n)O(n).

Cách biểu diễn ngăn xếp bằng danh sách liên kết:

1. Định nghĩa nút (Node) của danh sách liên kết:

   • Mỗi nút chứa một giá trị và một con trỏ tới nút kế tiếp.

2. Định nghĩa lớp Stack với các thao tác push, pop, và is_empty:

Mã nguồn chi tiết:

class Node:

    def __init__(self, data):

       self.data = data

       self.next = None

class Stack:

    def __init__(self):

        self.top = None  # Đỉnh của ngăn xếp (phần tử đầu của danh sách liên kết)

    def is_empty(self):

        return self.top is None

    def push(self, item):

        new_node = Node(item)

       new_node.next = self.top

        self.top = new_node

    def pop(self):

        if self.is_empty():

           return "Ngăn xếp rỗng"

       popped_node = self.top

        self.top = self.top.next

        return popped_node.data

    def peek(self):

        if self.is_empty():

           return "Ngăn xếp rỗng"

        return self.top.data

# Sử dụng ngăn xếp

stack = Stack()

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

stack.push(1)

stack.push(2)

stack.push(3)

print("Phần tử đỉnh:", stack.peek())  # Output: 3

# Lấy phần tử ra khỏi ngăn xếp (pop)

print("Phần tử lấy ra:", stack.pop())  # Output: 3

print("Phần tử đỉnh:", stack.peek())  # Output: 2

print("Phần tử lấy ra:", stack.pop())  # Output: 2

print("Phần tử đỉnh:", stack.peek())  # Output: 1

print("Phần tử lấy ra:", stack.pop())  # Output: 1

print("Ngăn xếp rỗng:", stack.pop())  # Output: Ngăn xếp rỗng

Giải thích:

1. Lớp Node: Định nghĩa một nút của danh sách liên kết, mỗi nút chứa dữ liệu và con trỏ đến nút kế tiếp.

2. Lớp Stack: Sử dụng danh sách liên kết để biểu diễn ngăn xếp. Bao gồm các phương thức push, pop, peek, và is_empty.

3. Phương thức push: Thêm một phần tử vào đầu ngăn xếp (đầu danh sách liên kết).

4. Phương thức pop: Lấy phần tử ở đầu ngăn xếp ra và trả về giá trị của nó.

5. Phương thức peek: Trả về giá trị của phần tử ở đầu ngăn xếp mà không loại bỏ nó.

6. Phương thức is_empty: Kiểm tra xem ngăn xếp có rỗng hay không.

Như vậy, việc sử dụng danh sách liên kết để biểu diễn ngăn xếp không chỉ khả thi mà còn có thể mang lại nhiều lợi ích trong nhiều tình huống lập trình khác nhau.