Stack - Ngăn xếp
1. Giới thiệu
Ngăn xếp là 1 dạng đặc biệt của danh sách liên kết mà việc bổ sung hay loại bỏ 1 phần tử đều thực hiện ở 1 đầu của danh sách gọi là đỉnh. Ngăn xếp có 2 thao tát cơ bản: thêm phần tử vào được gọi là push và loại bỏ phần tử được gọi là pop.
Việc loại bỏ phần tử sẽ tiến hành loại bỏ phần tử mới nhất được đưa vào danh sách, chính vì tính chất này mà ngăn xếp còn được gọi là kiểu dữ liệu LIFO (last in first out – Vào sau ra trước)
Java Collection framework cung cấp một lớp Stack mô hình hoá và triển khai cấu trúc dữ liệu Stack. Lớp này dựa trên nguyên tắc cơ bản là “last in-first out”. Ngoài các thao tác push – pop cơ bản, lớp này cung cấp thêm ba hàm: empty(), search() và peek().
Lớp Stack còn được xem là lớp mở rộng của lớp Vector, mối liên hệ được mô tả như hình:
Lớp còn hỗ trợ một phương thức khởi tạo mặc định Stack() được sử dụng để tạo một ngăn xếp trống.
1
public class Stack<E> extends Vector<E>
2. Cách khởi tạo ngăn xếp
Các Interface được thực thi trong Stack:
- Serializable: Đây là một Interface đánh dấu các lớp phải triển khai nếu chúng được tuần tự hóa và giải mã hóa.
- Cloneable: Đây là một Interface trong Java cần được thực thi bởi một lớp để cho phép các đối tượng của nó được sao chép.
- Iterable
: Interface này đại diện cho một tập hợp các đối tượng có thể lặp lại. - Collection
: Một Collection đại diện cho một nhóm các đối tượng được gọi là các phần tử. - List
: List interface cung cấp một cách để lưu trữ Collection đã được sắp xếp. Nó là một interface con của Collection. - RandomAccess: Đây là interface đánh dấu được sử dụng bởi các List implementation để chỉ ra rằng chúng hỗ trợ truy cập nhanh (thường là thời gian không đổi).
Làm thế nào để tạo một ngăn xếp?
Để tạo một ngăn xếp, chúng ta phải import gói java.util.stack và sử dụng hàm tạo Stack() của lớp này. Ví dụ dưới đây tạo một Stack trống.
1
Stack<E> stack = new Stack<E>(); // ở đây E thuộc kiểu đối tượng
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.Stack;
public class StackDemo {
// Push các phần tử vào đỉnh của Stack
static void stack_push(Stack<Integer> stack) {
for (int i = 0; i < 5; i++) {
stack.push(i);
}
}
// Pop các phần tử từ đỉnh của Stack
static void stack_pop(Stack<Integer> stack) {
System.out.println("Pop Operation:");
for (int i = 0; i < 5; i++) {
Integer y = (Integer) stack.pop();
System.out.println(y);
}
}
// Hiển thị các phần tử trên đỉnh của Stack
static void stack_peek(Stack<Integer> stack) {
Integer element = (Integer) stack.peek();
System.out.println("Element on stack top: " + element);
}
// Tìm kiếm các phần tử của stack
static void stack_search(Stack<Integer> stack, int element) {
Integer pos = (Integer) stack.search(element);
if (pos == -1)
System.out.println("Element not found");
else
System.out.println("Element is found at position: " + pos);
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<Integer>();
stack_push(stack);
stack_pop(stack);
stack_push(stack);
stack_peek(stack);
stack_search(stack, 2);
stack_search(stack, 6);
}
}
3. Các hành động và phương thức chủ yếu trên Stack
Adding Elements: Để thêm một phần tử vào ngăn xếp, chúng ta có thể sử dụng phương thức push(). Thao tác push() này đặt phần tử ở trên cùng của ngăn xếp.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Stack;
public class StackPush {
public static void main(String[] args) {
// Khởi tạo Stack mặc định
Stack stack1 = new Stack();
// Khởi tạo Stack sử dụng Generics
Stack<String> stack2 = new Stack<String>();
// Push các phần tử
stack1.push(3);
stack1.push("Michael");
stack1.push("Corleone");
stack2.push("Tom");
stack2.push("And");
stack2.push("Jerry");
// In các phần tử
System.out.println(stack1);
System.out.println(stack2);
}
}
Accessing the Element: Để truy xuất hoặc tìm nạp phần tử đầu tiên của Ngăn xếp hoặc phần tử có ở trên cùng, chúng ta có thể sử dụng phương thức peek(). Phần tử được truy xuất sẽ không bị xóa hoặc bị xóa khỏi Ngăn xếp.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Stack;
public class StackPeek {
public static void main(String args[]) {
// Tạo Stack rỗng
Stack<String> stack = new Stack<String>();
// Push các phần tử vào Stack
stack.push("Hi");
stack.push("I'm");
stack.push("Michael");
stack.push("Corleone");
stack.push("-TheGodFather");
// In các phần tử của Stack
System.out.println("Initial Stack: " + stack);
// Fetching các phần tử ở đầu của Stack
System.out.println("The element at the top of the" + " stack is: " + stack.peek());
// In Stack sau khi Peek
System.out.println("Final Stack: " + stack);
}
}
Removing Elements: Để loại bỏ một phần tử khỏi ngăn xếp, chúng ta có thể sử dụng phương thức pop(). Phần tử được loại bỏ là phần tử nằm trên cùng của ngăn xếp và được xóa khỏi Stack.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Stack;
public class StackPop {
public static void main(String args[]) {
// Tạo Stack rỗng
Stack<Integer> stack = new Stack<Integer>();
// Push các phần tử vào Stack
stack.push(10);
stack.push(15);
stack.push(30);
stack.push(20);
stack.push(5);
// In Stack
System.out.println("Initial Stack: " + stack);
// Xoá các phần tử
System.out.println("Popped element: " + stack.pop());
System.out.println("Popped element: " + stack.pop());
// Stack sau khi POP
System.out.println("Stack after pop operation " + stack);
}
}
Check Empty: Để kiểm tra một Stack có rỗng hay không chúng ta có thể sử dụng hàm empty() - Nó trả về true nếu không có gì ở trên cùng của ngăn xếp. Hoặc ngược lại trả về false.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Stack;
public class StackEmpty {
public static void main(String[] args) {
// Tạo Stack rỗng
Stack<String> stack = new Stack<String>();
// Push dữ liệu vào Stack
stack.push("Hi...");
stack.push("I'm");
stack.push("Michael");
stack.push("Corleone");
stack.push("TheGodFather");
// In stack
System.out.println("The stack is: " + stack);
// Kiểm trả xem Stack có rỗng không ?
System.out.println("Is the stack empty? --> " + stack.empty());
// Pop tất cả các phần tử của Stack
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
// Kiểm trả xem Stack có rỗng không ?
System.out.println("Is the stack empty? --> " + stack.empty());
}
}
Search Object: Để xác định xem một phần tử nào đó có tồn tại trong ngăn xếp hay không, chúng ta có thể dùng phương thức search() để kiểm tra. Nó trả về vị trí của phần tử từ trên cùng của ngăn xếp. Ngược lại, nó trả về -1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Stack;
public class StackSearch {
public static void main(String[] args) {
// Tạo Stack rỗng
Stack<String> stack = new Stack<String>();
// Push dữ liệu vào Stack
stack.push("Hi...");
stack.push("I'm");
stack.push("Michael");
stack.push("Corleone");
stack.push("TheGodFather");
// In stack
System.out.println("The stack is: " + stack);
// Kiểm tra phần tử thứ 3
System.out.println("Does the stack contains '3'? --> " + stack.search("3"));
// Kiểm tra phần tử "Michael"
System.out.println("Does the stack contains 'Michael'? --> " + stack.search("Michael"));
// Kiểm tra phần tử "Hà Nội"
System.out.println("Does the stack contains 'Hà Nội'? --> " + stack.search("Hà Nội"));
}
}
Nếu các bạn đã từng làm việc với Stack ở các ngôn ngữ khác thì trong Java cũng được tự. Chúng đều giống nhau ở bản chất và chỉ khác nhau cú pháp các câu lệnh và tính đặc thù của ngôn ngữ.
Stack là một trong những cấu trúc dữ liệu được ưa chuộng bởi các lập trình viên – nhưng chỉ hiệu quả thực sự khi áp dụng nó vào các trường hợp phù hợp.
Stack trong Java còn một vấn đề nâng cao hơn đó là Vector – phần này mình sẽ không giới thiệu và các bạn phải tìm hiểu thêm. Nếu có thời gian thì đừng lãng phí nó nhé.
Bài viết mang tính chất “ghi chú, lưu trữ, chia sẻ và phi lợi nhuận”.
Nếu bạn thấy hữu ích, đừng quên chia sẻ với bạn bè và đồng nghiệp của mình nhé!
Happy coding! 😎 👍🏻 🚀 🔥