Các cấu trúc dữ liệu cơ bản

Mục lục- Cấu trúc dữ liệu cơ bản

• Ngăn xếp (stack)
• Hàng đợi (queue)
• Hàng đợi hai đầu (deque)
• Mảng tuần tự và bộ nhớ
• Tìm hiểu sơ lược về bộ nhớ
• Mảng tuần tự
• Hạn chế của mảng tuần tự: cần biết trước kích thước dữ liệu để cấp phát không gian lưu trữ liên tục, và khi mở rộng phải di chuyển dữ liệu.
• Danh sách liên kết (Linked list)
• Cây nhị phân

Ngăn xếp (stack)

Ngăn xếp (stack) là một danh sách tuyến tính có giới hạn hoạt động. Chỉ cho phép thêm hoặc xóa phần tử ở một đầu gọi là đỉnh ngăn xếp.
Phần tử mới được thêm vào trên cùng phần tử hiện tại, trở thành phần tử mới ở đỉnh ngăn xếp. Khi xóa, phần tử ở đỉnh bị loại bỏ,
và phần tử liền kề trở thành đỉnh mới.

Ngăn xếp tuân theo nguyên tắc sau cùng vào, trước cùng ra (LIFO).

- Đặc điểm: cấu trúc dữ liệu nhập sau xuất trước.

# Ứng dụng: mỗi trình duyệt web đều có nút "quay lại". Các trang web bạn đã duyệt được lưu trong ngăn xếp (thực tế là địa chỉ URL).
Trang hiện tại nằm ở đỉnh, trang đầu tiên bạn xem nằm dưới đáy. Nếu nhấn 'quay lại', các trang sẽ được hiển thị theo thứ tự ngược lại.

# Thực hiện ngăn xếp bằng Python
class Pile():
    def __init__(self):
        self.data = []
    def add(self, element):
        self.data.append(element)
    def remove(self):
        return self.data.pop()
    def top(self):
        return len(self.data) - 1 if self.data else None
    def is_empty(self):
        return not bool(self.data)
    def count(self):
        return len(self.data)

pile = Pile()
pile.add(10)
pile.add(20)
pile.add(30)

print('Chỉ số phần tử đỉnh:', pile.top())
print('Kiểm tra rỗng:', pile.is_empty())
print('Số lượng phần tử:', pile.count())
print(pile.remove())
print(pile.remove())
print(pile.remove())

Hàng đợi (queue)

- Hàng đợi: theo nguyên tắc nhập trước xuất trước (FIFO).
- Trường hợp áp dụng:
    - Phòng máy tính của trường có 30 máy tính nối mạng với một máy in. Khi học sinh muốn in tài liệu,
các tác vụ in được xếp hàng chờ. Tác vụ đầu tiên vào sẽ được xử lý trước.
Nếu bạn là người cuối cùng, bạn phải chờ tất cả các tác vụ khác hoàn thành.

# Thực hiện hàng đợi bằng Python
class Line():
    def __init__(self):
        self.data = []
    def enqueue(self, element):
        self.data.insert(0, element)
    def dequeue(self):
        return self.data.pop() if self.data else None
    def is_empty(self):
        return not bool(self.data)
    def size(self):
        return len(self.data)

line = Line()
line.enqueue("Task1")
line.enqueue("Task2")
line.enqueue("Task3")
print(line.dequeue())
print(line.dequeue())
print(line.dequeue())    

# Bài tập phỏng vấn
- Trò chơi truyền tay nóng: 6 trẻ em ngồi thành vòng tròn, đứa đầu tiên cầm quả bóng nóng,
sau mỗi giây nó được truyền cho đứa kế tiếp. Quy định rằng sau mỗi 7 giây, đứa nào đang giữ bóng sẽ bị loại khỏi trò chơi.
Trò chơi kết thúc khi chỉ còn một đứa trẻ, đứa đó thắng cuộc. Hãy sử dụng hàng đợi để mô phỏng chiến lược này.
# Cách giải quyết
    - Giữ đứa trẻ đang giữ bóng luôn ở đầu hàng đợi.
class Line():
    def __init__(self):
        self.data = []
    def enqueue(self, kid):
        self.data.insert(0, kid)
    def dequeue(self):
        return self.data.pop() if self.data else None
    def size(self):
        return len(self.data)

