Giải chuyên đề Tin 12 KNTT Bài 4: Kiểu dữ liệu hàng đợi có đáp án

a) Có thể cài đặt hàng đợi bằng mảng một chiều tương tự như ngăn xếp được không?

Có, có thể cài đặt hàng đợi (queue) bằng mảng một chiều tương tự như ngăn xếp (stack) bằng cách sử dụng danh sách (list) trong Python. Tuy nhiên, hàng đợi và ngăn xếp có cách thức hoạt động khác nhau. Trong khi ngăn xếp tuân theo nguyên tắc LIFO (Last In, First Out - Vào sau, ra trước), hàng đợi tuân theo nguyên tắc FIFO (First In, First Out - Vào trước, ra trước). Để cài đặt hàng đợi bằng mảng một chiều, ta cần phải quản lý việc thêm phần tử vào cuối hàng đợi (enqueue) và lấy phần tử ra từ đầu hàng đợi (dequeue).

b) Khi cài đặt hàng đợi bằng mảng một chiều, cần có thông tin nào để thực hiện phép toán thêm vào và lấy ra?

Khi cài đặt hàng đợi bằng mảng một chiều, cần phải quản lý hai chỉ số chính:

1.  Front (đầu hàng đợi): Chỉ số này giữ vị trí của phần tử đầu tiên trong hàng đợi. Khi thực hiện phép toán lấy ra (dequeue), phần tử tại vị trí này sẽ được lấy ra và chỉ số front sẽ được cập nhật để trỏ đến phần tử tiếp theo.

2. Rear (cuối hàng đợi): Chỉ số này giữ vị trí của phần tử cuối cùng trong hàng đợi. Khi thực hiện phép toán thêm vào (enqueue), phần tử mới sẽ được thêm vào vị trí kế tiếp của chỉ số rear, và chỉ số rear sẽ được cập nhật để trỏ đến vị trí cuối mới của hàng đợi.

Ngoài ra, còn cần thêm thông tin về kích thước của mảng để quản lý việc tràn (overflow) khi hàng đợi đầy và để tránh lấy ra từ hàng đợi rỗng (underflow). Một số cách quản lý thông tin bổ sung có thể bao gồm:

- Size (kích thước hiện tại): Số lượng phần tử hiện có trong hàng đợi.

- Capacity (dung lượng tối đa): Dung lượng tối đa của mảng được sử dụng để cài đặt hàng đợi.

1. Có thể biểu diễn hàng đợi bằng mảng một chiều được không?

Có, hoàn toàn có thể biểu diễn hàng đợi (queue) bằng mảng một chiều (array). Trong Python, danh sách (list) có thể được sử dụng để cài đặt hàng đợi. Tuy nhiên, cần quản lý các chỉ số cho phép thêm phần tử vào cuối hàng đợi (enqueue) và lấy phần tử ra từ đầu hàng đợi (dequeue) một cách hiệu quả.

2. Cần có các biến nào để thực hiện các phép toán thêm vào và lấy ra?

Để thực hiện các phép toán thêm vào và lấy ra trong hàng đợi biểu diễn bằng mảng một chiều, cần có các biến sau:

1. Front (đầu hàng đợi):

- Đây là biến giữ vị trí của phần tử đầu tiên trong hàng đợi.

- Khi thực hiện phép toán lấy ra (dequeue), phần tử tại vị trí front sẽ được lấy ra, và chỉ số front sẽ được cập nhật để trỏ đến phần tử tiếp theo.

2. Rear (cuối hàng đợi):

- Đây là biến giữ vị trí của phần tử cuối cùng trong hàng đợi.

- Khi thực hiện phép toán thêm vào (enqueue), phần tử mới sẽ được thêm vào vị trí kế tiếp của rear, và chỉ số rear sẽ được cập nhật để trỏ đến vị trí cuối mới của hàng đợi.

3. Size (kích thước hiện tại):

- Đây là biến theo dõi số lượng phần tử hiện có trong hàng đợi.

