Class Stack<E>
Stack là một cấu trúc dữ liệu tuyến tính được sử dụng để lưu trữ một tập hợp các đối tượng theo nguyên tắc Last-In-First-Out (LIFO) nghĩa là "vào sau ra trước". Điều này có nghĩa là phần tử được thêm vào sau cùng sẽ được lấy ra đầu tiên.
Cách hoạt động của Stack
1. Thêm phần tử (Push):
Khi bạn thêm một phần tử vào Stack, phần tử này sẽ được đặt lên đỉnh của Stack. Trong Java, bạn có thể sử dụng phương thức push() để thêm phần tử.
2. Lấy phần tử (Pop):
Khi bạn lấy một phần tử ra khỏi Stack, phần tử trên đỉnh sẽ được lấy ra. Trong Java, phương thức pop() sẽ lấy và xóa phần tử trên đỉnh Stack.
Cấu trúc của một phần tử trong Stack
1. Phần tử (Element)
↳ Dữ liệu (Data): Mỗi phần tử trong Stack là một đối tượng chứa dữ liệu. Dữ liệu này có thể là bất kỳ kiểu dữ liệu nào, như số nguyên, chuỗi, đối tượng tùy chỉnh, v.v.
↳ Vị trí (Position): Phần tử trong Stack được tổ chức theo thứ tự, với phần tử được thêm vào sau cùng nằm ở đỉnh (top) của Stack.
2. Con trỏ đỉnh (Top Pointer)
↳ Mô tả: Top là một con trỏ hoặc chỉ số trong Stack trỏ đến phần tử hiện tại ở đỉnh của Stack.
↳ Vai trò: Khi một phần tử mới được thêm vào, top sẽ di chuyển đến vị trí mới của phần tử đó. Khi một phần tử bị loại bỏ, top sẽ quay lại vị trí của phần tử trước đó.
Cách tự triển khai một thư viện chuẩn cho cấu trúc dữ liệu Stack trong Java mà không sử dụng thư viện có sẵn:
Cách tự triển khai
// Tạo lớp Stack với kiểu dữ liệu tổng quát (generic)
public class Stack<T> {
private Node<T> top; // Đỉnh của stack
private int size; // Kích thước của stack
// Lớp Node đại diện cho mỗi phần tử trong stack
private static class Node<T> {
private T data; // Dữ liệu của node
private Node<T> next; // Liên kết tới node kế tiếp
// Constructor
public Node(T data) {
this.data = data;
}
}
// Constructor của Stack
public Stack() {
top = null;
size = 0;
}
// Thêm phần tử vào stack (push)
public void push(T data) {
Node<T> newNode = new Node<>(data); // Tạo node mới
newNode.next = top; // Liên kết node mới với đỉnh hiện tại
top = newNode; // Đỉnh mới của stack là node mới
size++; // Tăng kích thước stack
}
// Lấy và xóa phần tử khỏi stack (pop)
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("Stack rỗng");
}
T data = top.data; // Lấy dữ liệu của đỉnh hiện tại
top = top.next; // Chuyển đỉnh stack xuống node kế tiếp
size--; // Giảm kích thước stack
return data; // Trả về dữ liệu của đỉnh trước
}
// Xem phần tử ở đỉnh mà không xóa nó (peek)
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Stack rỗng");
}
return top.data; // Trả về dữ liệu của đỉnh
}
// Kiểm tra nếu stack rỗng
public boolean isEmpty() {
return top == null;
}
// Lấy kích thước của stack
public int size() {
return size;
}
// Duyệt qua các phần tử trong stack
public void printStack() {
Node<T> current = top;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
}
Khai báo Class Stack<E> trong Java
Để sử dụng Class Stack<E>, bạn cần import gói java.util vào đầu file Java của mình. Gói này cung cấp các lớp và giao diện để làm việc với các collection trong Java.
Cú pháp câu lệnh import:
Cú pháp
import java.util.Stack;
Cú pháp khai báo Class Stack<E>:
Cú pháp
public class Stack<E>
extends Vector<E>
Dưới đây là giải thích chi tiết về cú pháp khai báo này:
↳ public: Là access modifier – cho phép lớp Stack được truy cập từ bất kỳ đâu trong chương trình.
↳ class: Từ khóa khai báo lớp trong Java.
↳ Stack<E>: Tên lớp là Stack và sử dụng generic E để đại diện cho kiểu dữ liệu phần tử bên trong ngăn xếp.
↳ extends Vector<E>: Lớp Stack kế thừa từ lớp Vector. Điều này có nghĩa là Stack là một loại Vector với tất cả các phương thức và thuộc tính của Vector. Ngoài ra, lớp Stack cũng có thể thêm vào hoặc ghi đè các phương thức của Vector để cung cấp thêm các chức năng đặc biệt, như các phương thức liên quan đến cấu trúc dữ liệu ngăn xếp (stack) như push, pop, peek, v.v.
Constructor của lớp Stack
Lớp Stack trong Java chỉ có một constructor duy nhất đó là:
↳ Stack(): Tạo một stack rỗng.
Constructor này sẽ tạo ra một stack rỗng, sẵn sàng để bạn thêm các phần tử vào.
Ví dụ
Stack<String> stack = new Stack<>();
Tại sao Stack chỉ có một constructor đơn giản như vậy?
↳ Tính chất LIFO: Stack tuân theo nguyên tắc LIFO (Last In First Out), tức là phần tử nào được thêm vào sau cùng sẽ được lấy ra trước. Việc chỉ cần một stack rỗng để bắt đầu là đủ để thực hiện các thao tác cơ bản của một stack.
↳ Kế thừa từ Vector: Lớp Stack trong Java thực chất là một lớp con của lớp Vector. Vì vậy, nó kế thừa tất cả các phương thức và thuộc tính của Vector, bao gồm cả việc tăng dung lượng tự động khi cần thiết.
Các phương thức chính trong lớp Stack
Lớp Stack trong Java cung cấp các phương thức cơ bản để thao tác với stack, bao gồm thêm, lấy và xóa phần tử đỉnh. Nó là một cấu trúc dữ liệu hữu ích cho việc lưu trữ và xử lý dữ liệu theo thứ tự LIFO (Last-In-First-Out). Dưới đây là danh sách tất cả các phương thức của Class Stack<E> trong Java:
↳ boolean empty(): Kiểm tra xem stack có rỗng hay không.
↳ E peek(): Lấy phần tử đỉnh của stack mà không xóa nó.
↳ E pop(): Lấy và xóa phần tử đỉnh của stack.
↳ E push(E item): Thêm phần tử vào đỉnh của stack.
↳ Int search(Object o): Tìm vị trí của phần tử o trong stack (đếm từ 1).
Ví dụ cách sử dụng phương thức empty()
↳ Phương thức empty() đơn giản trả về một giá trị boolean (true hoặc false) để cho biết stack hiện tại có rỗng hay không.
↳ Trả về true: Nếu stack không chứa bất kỳ phần tử nào.
↳ Trả về false: Nếu stack có ít nhất một phần tử.
Dưới đây là ví dụ về cách sử dụng phương thức empty() của lớp Stack để kiểm tra xem stack có rỗng hay không, với kiểu dữ liệu String:
Ví dụ: Example.java
import java.util.Stack;
public class Example {
public static void main(String[] args) {
// Tạo một Stack với kiểu dữ liệu String
Stack<String> stack = new Stack<>();
// Kiểm tra nếu Stack rỗng
System.out.println("Stack có rỗng không? " + stack.empty()); // True
// Thêm một số phần tử vào Stack
stack.push("Apple");
stack.push("Banana");
stack.push("Cherry");
// Kiểm tra lại nếu Stack rỗng sau khi thêm phần tử
System.out.println("Stack có rỗng không? " + stack.empty()); // False
// Xóa tất cả các phần tử khỏi Stack
stack.pop(); // Xóa "Cherry"
stack.pop(); // Xóa "Banana"
stack.pop(); // Xóa "Apple"
// Kiểm tra nếu Stack rỗng sau khi xóa tất cả các phần tử
System.out.println("Stack có rỗng không? " + stack.empty()); // True
}
}
Kết quả của chương trình là:
Stack có rỗng không? false
Stack có rỗng không? true
Ví dụ về cách sử dụng phương thức peek()
Dưới đây là ví dụ về cách sử dụng phương thức peek() của lớp Stack để lấy phần tử đỉnh của stack mà không xóa nó, với kiểu dữ liệu Integer:
Ví dụ: Example.java
import java.util.Stack;
public class Example {
public static void main(String[] args) {
// Tạo một Stack với kiểu dữ liệu Integer
Stack<Integer> stack = new Stack<>();
// Thêm một số phần tử vào Stack
stack.push(10);
stack.push(20);
stack.push(30);
// Lấy và in phần tử đỉnh của Stack mà không xóa nó
System.out.println("Phần tử đỉnh hiện tại của Stack: " + stack.peek()); // 30
// In toàn bộ Stack để xem cấu trúc
System.out.println("Toàn bộ Stack: " + stack);
// Xóa phần tử đỉnh của Stack
stack.pop();
// Lấy và in phần tử đỉnh mới của Stack sau khi xóa phần tử đỉnh trước đó
System.out.println("Phần tử đỉnh mới của Stack sau khi xóa: " + stack.peek()); // 20
}
}
Kết quả của chương trình là:
Toàn bộ Stack: [10, 20, 30]
Phần tử đỉnh mới của Stack sau khi xóa: 20
Ví dụ về cách sử dụng phương thức pop()
Dưới đây là ví dụ về cách sử dụng phương thức pop() của lớp Stack để lấy và xóa phần tử đỉnh của stack, với kiểu dữ liệu Double:
Ví dụ: Example.java
import java.util.Stack;
public class Example {
public static void main(String[] args) {
// Tạo một Stack với kiểu dữ liệu Double
Stack<Double> stack = new Stack<>();
// Thêm một số phần tử vào Stack
stack.push(1.1);
stack.push(2.2);
stack.push(3.3);
// In Stack trước khi gọi pop()
System.out.println("Stack trước khi gọi pop(): " + stack);
// Lấy và xóa phần tử đỉnh của Stack
Double topElement = stack.pop();
System.out.println("Phần tử đỉnh đã bị xóa: " + topElement);
// In Stack sau khi gọi pop()
System.out.println("Stack sau khi gọi pop(): " + stack);
// Lấy phần tử đỉnh mới của Stack
Double newTopElement = stack.peek();
System.out.println("Phần tử đỉnh mới sau khi gọi pop(): " + newTopElement);
}
}
Kết quả của chương trình là:
Phần tử đỉnh đã bị xóa: 3.3
Stack sau khi gọi pop(): [1.1, 2.2]
Phần tử đỉnh mới sau khi gọi pop(): 2.2
Ví dụ về cách sử dụng phương thức push(E item)
Dưới đây là ví dụ về cách sử dụng phương thức push(E item) của lớp Stack để thêm phần tử vào đỉnh của stack, với kiểu dữ liệu String:
Ví dụ: Example.java
import java.util.Stack;
public class Example {
public static void main(String[] args) {
// Tạo một Stack với kiểu dữ liệu String
Stack<String> stack = new Stack<>();
// Thêm các phần tử vào đỉnh của Stack
stack.push("Apple");
stack.push("Banana");
stack.push("Cherry");
// In Stack sau khi thêm các phần tử
System.out.println("Stack sau khi thêm các phần tử:");
for (String item : stack) {
System.out.println(item);
}
}
}
Kết quả của chương trình là:
Stack sau khi thêm các phần tử:
Apple
Banana
Cherry
Sau khi thêm các phần tử, in toàn bộ stack để thấy cấu trúc của nó. Phần tử "Cherry" sẽ là phần tử đỉnh vì nó là phần tử cuối cùng được thêm vào stack.
Ví dụ minh họa cách sử dụng search(Object o)
↳ Phương thức search(Object o) của lớp Stack tìm vị trí của phần tử o trong stack, đếm từ 1 bắt đầu từ đỉnh của stack. Nếu phần tử không tồn tại trong stack, phương thức sẽ trả về -1.
Dưới đây là ví dụ minh họa cách sử dụng search(Object o) với kiểu dữ liệu String:
Ví dụ: Example.java
import java.util.Stack;
public class Example {
public static void main(String[] args) {
// Tạo một Stack với kiểu dữ liệu String
Stack<String> stack = new Stack<>();
// Thêm các phần tử vào đỉnh của Stack
stack.push("Apple");
stack.push("Banana");
stack.push("Cherry");
stack.push("Date");
stack.push("Elderberry");
// Tìm vị trí của các phần tử trong Stack
int position1 = stack.search("Cherry"); // Tìm vị trí của "Cherry"
int position2 = stack.search("Banana"); // Tìm vị trí của "Banana"
int position3 = stack.search("Fig"); // Tìm vị trí của "Fig", không tồn tại trong stack
// In kết quả tìm kiếm
System.out.println("Vị trí của 'Cherry': " + position1); // 3
System.out.println("Vị trí của 'Banana': " + position2); // 4
System.out.println("Vị trí của 'Fig': " + position3); // -1
}
}
Kết quả của chương trình là:
Vị trí của 'Banana': 4
Vị trí của 'Fig': -1
Ví dụ duyệt qua phần tử của Stack
Bạn có thể duyệt qua các phần tử của stack bằng cách sử dụng vòng lặp for-each hoặc bằng cách sử dụng phương thức iterator():
Ví dụ: Example.java
import java.util.Stack;
public class Example {
public static void main(String[] args) {
// Tạo một Stack với kiểu dữ liệu String
Stack<String> stack = new Stack<>();
stack.push("Apple");
stack.push("Banana");
stack.push("Cherry");
// Duyệt qua Stack bằng vòng lặp for-each
System.out.println("Duyệt qua Stack bằng vòng lặp for-each:");
for (String item : stack) {
System.out.println(item);
}
// Duyệt qua Stack bằng iterator
System.out.println("Duyệt qua Stack bằng iterator:");
java.util.Iterator<String> iterator = stack.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
Kết quả của chương trình là:
Duyệt qua Stack bằng vòng lặp for-each:
Apple
Banana
Cherry
Duyệt qua Stack bằng iterator:
Apple
Banana
Cherry
Ví dụ so sánh các phần tử với Stack
Bạn có thể so sánh hai Stack bằng cách sử dụng phương thức equals(Object o). Nếu hai stack có cùng số lượng phần tử và các phần tử tương ứng giống nhau, equals sẽ trả về true.
Ví dụ: Example.java
import java.util.Stack;
public class Example {
public static void main(String[] args) {
// Tạo hai Stack với kiểu dữ liệu String
Stack<String> stack1 = new Stack<>();
Stack<String> stack2 = new Stack<>();
// Thêm các phần tử vào stack1
stack1.push("Apple");
stack1.push("Banana");
stack1.push("Cherry");
// Thêm các phần tử vào stack2
stack2.push("Apple");
stack2.push("Banana");
stack2.push("Cherry");
// So sánh hai Stack
System.out.println("Stack1 và Stack2 có bằng nhau không? " + stack1.equals(stack2)); // True
// Thay đổi stack2
stack2.pop(); // Xóa phần tử "Cherry"
stack2.push("Date");
// So sánh lại
System.out.println("Stack1 và Stack2 có bằng nhau không sau khi thay đổi? " + stack1.equals(stack2)); // False
}
}
Kết quả của chương trình là:
Stack1 và Stack2 có bằng nhau không sau khi thay đổi? false
Ví dụ stack với đối tượng do người dùng định nghĩa
Dưới đây là ví dụ về cách sử dụng lớp Stack với một đối tượng do người dùng định nghĩa. Trong ví dụ này, chúng ta sẽ định nghĩa một lớp Person với các thuộc tính name và age, và sau đó sử dụng lớp Stack để lưu trữ các đối tượng Person.
Ví dụ: Example.java
import java.util.Stack;
class Person {
private String name;
private int age;
// Constructor
public Person(String name, int age) {
this.name = name;
this.age = age;
}
// Getter và Setter
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
// Phương thức toString() để in thông tin đối tượng
@Override
public String toString() {
return "Person{Tên='" + name + "', Tuổi=" + age + "}";
}
}
public class Example {
public static void main(String[] args) {
// Tạo một Stack với kiểu dữ liệu Person
Stack<Person> stack = new Stack<>();
// Thêm các đối tượng Person vào đỉnh của Stack
stack.push(new Person("Vuong", 30));
stack.push(new Person("Truong", 25));
stack.push(new Person("Duong", 35));
// Duyệt qua Stack và in các đối tượng Person
System.out.println("Duyệt qua Stack bằng vòng lặp for-each:");
for (Person person : stack) {
System.out.println(person);
}
// Sử dụng phương thức peek() để lấy phần tử đỉnh mà không xóa nó
System.out.println("\nPhần tử đỉnh hiện tại của Stack: " + stack.peek());
// Xóa phần tử đỉnh của Stack bằng phương thức pop()
System.out.println("\nXóa phần tử đỉnh của Stack: " + stack.pop());
// Duyệt qua Stack sau khi xóa phần tử đỉnh
System.out.println("\nDuyệt qua Stack sau khi xóa phần tử đỉnh:");
for (Person person : stack) {
System.out.println(person);
}
}
}
Kết quả của chương trình là:
Person{Tên='Vuong', Tuổi=30}
Person{Tên='Truong', Tuổi=25}
Person{Tên='Duong', Tuổi=35}
Phần tử đỉnh hiện tại của Stack: Person{Tên='Duong', Tuổi=35}
Xóa phần tử đỉnh của Stack: Person{Tên='Duong', Tuổi=35}
Duyệt qua Stack sau khi xóa phần tử đỉnh:
Person{Tên='Vuong', Tuổi=30}
Person{Tên='Truong', Tuổi=25}
Như vậy, chúng ta đã tìm hiểu các phương thức chính của lớp Stack trong Java. Với nguyên tắc hoạt động LIFO (Last-In-First-Out), Stack là một cấu trúc dữ liệu cơ bản nhưng cực kỳ quan trọng cho nhiều tác vụ như quản lý lời gọi hàm, duyệt cây, hoặc giải các bài toán đệ quy. Nắm vững cách sử dụng các phương thức thêm (push), lấy (pop), và kiểm tra phần tử đỉnh (peek) sẽ giúp bạn áp dụng Stack hiệu quả vào các bài toán lập trình của mình.