children = ['A','B','C','D','E','F']
line = Line()
for child in children:
    line.enqueue(child) # A ở đầu, F ở cuối
while line.size() > 1:
    for _ in range(6): # Mỗi lần lặp, bóng được truyền một lần
        kid = line.dequeue()
        line.enqueue(kid)
    line.dequeue()
winner = line.dequeue()
print('Người chiến thắng là:', winner)
for index, child in enumerate(children):
    if child == winner:   
        print(f'Vị trí thứ {index + 1} sẽ giành chiến thắng.')

Hàng đợi hai đầu (deque)

Khác với hàng đợi thông thường, hàng đợi hai đầu có thể thêm hoặc xóa phần tử từ cả hai đầu.
Nó kết hợp đặc điểm của cả ngăn xếp và hàng đợi trong một cấu trúc duy nhất.

# Thực hiện hàng đợi hai đầu bằng Python
class DualQueue():
    def __init__(self):
        self.data = []
    def add_front(self, item):
        self.data.insert(0, item)
    def add_rear(self, item):
        self.data.append(item)
    def remove_front(self):
        return self.data.pop(0) if self.data else None
    def remove_rear(self):
        return self.data.pop() if self.data else None
    def is_empty(self):
        return not bool(self.data)
    def size(self):
        return len(self.data)

dq = DualQueue()
dq.add_front("A")
dq.add_front("B")
dq.add_front("C")

print(dq.remove_rear())
print(dq.remove_rear())
print(dq.remove_rear())

- Ví dụ ứng dụng: kiểm tra chuỗi đối xứng
    - Chuỗi đối xứng là chuỗi mà đọc từ trái sang phải giống từ phải sang trái, ví dụ: radar, toot, madam.
class DualQueue():
    def __init__(self):
        self.data = []
    def add_front(self, char):
        self.data.insert(0, char)
    def add_rear(self, char):
        self.data.append(char)
    def remove_front(self):
        return self.data.pop(0) if self.data else None
    def remove_rear(self):
        return self.data.pop() if self.data else None
    def is_empty(self):
        return not bool(self.data)
    def size(self):
        return len(self.data)

def is_palindrome(s):
    dq = DualQueue()
    for ch in s:
        dq.add_front(ch)
    while dq.size() > 1:
        if dq.remove_front() != dq.remove_rear():
            return False
    return True

print(is_palindrome("civic"))
# Kết quả
True

Mảng tuần tự và bộ nhớ

• Hiểu sơ lược về bộ nhớ

- Bộ nhớ trong máy tính dùng để lưu trữ và thực hiện các phép toán trên dữ liệu nhị phân.
- Vấn đề: Máy tính tính toán 1+2 như thế nào?
    - Đưa các số 1 và 2 dưới dạng nhị phân vào bộ nhớ, sau đó sử dụng寄 register để thực hiện phép tính.
- Khái niệm biến:
    - Biến là tham chiếu đến một vùng nhớ cụ thể.
    - Mỗi vùng nhớ có hai thuộc tính mặc định:
        - Kích thước vùng nhớ:
            - bit (bit): một bit chỉ lưu trữ được một số nhị phân.
            - byte (byte): 8 bit.
            - kb: 1024 byte.
        - Địa chỉ vùng nhớ:
            - Được biểu diễn bằng giá trị thập lục phân.
            - Vai trò: giúp CPU tìm kiếm chính xác vị trí dữ liệu.

- Hiểu cách a=10 được biểu diễn trong bộ nhớ (tham chiếu, chỉ hướng).
    - Tham chiếu: biến ====> địa chỉ vùng nhớ.
    - a = 10: biến a/địa chỉ/vùng nhớ.
    - Chỉ hướng: nếu biến hoặc tham chiếu đại diện cho một địa chỉ vùng nhớ, thì biến hoặc tham chiếu đó chỉ hướng tới vùng nhớ đó.

• Mảng tuần tự

- Tập hợp các phần tử được sắp xếp theo thứ tự. Có thể tồn tại dưới hai dạng: đơn kiểu dữ liệu (np.array) và đa kiểu dữ liệu (list, tuple).

