Phối hợp hai hàng đợi với một ngăn xếp

Dữ liệu dưới đây là ví dụ giả định. Mỗi người có mã riêng và đăng kí một trong hai loại suất `ga`, `bo`. Người chọn cùng loại xếp vào cùng hàng theo thứ tự đăng kí. Suất ăn được đặt lên ngăn xếp theo thứ tự chuẩn bị; suất đặt cuối nằm trên cùng và được lấy trước. Mỗi lượt lấy một suất ở đỉnh. Nếu hàng đăng kí loại đó còn người, phục vụ người đầu hàng ấy. Nếu hàng ấy hết, phục vụ người đầu hàng còn lại và ghi mã người phải đổi loại. Giả định chỉ có hai nhãn ga/bo, tổng số suất bằng tổng số người, mỗi mã xuất hiện một lần.

Dùng các hàm ngăn xếp và hàng đợi đã học. Hàm sao chép danh sách suất để không làm mất dữ liệu đầu vào; trả về thứ tự phục vụ và danh sách mã đổi suất. ```python def serve_two_lines(orders, meals): ga, bo = Queue(), Queue() for code, choice in orders: if choice == 'ga': enqueue(ga, code) else: enqueue(bo, code) S = meals.copy() changed, served = [], [] while not isEmptyStack(S): meal = pop(S) preferred = ga if meal == 'ga' else bo other = bo if meal == 'ga' else ga if not isEmptyQueue(preferred): code = dequeue(preferred) else: code = dequeue(other) changed.append(code) served.append(code) return served, changed ```

Nếu mọi người bắt đầu chờ ở giây 0, mỗi lượt phục vụ mất đúng một giây và không có khoảng nghỉ, thời điểm hoàn tất sáu lượt là 1,2,3,4,5,6 giây. Trung bình từ lúc bắt đầu chờ đến khi nhận xong là (1+2+3+4+5+6)/6 = **3,5 giây**. Nếu chỉ tính thời gian chờ trước khi bắt đầu được phục vụ, các giá trị là 0,1,2,3,4,5 giây, trung bình 2,5 giây. Cần xác định cách tính trước khi diễn giải kết quả; hai đại lượng không cùng ý nghĩa.