Hàng đợi (Queue) - Ngăn xếp (stack)
Bách khoa toàn thư mở Wikipedia
Ngăn xếp - Stack là một vật chứa (container) các đối tượng làm việc theo cơ chế LIFO (Last In First Out) nghĩa là việc thêm một đối tượng vào stack hoặc lấy một đối tượng ra khỏi stack được thực hiện theo cơ chế "Vào sau ra trước".
Hàng đợi - Queue là một vật chứa (container) các đối tượng làm việc theo cơ chế FIFO (First In First Out) nghĩa là việc thêm một đối tượng vào hàng đợi hoặc lấy một đối tượng ra khỏi hàng đợi được thực hiện theo cơ chế "Vào trước ra trước".
Mục lục |
[sửa] Ngăn xếp - Stack
Trong stack, các đối tượng có thể được thêm vào stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi stack.
Thao tác thêm 1 đối tượng vào stack thường được gọi là "Push". Thao tác lấy 1 đối tượng ra khỏi stack gọi là "Pop".
Trong tin học, cấu trúc dữ liệu stack có nhiều ứng dụng: khử đệ qui, tổ chức lưu vết các quá trình tìm kiếm theo chiều sâu và quay lui, vét cạn, ứng dụng trong các bài toán tính toán biểu thức.
Ta có thể định nghĩa cấu trúc dữ liệu stack như sau: stack là một cấu trúc dữ liệu trừu tượng (ADT) tuyến tính hỗ trợ 2 thao tác chính:
• Push(o): Thêm đối tượng o vào đầu stack
• Pop(): Lấy đối tượng ở đầu stack ra khỏi stack và trả về giá trị của nó. Nếu stack rỗng thì lỗi sẽ xảy ra.
Ngoài ra, stack cũng hỗ trợ một số thao tác khác:
• isEmpty(): Kiểm tra xem stack có rỗng không.
• Top(): Trả về giá trị của phần tử nằm ở đầu stack mà không hủy nó khỏi stack. Nếu stack rỗng thì lỗi sẽ xảy ra.
Các thao tác thêm, trích và huỷ một phần tử chỉ được thực hiện ở cùng một phía của Stack do đó hoạt động của Stack được thực hiện theo nguyên tắc LIFO (Last In First Out - vào sau ra trước). Ðể biểu diễn Stack, ta có thể dùng mảng 1 chiều hoặc dùng danh sách liên kết.
[sửa] Biểu diễn stack dùng mảng
[sửa] Biểu diễn stack dùng danh sách liên kết
[sửa] Ứng dụng của Stack
Cấu trúc Stack thích hợp lưu trữ các loại dữ liệu mà trình tự truy xuất ngược với trình tự lưu trữ, do vậy một số ứng dụng sau thường cần đến stack :
• Trong trình biên dịch (thông dịch), khi thực hiện các thủ tục, Stack được sử dụng để lưu môi trường của các thủ tục.
• Trong một số bài toán của lý thuyết đồ thị (như tìm đường đi), Stack cũng thường được sử dụng để lưu dữ liệu khi giải các bài toán này.
Ngoài ra, Stack cũng còn được sử dụng trong trường hợp khử đệ qui đuôi.
[sửa] Hàng đợi - Queue
Trong hàng đợi, các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi.
Thao tác thêm một đối tượng vào hàng đợi và lấy một đối tượng ra khỏi hàng đợi lần lượt được gọi là "enqueue" và "dequeue". Việc thêm một đối tượng vào hàng đợi luôn diễn ra ở cuối hàng đợi và một phần tử luôn được lấy ra từ đầu hàng đợi.
Trong tin học, cấu trúc dữ liệu hàng đợi có nhiều ứng dụng: khử đệ qui, tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui, vét cạn, tổ chức quản lý và phân phối tiến trình trong các hệ điều hành, tổ chức bộ đệm bàn phím.
Ta có thể định nghĩa cấu trúc dữ liệu hàng đợi như sau: hàng đợi là một cấu trúc dữ liệu trừu tượng (ADT) tuyến tính. Tương tự như stack, hàng đợi hỗ trợ các thao tác:
• EnQueue(o): Thêm đối tượng o vào cuối hàng đợi.
• DeQueue(): Lấy đối tượng ở đầu queue ra khỏi hàng đợi và trả về giá trị của nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.
• IsEmpty(): Kiểm tra xem hàng đợi có rỗng không.
• Front(): Trả về giá trị của phần tử nằm ở đầu hàng đợi mà không hủy nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.
Các thao tác thêm, trích và huỷ một phần tử phải được thực hiện ở 2 phía khác nhau của hàng đợi do đó hoạt động của hàng đợi được thực hiện theo nguyên tắc FIFO (First In First Out - vào trước ra trước). Cũng như stack, ta có thể dùng cấu trúc mảng 1 chiều hoặc cấu trúc danh sách liên kết để biểu diễn cấu trúc hàng đợi.
[sửa] Biểu diễn hàng đợi dùng mảng
[sửa] Biểu diễn hàng đợi dùng danh sách liên kết
[sửa] Ứng dụng của hàng đợi
Hàng đợi có thể được sử dụng trong một số bài toán:
• Bài toán sản xuất và tiêu thụ (ứng dụng trong các hệ điều hành song song).
• Bộ đệm (ví dụ: Nhấn phím -> Bộ đệm -> CPU xử lý).
• Xử lý các lệnh trong máy tính (ứng dụng trong HÐH, trình biên dịch), hàng đợi các tiến trình chờ được xử lý.