Ngăn xếp và hàng đợi: lấy phần tử nào trước?

Một dãy dữ liệu, hai quy tắc lấy ra

Thêm lần lượt 3, 7, 2: ngăn xếp lấy 2 ở đỉnh; hàng đợi lấy 3 ở đầu.

Ngăn xếp (stack) tuân theo **vào sau, ra trước — LIFO**. Thêm và lấy đều ở đỉnh; phần tử vừa thêm trở thành đỉnh mới. Chồng sách chỉ được lấy từ trên cùng là một mô hình ngăn xếp. Hàng đợi (queue) tuân theo **vào trước, ra trước — FIFO**. Thêm ở cuối, lấy ở đầu. Những người đến quầy lần lượt và được phục vụ theo thứ tự đến là một mô hình hàng đợi. Sơ đồ dùng cùng thứ tự thêm 3, 7, 2 để chỉ ra sự khác nhau: ngăn xếp lấy 2 trước, hàng đợi lấy 3 trước.

Xem chưa làm mất phần tử

|Công việc|Ngăn xếp|Hàng đợi| |---|---|---| |Khởi tạo rỗng|Stack()|Queue()| |Kiểm tra rỗng|isEmptyStack(S)|isEmptyQueue(Q)| |Thêm phần tử x|push(S,x), ở đỉnh|enqueue(Q,x), ở cuối| |Lấy ra và trả về|pop(S), ở đỉnh|dequeue(Q), ở đầu| |Chỉ xem, giữ nguyên cấu trúc|top(S), xem đỉnh|front(Q), xem đầu| Sau khi thêm 3, 7, 2 vào ngăn xếp, `top(S)` trả về 2 và vẫn còn ba phần tử. `pop(S)` cũng trả về 2 nhưng chỉ còn 3, 7. Nếu là hàng đợi, `dequeue(Q)` trả về 3, còn 7, 2. Ngăn xếp và hàng đợi rỗng không có phần tử để xem hoặc lấy ra. Chương trình phải kiểm tra trường hợp này trước khi truy cập.

Bài luyện

Thêm lần lượt 3, 7, 2 vào ngăn xếp rỗng rồi lấy hết bằng pop. Thứ tự nhận được là gì?

A3, 7, 2.B2, 7, 3.C7, 3, 2.D2, 3, 7.

Bài luyện

Hàng đợi Q chứa [3, 7, 2], đầu ở bên trái. Sau front(Q), Q thế nào?

ACòn [7, 2].BCòn [3, 7].CVẫn [3, 7, 2].DTrở thành [2, 7, 3].

Bài luyện

Mô hình nào phù hợp với hàng đợi FIFO?

ALấy sách ở đỉnh chồng sách.BLấy vật vừa đặt cuối vào một hộp chỉ mở ở đỉnh.CHoàn tác thao tác gần nhất.DPhục vụ theo thứ tự đến, không ưu tiên chen hàng.