Ngăn xếp Stack trong Java | Lập Trình Từ Đầu

1. Ngăn xếp Stack trong Java là gì?

Ngăn xếp hay Stack là một cấu trúc dữ liệu tuyến tính, thường được sử dụng để lưu trữ các dữ liệu theo cơ chế Last-In-First-Out (LIFO) – cơ chế này được hiểu là: “Vào cuối thì được xử lý đầu”.

Cấu trúc dữ liệu ngăn xếp có hai thao tác quan trọng nhất là pushpop. Thao tác push sẽ chèn một phần tử vào trên đỉnh ngăn xếp và thao tác pop sẽ xóa một phần tử khỏi đầu ngăn xếp. Xem hình minh họa dưới đây để hiểu rõ hơn về Stack và thao tác pushpop thường được sử dụng:

Trong ngôn ngữ lập trình Java (chi tiết hơn là trong Java collection) đã cung cấp sẵn cho chúng ta một lớp Stack để làm việc với kiểu ngăn xếp này. Trong đó, lớp Stack này sẽ cung cấp nhiều phương thức để ta tiện lợi hơn khi thao tác với Stack, đó là các phương thức để thực hiện: thêm phần tử vào Stack (push), lấy phần tử (trên đầu) của Stack (pop), tìm kiếm phần tử trong Stack (search)… Để sử dụng được lớp này trong Java, ta cần nhập vào thư viện:  import java.util.Stack;

2. Khai báo Stack trong Java

Trong Java, để khai báo một Stack ta sẽ chỉ cần khởi tạo một lớp Stack với một định nghĩa constructor mặc định cho lớp Stack này. Khi đó, Stack được khởi tạo thành công sẽ mặc định là một ngăn xếp rỗng.

Đoạn code dưới đây, sẽ khởi tạo một Stack trong Java với kiểu dữ liệu của các phần tử được lưu trữ bên trong StackInteger và sau khi khởi tạo thành công sẽ là một ngăn xếp rỗng:

import java.util.Stack;  
public class Main{  
    public static void main(String[] args){  
        //Tao mot stack voi kieu Integer  
        Stack<Integer> stk = new Stack<>();  
        //Kiem tra stack co rong khong
        boolean result = stk.empty();
        //Mac dinh khi khoi tao stack nay se la rong
        System.out.println("Stack la rong khi khoi tao? " + result);  
    }
}

Kết quả:

Stack la rong khi khoi tao? true

Lưu ý: Vì lớp Stack được xây dựng và kế thừa dựa trên lớp Vector, nên chúng ta hoàn toàn có thể sử dụng lại các phương thức có trong lớp Vector. Thế nên, Stack ở ví dụ trên mới có thể thể gọi và sử dụng phương thức empty().

3. Thao tác với Stack trong Java

Như đã đề cập ở phần đầu tiên, khi làm việc với cấu trúc Stack trong Java, chúng ta có thể thực hiện các thao tác như: thêm phần tử vào Stack (push), lấy phần tử (trên đầu) của Stack (pop), tìm kiếm phần tử trong Stack (search) trong đó có 2 thao tác chính khi làm việc với Stack đó là pushpop.

3.1 Thao tác Push với Stack trong Java

Như ta đã biết, khi khai báo khởi tạo một Stack mới sẽ có dung lượng lưu trữ là rỗng. Tuy nhiên, trong một bài toán ta cần lưu trữ các dữ liệu vào trong Stack thì phải làm như thế nào? Đó chính là việc thêm phần tử (push) vào trong Stack đó.

Việc thêm phần tử vào trong Stack được thực hiện bằng cách thêm phần tử mới vào trên đỉnh của Stack và khi xử lý Stack đó thì lại lấy ra phần tử ở trên đỉnh Stack để xử lý. 

Như trong ví dụ dưới đây, Stack được thêm (push) lần lượt các phần tử: 20, 13, 89, 90, 11, 45, 18 vào trên đỉnh ngăn xếp:

Đoạn code dưới đây, thực hiện thêm (push) các phần tử 20, 13, 89, 90, 11, 45, 18 vào trên đỉnh Stack bằng cách sử dụng phương thức push() trong Java như sau:

import java.util.Stack;  
public class Main{  
    public static void main(String[] args){  
        //Tao mot stack voi kieu Integer  
        Stack<Integer> stk = new Stack<>();  
        //Mac dinh khi khoi tao stack nay se la rong
        System.out.println("Stack la rong khi khoi tao? " + stk.empty());
        //Push phan tu: 20, 13, 89, 90, 11, 45, 18 vao dinh Stack
        stk.push(20);  
        stk.push(13);  
        stk.push(89);  
        stk.push(90);
        stk.push(11);  
        stk.push(45);  
        stk.push(18);
        //Kiem tra stack con rong sau khi push hay khong?
        System.out.println("Stack la rong sau khi push? " + stk.empty());
        //Hien thi cac phan tu trong stack
        System.out.println("Phan tu Stack: " + stk);
    }
}

Kết quả:

Stack la rong khi khoi tao? true
Stack la rong sau khi push? false
Phan tu Stack: [20, 13, 89, 90, 11, 45, 18]