- Biến này giúp kiểm tra hàng đợi có rỗng hay đầy để tránh các lỗi underflow (lấy từ hàng đợi rỗng) và overflow (thêm vào hàng đợi đầy).

4. Capacity (dung lượng tối đa):

- Đây là biến xác định dung lượng tối đa của mảng được sử dụng để cài đặt hàng đợi.

- Giúp kiểm tra và ngăn chặn tình trạng tràn (overflow) khi hàng đợi đầy.

Khi hàng đợi (queue) được cài đặt bằng danh sách (list) trong Python, có thể tính số phần tử của hàng đợi này bằng cách sử dụng thuộc tính size mà ta đã định nghĩa trong lớp Queue. Thuộc tính size sẽ được cập nhật mỗi khi thực hiện các phép toán thêm vào (enqueue) hoặc lấy ra (dequeue).

- Gợi ý cách tính số phần tử của hàng đợi bằng cách truy cập thuộc tính size:

class Queue:

    def __init__(self, capacity):

        self.capacity = capacity

        self.queue = [None] * capacity

        self.front = 0

        self.rear = -1

        self.size = 0

    def is_full(self):

        return self.size == self.capacity

    def is_empty(self):

        return self.size == 0

    def enqueue(self, item):

        if self.is_full():

            print("Queue is full")

            return

        self.rear = (self.rear + 1) % self.capacity

        self.queue[self.rear] = item

        self.size += 1

        print(f"Enqueued {item}")

    def dequeue(self):

        if self.is_empty():

            print("Queue is empty")

            return None

        item = self.queue[self.front]

        self.front = (self.front + 1) % self.capacity

        self.size -= 1

        print(f"Dequeued {item}")

        return item

    def get_front(self):

        if self.is_empty():

            print("Queue is empty")

            return None

        return self.queue[self.front]

    def get_rear(self):

        if self.is_empty():

            print("Queue is empty")

            return None

        return self.queue[self.rear]

    def get_size(self):

        return self.size

# Test the Queue

q = Queue(5)

q.enqueue(10)

q.enqueue(20)

q.enqueue(30)

print(f"Number of elements in the queue: {q.get_size()}")  # Should print 3

q.dequeue()

print(f"Number of elements in the queue: {q.get_size()}")  # Should print 2

* Trong chương trình trên ta có:

 - Hàm enqueue thêm phần tử vào cuối hàng đợi và tăng size lên 1.

 - Hàm dequeue lấy phần tử ra từ đầu hàng đợi và giảm size xuống 1.

 - Hàm get_size trả về giá trị của thuộc tính size, tức là số phần tử hiện có trong hàng đợi.

Do đó, số phần tử trong hàng đợi luôn được theo dõi và cập nhật thông qua biến size, và ta có thể biết được số phần tử hiện có trong hàng đợi bất cứ lúc nào bằng cách gọi phương thức get_size.

Để xác định giá trị của phần tử ở đầu (front) và đuôi (rear) sau khi thực hiện tuần tự các phép toán trên hàng đợi (queue), ta sẽ theo dõi từng phép toán một cách chi tiết. Giả sử hàng đợi ban đầu có dung lượng đủ lớn để chứa tất cả các phần tử được thêm vào mà không cần phải xử lý trường hợp tràn (overflow).

Ban đầu, hàng đợi là rỗng:

front = 0

rear = -1

size = 0

Các bước thực hiện tuần tự các phép toán như sau:

1. enqueue(Q, 2)

Thêm 2 vào cuối hàng đợi.

rear tăng lên 0.

size tăng lên 1.

queue = [2]

front = 0

rear = 0

2.  enqueue(Q, 19)

Thêm 19 vào cuối hàng đợi.

rear tăng lên 1.

size tăng lên 2.

queue = [2, 19]

front = 0

rear = 1

3.  dequeue(Q)

Lấy 2 ra từ đầu hàng đợi.

front tăng lên 1.

size giảm xuống 1.

queue = [2, 19] (phần tử tại front không còn được sử dụng)

front = 1

rear = 1

