Bài 5. Thực hành kiểu dữ liệu ngăn xếp và hàng đợi

THỰC HÀNH KIỂU DỮ LIỆU NGĂN XẾP VÀ HÀNG ĐỢI

Sau bài học này em sẽ:

Trong bài trước, chúng ta đã sử dụng kiểu dữ liệu hàng đợi và ngăn xếp. Trong nhiều trường hợp ứng dụng trong thực tế chúng ta phải kết hợp cả hai loại dữ liệu này. Em có thể nêu được một ví dụ cần sử dụng cả hai kiểu dữ liệu này không?

Nhiệm vụ: Viết chương trình mô phỏng bếp ăn tập thể

Nhà ăn tập thể của một doanh nghiệp, phục vụ cho người lao động xếp hàng vào chọn suất ăn. Nhà ăn này chỉ có đúng hai loại là cơm gà và cơm bò. Mỗi người khi vào phải xếp hàng và đăng kí món ăn (gà hoặc bò). Thông tin đăng kí suất ăn sẽ được lưu trong tệp input1.inp như hình bên. Trong đó, mỗi hàng tương ứng với lượt đăng kí của một người, số đầu tiên là số định danh (ID của người đăng kí), theo sau là loại suất ăn mà người đó chọn.

input1.inp

1 gà 2 bò 3 gà 4 gà 5 gà 6 bò 7 bò 8 gà

Căn cứ vào tệp đã đăng kí, người quản lí sẽ cho người lao động xếp thành hai hàng, một hàng gồm toàn bộ những người đã chọn cơm gà, hàng còn lại gồm những người chọn cơm bò.

Do nhà bếp không biết trước thông tin đăng kí của người lao động nên sẽ chuẩn bị trước các suất ăn một cách ngẫu nhiên. Các suất ăn được chuẩn bị sẵn và được đưa vào một ngăn xếp, tổng số lượng các suất ăn bằng với tổng số người lao động. Thông tin các suất ăn đã chuẩn bị sẵn được lưu trong tệp input2.inp có dạng như sau:

Quy tắc nhà bếp hoạt động như sau: Mỗi lần người quản lí sẽ lấy một suất ăn trong ngăn xếp và đưa cho người đầu tiên trong hàng đợi tương ứng. Ví dụ, nếu suất ăn được lấy ra là cơm gà thì sẽ đưa cho người đầu tiên trong hàng chọn cơm gà.

Nếu số lượng các loại suất ăn không đúng với số lượng các suất ăn mà mọi người đăng kí, sẽ xảy ra hiện tượng một hàng đợi (ví dụ hàng đợi cơm gà) đã được phục vụ xong nhưng loại đó vẫn còn. Khi đó, người quản lí bắt buộc người đã đăng kí cơm bò phải chuyển sang cơm gà.

Hãy viết chương trình mô phỏng quá trình trên. Nhận đầu vào là hai tệp input1.inp thể hiện việc đăng kí suất ăn của mọi người và tệp input2.inp thể hiện các suất ăn đã được chuẩn bị trước và đưa vào ngăn xếp. Hãy cho biết có người nào buộc phải đổi suất ăn của mình hay không. Nếu có thì hãy in ra số ID của những người đó.

Hướng dẫn

Phân tích: Để xử lí bài toán này, việc đầu tiên là phải tiến hành đọc dữ liệu từ hai file input và đưa chúng vào những kiểu dữ liệu phù hợp. Với dữ liệu người lao động trong hàng đợi, yêu cầu người xếp hàng trước sẽ được phục vụ món ăn trước nên chúng ta sẽ sử dụng kiểu dữ liệu hàng đợi để mô phỏng hai hàng đợi của suất ăn gà và suất ăn bò. Với dữ liệu các suất ăn được đưa vào ngăn xếp, các suất ăn sẽ được lấy lần lượt từ trên xuống dưới nên chúng ta sử dụng dạng dữ liệu ngăn xếp để lưu trữ loại dữ liệu này.

