Ngăn xếp và Hàng đợi là hai trong số những cấu trúc dữ liệu cực kỳ quan trọng, được sử dụng thường xuyên trong thiết kế thuật toán. Chúng không chỉ quan trọng trong máy tính mà còn trong cuộc sống hàng ngày của chúng ta. Trong bài viết này, chúng ta sẽ cùng tìm hiểu về hoạt động của ngăn xếp và hàng đợi, cũng như cách cài đặt chúng một cách đơn giản.
Ngăn xếp (Stack)
Ngăn xếp là một kiểu danh sách mà việc bổ sung một phần tử và xóa một phần tử được thực hiện ở cuối danh sách.
Imagine a stack as a stack of plates. When you want to add a plate, you place it on top of the stack (at the end), and when you want to take a plate, you take it from the top (from the end).
Phần tử ở đỉnh ngăn xếp (cuối danh sách) được gọi là phần tử top của ngăn xếp. Nguyên tắc thêm - xoá phần tử như trên được gọi là "vào sau ra trước", do đó ngăn xếp còn có tên gọi khác là danh sách kiểu LIFO (Last In First Out). Ngăn xếp cung cấp một số thao tác cơ bản:
init: Khởi tạo ngăn xếp rỗng.is_empty: Kiểm tra xem ngăn xếp có rỗng không.get_top: Trả về phần tử ở đỉnh ngăn xếp.push: Thêm một phần tử vào ngăn xếp.pop: Lấy ra phần tử ở đỉnh ngăn xếp.
Ngăn xếp có thể được biểu diễn bằng mảng hoặc danh sách liên kết. Trong các ngôn ngữ hiện đại như C++ và Python, đã có sẵn ngăn xếp để sử dụng, vì vậy chúng ta không cần phải triển khai thủ công.
Hàng đợi (Queue)
Giống như tên gọi của nó, hàng đợi là một cấu trúc dữ liệu biểu diễn một danh sách các phần tử đứng trong "hàng chờ" được xử lý. Trong cấu trúc dữ liệu này, việc bổ sung một phần tử được thực hiện ở cuối danh sách, còn việc loại bỏ một phần tử được thực hiện ở đầu danh sách.
Có thể tưởng tượng hàng đợi giống như một hàng người xếp hàng chờ mua vé, ai đến trước được mua trước và rời khỏi hàng, còn những người đến sau sẽ bổ sung vào cuối hàng. Vì nguyên tắc "vào trước ra trước" như vậy nên hàng đợi còn được gọi là danh sách kiểu FIFO (First In First Out).
Phần tử ở đầu hàng đợi được gọi là phần tử front, còn phần tử ở cuối hàng đợi được gọi là phần tử rear. Tương tự như ngăn xếp, hàng đợi cung cấp một số thao tác cơ bản:
init: Khởi tạo hàng đợi rỗng.is_empty: Kiểm tra hàng đợi có rỗng hay không.get_front: Trả về giá trị của phần tử ở đầu hàng đợi.push: Đẩy một phần tử vào cuối hàng đợi.pop: Loại bỏ một phần tử ở đầu hàng đợi.
Hàng đợi có thể được biểu diễn bằng mảng hoặc danh sách liên kết. Tuy nhiên, trong các ngôn ngữ hiện đại như C++ và Python, đã không còn ưu tiên sử dụng danh sách liên kết nữa, cũng như đã cài đặt sẵn hàng đợi và ngăn xếp, nên ở đây tôi chỉ phân tích sơ qua cách cài đặt bằng mảng để bạn đọc hiểu về cơ chế của cấu trúc dữ liệu này.
Kết luận
Ngăn xếp và hàng đợi là hai cấu trúc dữ liệu quan trọng giúp chúng ta tổ chức và xử lý các phần tử một cách hợp lý. Chúng được sử dụng rộng rãi trong lập trình để giải quyết các bài toán phức tạp. Việc hiểu và sử dụng đúng cách hai cấu trúc dữ liệu này sẽ giúp bạn trở thành một lập trình viên giỏi.
Hy vọng qua bài viết này, bạn đã hiểu rõ hơn về ngăn xếp và hàng đợi cũng như cách sử dụng chúng trong lập trình.
Ảnh minh họa được lấy từ bài viết gốc, không liên quan đến nội dung phần dịch.