Stack, Queue và Priority Queue trong Java (phần 1)

Stack, Queue và Priority Queue trong Java (phần 1)

Phần 1: Stack

Stack là gì?

Stack là một cách thức lưu trữ và lấy dữ liệu theo kiểu xếp chồng. Để dễ hình dung, giả sử bạn có 1 thùng dựng sách có chiều dài và chiều rộng vừa với cuốn sách, và chiều cao vừa đủ.

Bạn có 5 cuốn sách xếp theo thứ tự từ trái sang lần lượt là 1, 2, 3, 4, 5

Bây giờ, bạn đi lần lượt từ trái sang, mỗi lần đi đặt 1 cuốn sách vào thùng. Sau khi đi qua 5 cuốn sách, thùng sẽ như sau

Các bạn để ý một số điểm đặc biệt như sau:

1. Khi đưa sách vào, ta chỉ có thể đặt cuốn sách mới lên trên cuốn sách cũ

2. Nếu ta lấy sách ra, ta phải lấy theo thứ tự: Từ cuốn sách đặt cuối cùng (last) lấy ra trước (first) cho đến cuốn sách đặt đầu tiên (first) lấy ra sau (last)

=>Ta còn gọi nó là LIFO (Last In First Out – Vào cuối ra trước)

3. Thứ tự sách tính từ đỉnh (top) của stack tới đáy (bottom) của stack là 5, 4, 3, 2, 1 ngược với thứ tự ban đầu khi xếp từ trái sang 1, 2, 3, 4, 5

=>Đứa chạy đầu tiên sẽ đặt vào vị trí đáy, cho tới đứa chạy cuối cùng sẽ đặt vào vị trí đỉnh

Trong lập trình, người ta sử dụng nó để giải quyết một số bài toán đặc trưng

Trong Java, có hỗ trợ một lớp Stack dùng để thực hiện kiểu lưu trữ và lấy thông tin như thế này

Stack trong Java

Stack trong Java nằm trong java.util, cú pháp khai báo và khởi tạo như sau

Stack<Type> obj = new Stack<Type>();

Cách tương tác với các phần tử như sau:

push(): đưa phần tử vào trong stack, theo kiểu của stack – đưa vào đầu danh sách stack

pop(): đưa phần tử ra ngoài stack, theo kiểu của stack – trả về một giá trị tại vị trí nằm ở đầu danh sách stack, và xóa phần tử đó trong danh sách stack

peek(): xem (trả về) phần tử đầu tiên trong danh sách stack

    *Hàm peek() không xóa phần tử đầu tiên như pop()

Ngoài ba hàm trên, còn một số hàm dùng để tìm kiếm phần tử. Một số quy ước về vị trí ta cần biết như sau

Search position được tính theo khoảng cách của phần tử tính từ vị trí top, với phần tử đầu tiên bắt đầu bằng 1.

Index được tính từ đáy của danh sách, đếm bắt đầu từ 0.

Search position được dùng khi ta gọi hàm search(somethingObject). Cú pháp như sau

 obj.search(somethingObject);

Để đơn giản ta thử ví dụ như sau

Stack<Integer> listBook = new Stack<Integer>();

listBook.push(1);

listBook.push(2);

listBook.push(3);

listBook.push(4);

listBook.push(5);

Như ta thấy, sau khi push các cuốn sách từ 1 tới 5, ta nhận được 1 stack với phần tử tại đỉnh là cuốn sách số 5. Giả sử khi ta muốn tìm cuốn sách số 2 có search position là bao nhiêu, ta dùng hàm sau

listBook.search(new Integer(2));

Lúc đó ta trả về search position có giá trị là 4. Số 4 được xem là khoảng cách từ top đến vị trí cuốn sách số 2.

Tương tự như thế, index được dùng giống như khi mình sử dụng list, chỉ cần chú ý phần tử đầu tiên là đáy và bắt đầu từ 0

Ví dụ: listBook.get(1) -> Kết quả trả về là cuốn sách số 2

Hôm nay chúng ta đã xong bài viết về Stack rồi, đơn giản phải không nào!

Nội dung bài viết thuộc về Lê Công Diễn.

Người viết: Lê Công Diễn

Mang đi nhớ ghi nguồn