Giải SGK Chuyên đề Tin học 12 Bài 4. Kiểu dữ liệu hàng đợi

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)