Bài 1. Mô hình dữ liệu ngăn xếp và hàng đợi
Chuyên đề 1. TÌM HIỂU MỘT VÀI KIỂU DỮ LIỆU TUYẾN TÍNH
MÔ HÌNH DỮ LIỆU NGĂN XẾP VÀ HÀNG ĐỢI
Sau bài học này em sẽ:
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:
b) Ai sẽ là người được rút tiền trước tại cây ATM? Người cuối cùng sẽ được rút tiền khi nào?
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.
Trong các ví dụ thực tế ở phần khởi động, ví dụ ở Hình 1.1a thuộc mô hình dữ liệ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 ở một đầu, theo cơ chế hoạt động LIFO.
Một ví dụ khác về ngăn xếp là 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à ngăn xếp. Mỗi khi thực hiện một thao tác, 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 trạng thái mới.
Mô hình dữ liệu ngăn xếp được mô tả như sau:
Sau đây là các thao tác cơ bản trên dữ liệu ngăn xếp. Có thể thiết lập các lệnh thực hiện những thao tác này đều có độ phức tạp thời gian O(1), tức là hằng số, không phụ thuộc vào độ dài của ngăn xếp.
| Số thứ tự | Thao tác | HàmILệnh |
| Tạo một xếp rỗng. ngăn | 5 Stack ( ) | |
| 2 | Đưa phần tử x vào đỉnh xếp $. ngăn | push(S,x) |
| 3 | Lấy ra một phần tử từ đỉnh của ngăn xếp $ và trả về phần tử này. | pop(S) |
| Kiểm tra xếp rỗng. Trả về True nếu $ ngược lại trả về False. rỗng, ngăn | isEmptyStack(S) | |
| 5 | Trả về phẩn tử tại vị trí đỉnh của ngăn xếp $, S không thay đổi. | top(s) |
Ví dụ 1. Để tạo một ngăn xếp rỗng, cần thực hiện các lệnh sau:
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() và hàm pop().
push(S,1); push(S,5); pop(S); push(S,10).
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.
Hàng đợi (queue) 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.
Một ví dụ của mô hình hàng đợi là hàng đợi của máy in. Máy in 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ào vào hàng trong trước.
Mô hình dữ liệu hàng đợi (queue) có thể được mô tả như sau:
Sau đây là các thao tác cơ bản trên dữ liệu hàng đợi. Có thể thiết lập các lệnh thực hiện những thao tác này đều có độ phức tạp thời gian O(1), tức là hằng số, không phụ thuộc vào độ dài của hàng đợi.
Bảng 1.2. Các thao tác cơ bản làm việc trên dữ liệu hàng đợi
| STT | Thao tác | HàmILệnh |
| Tạo một đợi rỗng. hàng | Q Queue( ) | |
| 2 | Đưa phần tử x vào cuối của hàng đợi Q. | enqueue(Q,x) |
| 3 | 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 | dequeue(Q) |
| Kiểm tra hàng đợi Hàm trả về True nếu Q ngược lại trả về False. rỗng. rỗng , | isEmptyQueue(Q) | |
| 5 | Trả về phần tử đầu của hàng đợi Q và Q không thay đổi. | front(Q) |
Ví dụ 1. Muốn tạo một hàng đợi rỗng, cần thực hiện lệnh: Q = Queue()
Sau khi hàng đợi đã có và chúng ta biết Q không rỗng. Muốn lấy ra phần tử ở đầu hàng đợi và chuyển xuống cuối Q, chúng ta thực hiện các lệnh sau:
X = dequeue(Q) enqueue(Q,x)Hàng đợi có các hàm cơ bản: hàm enqueue() để đưa dữ liệu vào đuôi hàng đợi và hàm dequeue() để lấy dữ liệu ra ở đầu hàng đợi. Hàng đợi hoạt động theo cơ chế "vào trước, ra trước".
Q = Queue(); enqueue(Q,2); enqueue(Q,10); dequeue(Q); enqueue(Q,1); dequeue(Q)
LUYỆN TẬP