- List và tuple trong Python là ví dụ về mảng tuần tự đa kiểu dữ liệu.

- Mô hình bộ nhớ của mảng tuần tự đơn kiểu (khai báo liên tục, mỗi vùng nhớ có cùng kích thước).

- Mô hình bộ nhớ của mảng tuần tự đa kiểu (khai báo không liên tục).

• Hạn chế của mảng tuần tự: Cần biết trước kích thước dữ liệu để cấp phát không gian lưu trữ liên tục, và khi mở rộng phải di chuyển dữ liệu.

Danh sách liên kết (Linked list)

- Danh sách liên kết là một cấu trúc dữ liệu tuyến tính phổ biến, nhưng không lưu trữ dữ liệu liên tục như mảng tuần tự,
mà mỗi nút (đơn vị lưu trữ dữ liệu) chứa thông tin về nút tiếp theo (địa chỉ).

- So với mảng tuần tự, danh sách liên kết tận dụng tối đa không gian bộ nhớ máy tính, cung cấp khả năng quản lý bộ nhớ linh hoạt và không cần di chuyển dữ liệu khi mở rộng.

- Thực hiện danh sách liên kết đơn bằng Python

. is_empty(): Kiểm tra danh sách có rỗng không.

. length(): Độ dài danh sách.

. travel(): Duyệt toàn bộ danh sách.

. add(item): Thêm phần tử vào đầu danh sách.

. append(item): Thêm phần tử vào cuối danh sách.

. insert(pos, item): Thêm phần tử tại vị trí chỉ định.

. remove(item): Xóa nút.

. search(item): Tìm kiếm nút.

# Mã nguồn
class Node():
    def __init__(self, data):
        self.data = data
        self.next = None
        
class LinkedList():
    def __init__(self):
        self.head = None
    def add(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node
    def traverse(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next
    def is_empty(self):
        return self.head is None
    def size(self):
        current = self.head
        count = 0
        while current:
            count += 1
            current = current.next
        return count
    def append(self, data):
        node = Node(data)
        if not self.head:
            self.head = node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = node
    def search(self, data):
        current = self.head
        while current:
            if current.data == data:
                return True
            current = current.next
        return False
    def insert(self, pos, data):
        if pos == 0:
            self.add(data)
            return
        node = Node(data)
        current = self.head
        previous = None
        for _ in range(pos):
            previous = current
            current = current.next
        previous.next = node
        node.next = current
    def remove(self, data):
        current = self.head
        previous = None
        while current:
            if current.data == data:
                if previous:
                    previous.next = current.next
                else:
                    self.head = current.next
                return
            previous = current
            current = current.next

Cây nhị phân

• Cây nhị phân
• Nút gốc
• Lá cây:
• Lá trái
• Lá phải
• Cấp độ/cao độ của cây
• Duyệt cây nhị phân
• Duyệt theo chiều rộng
• Duyệt từng lớp các nút.
• Duyệt theo chiều sâu
• Trước: gốc-trái-phải
• Giữa: trái-gốc-phải
• Sau: trái-phải-gốc

# Thực hiện cây nhị phân bằng Python
class TreeNode():
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    
class BinaryTree():
    def __init__(self):
        self.root = None
    def add_node(self, value):
        node = TreeNode(value)
        if not self.root:
            self.root = node
            return
        current = self.root
        queue = [current]
        while queue:
            temp = queue.pop(0)
            if not temp.left:
                temp.left = node
                return
            else:
                queue.append(temp.left)
            if not temp.right:
                temp.right = node
                return
            else:
                queue.append(temp.right)
    def breadth_traversal(self):
        current = self.root
        queue = [current]
        while queue:
            temp = queue.pop(0)
            print(temp.value)
            if temp.left:
                queue.append(temp.left)
            if temp.right:
                queue.append(temp.right)
                
    def preorder(self, node): # Duyệt trước: gốc-trái-phải
        if node:
            print(node.value)
            self.preorder(node.left)
            self.preorder(node.right)
    def inorder(self, node): # Duyệt giữa: trái-gốc-phải
        if node:
            self.inorder(node.left)
            print(node.value)
            self.inorder(node.right)
    def postorder(self, node): # Duyệt sau: trái-phải-gốc
        if node:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.value)