Data Structures – Cấu trúc dữ liệu (P2)

Cấu trúc dữ liệu là khối xây dựng cơ bản của lập trình máy tính. Chúng xác định cách tổ chức, lưu trữ và thao tác dữ liệu trong một chương trình. Hiểu cấu trúc dữ liệu là rất quan trọng để phát triển các thuật toán hiệu quả và hiệu quả. Trong hướng dẫn này, chúng ta sẽ khám phá các cấu trúc dữ liệu được sử dụng phổ biến nhất, như Arrays, Linked Lists, Stacks, Queues, Trees and Graphs, …

Các cấu trúc dữ liệu phổ biến

3. Stack

Ngăn xếp là một cấu trúc dữ liệu tuyến tính tuân theo một thứ tự cụ thể trong đó các thao tác được thực hiện. Thứ tự có thể là LIFO(Last In First Out) hoặc FILO(First In Last Out). Trong ngăn xếp, tất cả việc chèn và xóa chỉ được phép ở một đầu của danh sách.

Hoạt động ngăn xếp:

• push(): Khi thao tác này được thực hiện, một phần tử sẽ được chèn vào ngăn xếp.
• pop(): Khi thao tác này được thực hiện, một phần tử sẽ bị xóa khỏi đỉnh ngăn xếp và được trả về.
• top(): Thao tác này sẽ trả về phần tử được chèn cuối cùng ở trên cùng mà không xóa nó.
• size(): Thao tác này sẽ trả về kích thước của ngăn xếp tức là tổng số phần tử có trong ngăn xếp.
• isEmpty(): Thao tác này cho biết ngăn xếp có trống hay không.

4. Queue

Giống như Stack, Queue là một cấu trúc tuyến tính tuân theo một thứ tự cụ thể trong đó các thao tác được thực hiện. Thứ tự là First In First Out (FIFO). Trong hàng đợi, các mục được chèn vào một đầu và bị xóa ở đầu kia. Một ví dụ điển hình về hàng đợi là bất kỳ hàng đợi nào của người tiêu dùng đối với một tài nguyên mà người tiêu dùng đến trước sẽ được phục vụ trước. Sự khác biệt giữa ngăn xếp và hàng đợi là ở việc loại bỏ. Trong ngăn xếp, chúng tôi xóa mục được thêm gần đây nhất; trong hàng đợi, chúng tôi xóa mục ít được thêm gần đây nhất. 

Hoạt động xếp hàng:

• Enqueue(): Thêm (hoặc lưu trữ) một phần tử vào cuối hàng đợi..
• Dequeue(): Loại bỏ các phần tử khỏi hàng đợi.
• Peek() hoặc front(): Lấy phần tử dữ liệu có sẵn ở nút phía trước của hàng đợi mà không xóa nó.
• Rear(): Thao tác này trả về phần tử ở phía sau mà không loại bỏ nó.
• isFull(): Xác thực nếu hàng đợi đầy.
• isNull(): Kiểm tra xem hàng đợi có trống không.

5. Binary Tree – Cây nhị phân

Không giống như Array, Linked List, queue và stack là các cấu trúc dữ liệu tuyến tính, cây là cấu trúc dữ liệu phân cấp. Cây nhị phân là một cấu trúc dữ liệu cây trong đó mỗi nút có tối đa hai con, được gọi là con trái và con phải. Nó được thực hiện chủ yếu bằng cách sử dụng Liên kết. 

Cây nhị phân được biểu thị bằng một con trỏ tới nút trên cùng trong cây. Nếu cây trống thì giá trị của gốc là NULL. Nút Cây nhị phân chứa các phần sau. 

1. Data
2. Pointer to left child
3. Pointer to the right child

6. Binary Search Tree – Cây nhị phân tìm kiếm

A Binary Search Tree is a Binary Tree following the additional properties: 

• The left part of the root node contains keys less than the root node key.
• The right part of the root node contains keys greater than the root node key.
• There is no duplicate key present in the binary tree.

A Binary tree having the following properties is known as Binary search tree (BST).

Cùng theo dõi tiếp phần sau!