KHỞI ĐỘNG

Em hãy quan sát các hình ảnh về đồ vật và hiện tượng trong thực tế trong Hình 1.1 và cho biết:

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

b) Ai 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 nào?

Giải chi tiết:

a) Đĩa ở trên cùng là đĩa đượ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 xếp đầu hàng 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 được rút tiền khi tất cả những người đứng trên đã rút tiền xong.

1. Mô hình dữ liệu ngăn xếp

Hoạt động 1: Tìm hiểu mô hình dữ liệu ngăn xếp

Đọc, trao đổi và thảo luận để hiểu về mô hình dữ liệu ngăn xếp và cơ chế hoạt động “vào sau, ra trước” (LIFO-Last in, First Out) của mô hình dữ liệu này.

Giải chi tiết:

Mô hình dữ liệu ngăn xếp và cơ chế hoạt động “vào sau, ra trước” (LIFO-Last in, First Out) của mô hình dữ liệu: Có thể hiểu ngăn xếp là đối tượng dữ liệu, trong đó việc đưa dữ liệu vào và lấy dữ liệu ra ở cùng 1 đầu, theo cơ chế hoạt động LIFO. Thao tác đưa dữ liệu vào là push và lấy dữ liệu ra gọi là pop. Quy ước đầu dùng để đưa dữ liệu vào và lấy dữ liệu ra là đỉnh (top) của ngăn xếp. Đầu ngược lại là đáy(bottom) của ngăn xếp.

Câu hỏi 1: Muốn lấy ra phần tử nằm ở đáy của ngăn xếp thì phải làm như thế nào?

Giải chi tiết:

Muốn lấy được phần tử nằm ở đáy của ngăn xếp thì phải lấy hết các phần tử ở trên phần tử ở đáy đó ra trước, sau đó mới có thể lấy phần tử ở đáy.

Câu hỏi 2: Cho S là một ngăn xếp rỗng. Em hãy cho biết, khi thực hiện các lệnh sau thì S sẽ chứa những phần tử nào:

push(S,1); push(S,5); pop(S); push(S,10).

Giải chi tiết:

S sẽ chứa những phần tử sau: 1, 10

Với Top là 10 và Bottom là 1

2. Mô hình dữ liệu hàng đợi

Hoạt động 2: Tìm hiểu mô hình dữ liệu hàng đợi

Đọc, trao đổi và thảo luận để hiểu về mô hình dữ liệu hàng đợi và cơ chế hoạt động “vào trước, ra trước” (FIFO-First in, First out) của mô hình dữ liệu này.

Giải chi tiết:

Mô hình dữ liệu hàng đợi và cơ chế hoạt động “vào trước, ra trước” (FIFO-First in, First out) của mô hình dữ liệu: là đối tượng dữ liệu trong đó việc đưa dữ liệu vào tại một đầu và lấy dữ liệu ra ở đầu khác, theo cơ chế hoạt động FIFO. Hàng đợi có các thao tác đưa phần tử đưa phần tử vào ở một đầu và lấy phần tử ra tại một đầu khác của hàng đợi. Thao tác đưa dữ liệu vào là enqueue và lấy dữ liệu ra là dequeue. Quy ước đầu để đưa dữ liệu vào là đuôi (back, rear, tail) của hàng đợi. Đầu ngược lại dùng để lấy dữ liệu ra là đầu (font, head) của hàng đợi.

Câu hỏi 1: Hãy chỉ ra những điểm giống và khác nhau giữa ngăn xếp và hàng đợi.

Giải chi tiết:

*Giống nhau:

- Đều là một dãy tuyến tính các phần tử dữ liệu.

- Đều có thể thêm và xóa phần tử.

- Đều có thể được triển khai bằng mảng hoặc danh sách liên kết.

*Khác nhau:

- Nguyên lý hoạt động: Ngăn xếp hoạt động theo nguyên lý LIFO, Hàng đợi hoạt động theo nguyên lý FIFO.

- Thao tác thêm và lấy phần tử: Ngăn xếp thêm vào đỉnh ngăn xếp và lấy cũng xóa phần tử ở đỉnh; Hàng đợi thêm phần tử vào cuối hàng và lấy phần tử ở đầu hàng.

- Ứng dụng thực tế.

Câu hỏi 2: Sau khi thực hiện các lệnh sau, hỏi trong hàng đợi Q có những giá trị nào?

Q = Queue()

enqueue(Q,2); enqueue(Q,10); dequeue(Q); enqueue(Q,1); dequeue(Q).

Giải chi tiết:

Q sẽ chứa những phần tử sau: 1

LUYỆN TẬP

Câu hỏi 1: Cho trước một dãy số, nếu đưa các số này lần lượt từ trái qua phải vào một ngăn xếp, sau đó lại lấy các số này ra từ ngăn xếp và xếp theo thứ tự lấy ra cũng từ trái qua phải, thì sẽ thu được dãy số mới như thế nào?

Giải chi tiết:

Ta sẽ thu được dãy số mới ngược với dãy số ban đầu.

Ví dụ: Cho dãy số 1, 2, 3, 4, 5 sau các thao tác như đề bài ta sẽ thu được dãy số 5, 4, 3, 2, 1

Câu hỏi 2: Giả sử cho một dãy các số, ví dụ 2, 5, 1, 0, 10, các số này lần lượt được kiểm tra, nếu là số chẵn sẽ được đưa vào hàng đợi Q, nếu là số lẻ thì đưa vào ngăn xếp S. Sau đó lần lượt lấy tất cả các số từ S và in ra màn hình. Hỏi các số được in ra màn hình lần lượt là các số nào?

Giải chi tiết:

Các số được in ra màn hình lần lượt là: 1 , 5

VẬN DỤNG

Câu hỏi 1: Tìm thêm các ví dụ thực tế của ngăn xếp và hàng đợi, mô tả hoạt động của các ví dụ này.

Giải chi tiết:

Ví dụ thực tế của ngăn xếp: Xếp lần lượt các quyển sách vào thùng, quyển vào đầu tiên sẽ nằm ở dưới dùng, quyển vào cuối cùng sẽ nằm ở trên cùng. Khi lấy sách phải lấy các quyển ở trên (hay là vào sau) ra trước thì ta mới có thể lấy các quyển dưới (hay là vào trước) ra được.

Ví dụ thực tế của hàng đợi: Xếp hàng lần lượt để soát vé vào cổng của một công viên. Người đến trước sẽ được đứng đầu hàng người đến sau sẽ đứng đằng sau những người đến trước. Ai đến trước sẽ được soát vé vào cổng trước, ai đến sau thì phải chờ những người đến trước soát vé xong thì mới đến lượt để soát vé vào cổng.

Câu hỏi 2: Giả sử ngăn xếp S chứa các phần tử theo thứ tự từ đỉnh xuống là 2, 1, 3. Được phép sử dụng một hàng đợi rỗng Q, em hãy xếp các phần tử của ngăn xếp S theo thứ tự 3, 2, 1 (từ đỉnh xuống đáy).

Giải chi tiết:

Các bước thực hiện như sau:

pop(S); pop(S); enqueue(Q,2); enqueue(Q,1); dequeue(Q); push(S,2); dequeue(Q); push(S,1); pop(S); pop(S); pop(S); enqueue(Q,1); enqueue(Q,2); enqueue(Q,3); push(S,1); push(S,2); push(S,3).