Quá trình thực hiện push các phần tử 20, 13, 89, 90, 11, 45, 18 vào Stack trên được minh họa như bên dưới đây:

stack: []
push -> 20
stack: [20]
push -> 13
stack: [20, 13]
push -> 89
stack: [20, 13, 89]
push -> 90
stack: [20, 13, 89, 90]
push -> 11
stack: [20, 13, 89, 90, 11]
push -> 45
stack: [20, 13, 89, 90, 11, 45]
push -> 18
stack: [20, 13, 89, 90, 11, 45, 18]

3.2 Thao tác Pop với Stack trong Java

Thao tác Pop với Stack trong Java thực chất là việc lấy ra phần tử trên đỉnh của Stack đó và đồng thời thực hiện xóa đi phần tử ở trên đỉnh đã được lấy ra.

Như trong ví dụ dưới đây, Stack được thêm (push) lần lượt các phần tử: 20, 13, 89, 90, 11, 45, 18 vào trên đỉnh ngăn xếp. Giả sử, ta cần thực hiện việc lấy ra và đồng thời xóa (pop) đi 3 phần tử 18, 45, 11 có trong (trên đỉnh) Stack này. Khi đó, việc lấy ra phần tử trên đỉnh Stack và xóa đi chúng sẽ được xử lý theo trình tự 18 -> 45 – >11

Đoạn code dưới đây, thực hiện thêm (push) các phần tử 20, 13, 89, 90, 11, 45, 18 vào trên đỉnh Stack bằng cách sử dụng phương thức push() và sau đó thực hiện lấy ra 3 phần tử trên đỉnh Stack và đồng thời xóa đi (pop) phần tử đó thông qua phương thức pop() như sau:

import java.util.Stack;  
public class Main{  
    public static void main(String[] args){  
        //Tao mot stack voi kieu Integer  
        Stack<Integer> stk = new Stack<>();  
        //Mac dinh khi khoi tao stack nay se la rong
        System.out.println("Stack la rong khi khoi tao? " + stk.empty());
        //Push phan tu: 20, 13, 89, 90, 11, 45, 18 vao dinh Stack
        stk.push(20);  
        stk.push(13);  
        stk.push(89);  
        stk.push(90);
        stk.push(11);  
        stk.push(45);  
        stk.push(18);
        //Kiem tra stack con rong sau khi push hay khong?
        System.out.println("Stack la rong sau khi push? " + stk.empty());
        //Hien thi cac phan tu trong stack ban dau
        System.out.println("Phan tu Stack ban dau: " + stk);
        //Pop phan tu 18,45,11 tren dinh Stack bang phuong thuc pop()
        //Lay ra va xoa phan tu 18
        System.out.println("Phan tu duoc lay ra va xoa khoi Stack: " + stk.pop());
        //Lay ra va xoa phan tu 45
        System.out.println("Phan tu duoc lay ra va xoa khoi Stack: " + stk.pop());
        //Lay ra va xoa phan tu 11
        System.out.println("Phan tu duoc lay ra va xoa khoi Stack: " + stk.pop());
        //Stack sau khi pop 3 phan tu
        System.out.println("Phan tu Stack sau khi pop 3 phan tu: " + stk);
    }
}

Kết quả:

Stack la rong khi khoi tao? true
Stack la rong sau khi push? false
Phan tu Stack ban dau: [20, 13, 89, 90, 11, 45, 18]
Phan tu duoc lay ra va xoa khoi Stack: 18
Phan tu duoc lay ra va xoa khoi Stack: 45
Phan tu duoc lay ra va xoa khoi Stack: 11
Phan tu Stack sau khi pop 3 phan tu: [20, 13, 89, 90]

Quá trình thực hiện push các phần tử 20, 13, 89, 90, 11, 45, 18 vào Stack trên và sau đó xóa đi 3 phần tử trên đỉnh Stack là: 18, 45, 11   được minh họa như bên dưới đây:

stack: []
push -> 20
stack: [20]
push -> 13
stack: [20, 13]
push -> 89
stack: [20, 13, 89]
push -> 90
stack: [20, 13, 89, 90]
push -> 11
stack: [20, 13, 89, 90, 11]
push -> 45
stack: [20, 13, 89, 90, 11, 45]
push -> 18
stack: [20, 13, 89, 90, 11, 45, 18]
pop -> 18
stack: [20, 13, 89, 90, 11, 45]
pop -> 45
stack: [20, 13, 89, 90, 11]
pop -> 11
stack: [20, 13, 89, 90]

3.3 Tìm kiếm phần tử trong Stack

Việc tìm kiếm một phần tử có trong Stack hay không cũng được thực hiện theo trình tự từ trên đỉnh Stack đến đáy của Stack. Thực chất, việc tìm kiếm phần tử trong Stack là việc kiểm tra xem phần tử cần tìm có thuộc trong Stack hay không? Và nếu phần tử có thuộc trong Stack thì phần tử đó ở vị trí nào trong Stack?

