CHÀO MỪNG CÁC EM

ĐẾN VỚI BÀI HỌC!

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?

Ø  Hướng dẫn thực hiện

Cơ chế hoạt động của mô hình dữ liệu ngăn xếp – stack

Cơ chế hoạt động của mô hình dữ liệu hàng đợi – queue

CHUYÊN ĐỀ 1: TÌM HIỂU MỘT VÀI KIỂU DỮ LIỆU TUYẾN TÍNH

BÀI 1: MÔ HÌNH DỮ LIỆU NGĂN XẾP VÀ HÀNG ĐỢI

NỘI DUNG BÀI HỌC

PHẦN 1.

MÔ HÌNH DỮ LIỆU NGĂN XẾP

Em hãy tìm hiểu nội dung mục 1 SGK tr.5 – 6, trả lời các câu hỏi sau:

• Mô hình dữ liệu ngăn xếp hoạt động theo cơ chế gì?
• Em hãy nêu một ví dụ khác về ngăn xếp và mô tả cách hoạt động của ví dụ này.
• Em hãy mô tả mô hình dữ liệu ngăn xếp.

Ø  Cơ chế hoạt động của mô hình dữ liệu ngăn xếp:

“vào sau, ra trước” (LIFO – Last In, First Out).

Ví dụ:

Khi soạn thảo văn bản trong Word:

ü  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.

Mô tả mô hình

• Ngăn xếp là một dãy tuyến tính các phần tử dữ liệu.
• Hãy ghép nối các nội dung cột A với cột B để có kết quả đúng nhất.

ĐỌC – HIỂU VÍ DỤ

Để tạo một ngăn xếp rỗng có thể thực hiện lệnh sau:

S = Stack ()

Nếu muốn đưa lần lượt các số 2, 1, 5 vào ngăn xếp, cần thực hiện các lệnh sau:

push(S,2); push(S,1); push(S,5)

Trả lời câu hỏi Củng cố SGK tr.7:

Câu 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?

pop(S) tất cả các phần tử trong Stack.

Câu 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).

S sẽ chứa phần tử 1, 10.

KẾT LUẬN

• Đặc điểm: Ngăn xếp (stack) thuộc kiểu dữ liệu tuyến tính có các hàm cơ bản: hàm push() để đưa dữ liệu vào và hàm pop() để lấy dữ liệu ra ở cùng một đầu là đỉnh của ngăn xếp. Một số hàm khác là isEmptyStack(), top().
• Cơ chế hoạt động: Ngăn xếp hoạt động theo cơ chế “vào sau, ra trước” (LIFO).

PHẦN 2.MÔ HÌNH DỮ LIỆU HÀNG ĐỢI

Tìm hiểu nội dung mục 2 SGK tr.7 – 8, trả lời các câu hỏi sau:

• Mô hình dữ liệu hàng đợi hoạt động theo cơ chế gì?
• Em hãy nêu một ví dụ của mô hình hàng đợi và mô tả cách hoạt động của nó.
• Em hãy mô tả mô hình dữ liệu hàng đợi.

Ø  Cơ chế hoạt động của mô hình dữ liệu hàng đợi:

“vào trước, ra trước” (FIFO – First In, First Out)

Ví dụ:

Khi thực hiện in tài liệu, máy in sẽ thực hiện lưu trữ thông tin vào một hàng đợi:

ü  Nội dung nào vào trước được in trước.

ü  Nội dung nào vào sau được thực hiện in sau.

Mô tả mô hình

• Hàng đợi là một dãy tuyến tính các phần tử dữ liệu.
• Cơ chế FIFO
• Hãy ghép nối các nội dung cột A với cột B để có kết quả đúng nhất.

Trả lời câu hỏi Củng cố SGK tr.8:

Câu 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.

Trả lời câu hỏi Củng cố SGK tr.8:

Câu 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).