4.  enqueue(Q, 6)

Thêm 6 vào cuối hàng đợi.

rear tăng lên 2.

size tăng lên 2.

queue = [2, 19, 6]

front = 1

rear = 2

5.  dequeue(Q)

Lấy 19 ra từ đầu hàng đợi.

front tăng lên 2.

size giảm xuống 1.

queue = [2, 19, 6] (phần tử tại front không còn được sử dụng)

front = 2

rear = 2

6. enqueue(Q, 9)

Thêm 9 vào cuối hàng đợi.

rear tăng lên 3.

size tăng lên 2.

queue = [2, 19, 6, 9]

front = 2

rear = 3

7. enqueue(Q, 1)

Thêm 1 vào cuối hàng đợi.

rear tăng lên 4.

size tăng lên 3.

queue = [2, 19, 6, 9, 1]

front = 2

rear = 4

- Sau khi thực hiện tuần tự các phép toán, trạng thái của hàng đợi sẽ như sau:

queue = [2, 19, 6, 9, 1]

front = 2 (phần tử ở đầu hàng đợi là 6)

rear = 4 (phần tử ở cuối hàng đợi là 1)

Hàng đợi được cài đặt với các phép toán chính như thêm phần tử vào cuối hàng đợi (enqueue), lấy phần tử ra từ đầu hàng đợi (dequeue), kiểm tra xem hàng đợi có rỗng không (is_empty), và trả về số phần tử hiện tại trong hàng đợi (size).

Khi hàng đợi (queue) và ngăn xếp (stack) được cài đặt bằng danh sách (list) trong Python, cách quản lý chỉ số của các phần tử có một số điểm khác nhau. Dưới đây là sự phân tích chi tiết về chỉ số của các phần tử tại đầu (front) và đuôi (rear) của hàng đợi so với chỉ số của các phần tử tại đáy (bottom) và đỉnh (top) của ngăn xếp.

Hàng đợi (Queue)

Trong hàng đợi (FIFO - First In, First Out):

- Front (đầu hàng đợi): Chỉ số của phần tử đầu tiên (phần tử được thêm vào đầu tiên và sẽ được lấy ra đầu tiên).

- Rear (đuôi hàng đợi): Chỉ số của phần tử cuối cùng (phần tử được thêm vào gần đây nhất).

Ngăn xếp (Stack)

Trong ngăn xếp (LIFO - Last In, First Out):

- Bottom (đáy ngăn xếp): Chỉ số của phần tử đầu tiên được thêm vào (phần tử nằm ở đáy ngăn xếp, ít được truy cập nhất).

- Top (đỉnh ngăn xếp): Chỉ số của phần tử cuối cùng được thêm vào (phần tử nSo sánh các chỉ số

- Hàng đợi:

+ Front: Chỉ số của phần tử đầu tiên được thêm vào và sẽ được lấy ra đầu tiên. Trong ví dụ, Front = 0.

+ Rear: Chỉ số của phần tử cuối cùng được thêm vào. Trong ví dụ, rear = 4

- Ngăn xếp:

+ Bottom: Chỉ số của phần tử đầu tiên được thêm vào, nằm ở đáy ngăn xếp. Trong ví dụ, Bottom = 0 .

+ Top: Chỉ số của phần tử cuối cùng được thêm vào, nằm ở đỉnh ngăn xếp. Trong ví dụ, Top = 4

Cả hàng đợi và ngăn xếp đều sử dụng danh sách Python, và cả hai đều sử dụng chỉ số 0 cho phần tử đầu tiên được thêm vào. Sự khác biệt chính nằm ở cách mà các phần tử được thêm vào và lấy ra:

- Trong hàng đợi, phần tử ở Front được lấy ra trước và phần tử ở Rear được thêm vào cuối.

- Trong ngăn xếp, phần tử ở Top được lấy ra trước và phần tử ở Bottom nằm ở đáy ngăn xếp.

- Nằm ở đỉnh ngăn xếp, phần tử sẽ được lấy ra đầu tiên).