Đối với Stack trong Java, để tìm kiếm và kiểm tra một phần tử có trong Stack hay không thì ta chỉ cần gọi đến phương thức search() – phương thức này trả về vị trí của phần tử nếu phần tử cần tìm có trong Stack và trả về -1 nếu phần tử cần tìm không có trong Stack.

import java.util.Stack;  
public class Main{  
    public static void main(String[] args){  
        //Tao mot stack voi kieu Integer  
        Stack<Integer> stk = new Stack<>();  
        //Mac dinh khi khoi tao stack nay se la rong
        System.out.println("Stack la rong khi khoi tao? " + stk.empty());
        //Push phan tu: 20, 13, 89, 90, 11, 45, 18 vao dinh Stack
        stk.push(20);  
        stk.push(13);  
        stk.push(89);  
        stk.push(90);
        stk.push(11);  
        stk.push(45);  
        stk.push(18);
        //Kiem tra stack con rong sau khi push hay khong?
        System.out.println("Stack la rong sau khi push? " + stk.empty());
        //Hien thi cac phan tu trong stack ban dau
        System.out.println("Phan tu Stack ban dau: " + stk);
        //Tim kiem phan tu 90 trong Stack
        int result = stk.search(90);
        System.out.println("Vi tri phan tu 90 trong stack: " + result);
        //Tim kiem phan tu 100 khong co trong Stack se tra ve -1
        int result2 = stk.search(100);
        System.out.println("Vi tri phan tu 100 trong stack: " + result2);
        
    }
}

Kết quả:

Stack la rong khi khoi tao? true
Stack la rong sau khi push? false
Phan tu Stack ban dau: [20, 13, 89, 90, 11, 45, 18]
Vi tri phan tu 90 trong stack: 4
Vi tri phan tu 100 trong stack: -1

3.4 Duyệt Stack trong Java

Chúng ta hoàn toàn có thể duyệt qua một ngăn xếp Stack trong Java với vòng lặp forEach(). Việc duyệt qua các phần tử có trong Stack giúp ta có thể thao tác thay đổi giá trị hoặc loại bỏ phần tử đó ra khỏi Stack theo một cách thủ công nhất.

import java.util.Stack;  
public class Main{  
    public static void main(String[] args){  
        //Tao mot stack voi kieu Integer  
        Stack<Integer> stk = new Stack<>();  
        //Mac dinh khi khoi tao stack nay se la rong
        System.out.println("Stack la rong khi khoi tao? " + stk.empty());
        //Push phan tu: 20, 13, 89, 90, 11, 45, 18 vao dinh Stack
        stk.push(20);  
        stk.push(13);  
        stk.push(89);  
        stk.push(90);
        stk.push(11);  
        stk.push(45);  
        stk.push(18);
        //Kiem tra stack con rong sau khi push hay khong?
        System.out.println("Stack la rong sau khi push? " + stk.empty());
        //Hien thi cac phan tu trong stack ban dau
        System.out.println("Phan tu Stack ban dau: " + stk);
        //Duyet qua cac phan tu trong stack
        System.out.println("Duyet tung phan tu trong Stack:");
        //Su dung phuong thuc forEach() de duyet
        stk.forEach(n -> {
            //Neu phan tu co gia tri 90 thi thay doi bang 100
            if(n == 90){
            	n = 100;
            }
            //Hien thi tung phan tu sau khi duyet
            System.out.println(n);
        }); 
    }
}

Kết quả:

Stack la rong khi khoi tao? true
Stack la rong sau khi push? false
Phan tu Stack ban dau: [20, 13, 89, 90, 11, 45, 18]
Duyet tung phan tu trong Stack:
20
13
89
100
11
45
18

4. Các phương thức của Stack trong Java

Trong các ví dụ trên, chúng ta đã cùng nhau sử dụng các phương thức phổ biến khi thao tác thêm phần tử vào Stack, lấy ra phần tử và xóa khỏi Stack, tìm kiếm trong Stack… đó là các phương thức: push(), pop(), search(),…Tuy nhiên vẫn còn rất nhiều các phương thức được sử dụng kèm với Stack để tiện lợi sử dụng Stack một cách dễ dàng hơn.

Các phương thức này được chúng tôi liệt kê bên dưới đây, và ngoài ra Stack được phát triển và kế thừa dựa trên Vector trong Java, vì thế mà Stack cũng có các phương thức của lớp Vector (bạn có thể xem lại bài Vector để tìm hiểu thêm các phương thức này) dưới đây sẽ chỉ bao gồm các phương thức dành riêng cho lớp Stack trong Java:

Phương thức
Mô tả

boolean empty()
Kiểm tra Stack có rỗng hay không? Nếu có trả về true, ngược lại trả về false

Object peek()
Lấy ra phần tử trên đỉnh của Stack nhưng KHÔNG đồng thời xóa nó.

Object pop()
Lấy ra phần tử trên đỉnh của Stack và đồng thời xóa đi nó.

Object push(Object element)
Thêm phần tử vào trên đỉnh Stack

int search(Object element)
Tìm kiếm phần tử có trong Stack. Nếu có trả về vị trí phần tử, ngược lại nếu KHÔNG có trả về -1