Nếu suất ăn là gà, chúng ta kiểm tra nếu vẫn còn người trong hàng đợi suất ăn gà, chúng ta phát suất ăn cho người đầu tiên trong hàng đó (dequeue) và tiếp tục. Nếu đã hết người trong hàng đợi suất ăn gà, chúng ta bắt buộc người đầu tiên trong hàng suất ăn bò đổi sang suất ăn gà, đưa ID của người này vào danh sách những người buộc phải đổi món ăn và tiếp tục. Quy trình tương tự được thực hiện nếu suất ăn lấy ra từ ngăn xếp là suất ăn bò.

Chương trình thực hiện bài toán này có thể được thực hiện như sau:

bepan.py

from Queue import *
from Stack import *
def bepan(dangkiga, dangkibo, suatan):
doimon = [] #list chứa ID những người phải đổi món
while not isEmptyStack(suatan):
tmp = pop(suatan)
if tmp == 'bò': # nếu suất ăn lấy ra là bò
if not isEmptyQueue(dangkibo): #còn người đăng kí suất ăn bò
dequeue(dangkibo)
else:
ID_doi = dequeue(dangkiga)
doimon.append(ID_doi)
elif tmp == 'gà': # nếu suất ăn lấy ra là gà
if not isEmptyQueue(dangkiga): #còn người đăng kí suất ăn gà
dequeue(dangkiga)
else:
ID_doi = dequeue(dangkibo)
doimon.append(ID_doi)
return doimon
dangkiga = Queue()
dangkibo = Queue()
suatan = Stack()
file1 = open("input1.inp", encoding="utf8")
for line in file1.readlines(): #đọc thông tin đăng kí và đưa vào 2 queue
id, dangki = line.split()
if dangki == 'gà':
enqueue(dangkiga, id)
elif dangki == 'bò':
enqueue(dangkibo, id)
file1.close()
file2 = open("input2.inp", encoding="utf8")
data = file2.read()
for item in data.split(' '): # đọc thông tin suất ăn
push(suatan, item)
file2.close()
doimon = bepan(dangkiga, dangkibo, suatan)
if len(doimon) == 0:
print("Không có người nào phải đổi món ăn")
else:
print("Danh sách những người phải đổi món là:", doimon)

LUYỆN TẬP

VẬN DỤNG

Bài toán nhà bếp được thay đổi như sau: Yêu cầu người lao động xếp thành một hàng để nhận đồ ăn, trong đó những người đăng kí suất cơm gà và những người đăng kí suất cơm bò sẽ đứng lẫn với nhau. Các suất ăn vẫn được nhà bếp thực hiện và đưa vào một ngăn xếp để phục vụ người lao động.

Quy tắc chọn suất ăn như sau: Mỗi người đến lượt sẽ nhận suất ăn được đưa ra từ ngăn xếp, nếu suất ăn đó đúng với suất ăn đã đăng kí thì người này sẽ được nhận suất ăn và đưa ra khỏi hàng đợi. Ngược lại nếu suất ăn không đúng với đăng kí thì người này sẽ ra khỏi hàng đợi và xếp lại vào cuối hàng và tiếp tục đợi. Quá trình chọn suất ăn như trên sẽ dừng lại nếu tất cả số người xếp hàng đều nhận được suất ăn đúng của mình hoặc tất cả mọi người trong hàng đợi đều không thể nhận được suất ăn như đã đăng kí.

Em hãy viết chương trình đọc hai tệp dữ liệu chứa thông tin về các suất ăn của người lao động và tính số người không nhận được suất ăn của mình.

Dữ liệu đầu vào gồm hai tệp, tệp input1.inp chứa thông tin về các suất ăn của người lao động trong hàng đợi, tệp input2.inp chứa thông tin về các suất ăn mà nhà ăn đã chuẩn bị và đưa vào trong ngăn xếp. Ví dụ dữ liệu đầu vào và đầu ra như sau:

Dữ liệu đầu ra là một số nguyên cho trước chỉ số lượng người xếp hàng không thể chọn được suất ăn của mình. Trong ví dụ trên kết quả đưa ra là 2.