Giải SGK Chuyên đề Tin học 12 Bài 1. Mô hình dữ liệu ngăn xếp và hàng đợi

a) Trong chồng đĩa, đĩa trên cùng được xếp vào sau cùng. Đĩa trên cùng cần được lấy ra đầu tiên.

b) Người gần cây rút tiền nhất sẽ là người được rút tiền trước tại cây ATM. Người xếp hàng cuối cùng sẽ được rút tiền khi người trước đó rút được tiền.

Push(s,1): Đưa phần tử 1 vào đỉnh ngăn xếp s.

push(s,5): Đưa phần tử 5 vào đỉnh ngăn xếp s.

pop(s): Lấy ra một phần tử từ đỉnh của ngăn xếp S và trả về phần tử này.

push(s,10): Đưa phần tử 10 vào đỉnh ngăn xếp s.

Giống nhau giữa ngăn xếp và hàng đợi: đều là kiểu dữ liệu tuyến tính, đều phải đưa dữ liệu vào và lấy dữ liệu ra.

Khác nhau:

- Ngăn xếp: hoạt động theo cơ chế “vào sau, ra trước”.

- Hàng đợi: hoạt động theo cơ chế “vào trước, ra trước”.

Q=Queue(): Tạo một hàng đợi rông

Enqueue(Q,2): Đưa phần tử 2 vào vào cuối của hàng đợi Q.

Enqueue(Q,10): Đưa phần tử 10 vào vào cuối của hàng đợi Q.

Dequeue(Q): Lấy ra một phần tử tại đầu của hàng đợi Q và trả về phần tử này.

Enqueue(Q,1): Đưa phần tử 1 vào vào cuối của hàng đợi Q.

Dequeue(Q): Lấy ra một phần tử tại đầu của hàng đợi Q và trả về phần tử này.

- Ví dụ thực tế của ngăn xếp: Chức năng Undo thường được sử dụng khi soạn thảo văn bản. Lệnh Undo giúp người sử dụng huỷ bỏ kết quả của thao tác gần nhất. Mô hình quản lí các dữ liệu Undo chính là các ngăn xếp. Mỗi khi thực hiện một thao tác mới, trạng thái hiện tại của văn bản được đưa vào đỉnh của ngăn xếp Undo. Khi yêu cầu Undo, trạng thái hiện tại được lấy ra từ đỉnh ngăn xếp và khôi phục lại.

- Ví dụ thực tế của hàng đợi: hàng đợi của máy in. Máy in trong văn phòng thường được sử dụng cho nhiều người, trong đó mỗi người có thể đưa ra các lệnh in bất cứ lúc nào. Máy in sẽ lưu trữ các nội dung in vào một hàng đợi, nội dung nò vào trước sẽ in trước, nội dung nào vào sau sẽ in sau.

Sắp xếp các phần tử của ngăn xếp S theo thứ tự 3, 1, 2 (từ đỉnh xuống đáy):

Push(s,2); Push(s,1); Push(s,3);