Cấu trúc dữ liệu ngăn xếp là gì
Trước hết, chúng ta hãy xem nhanh cấu trúc dữ liệu ngăn xếp là gì. Đó là cấu trúc dữ liệu tuyến tính dựa trên nguyên tắc Nhập trước xuất trước (LIFO). Đó là loại chống xếp hàng. Hãy tưởng tượng một cỗ bài hoặc một chồng sách trong hộp. Cuốn sách mà bạn đặt vào ngăn xếp đầu tiên nằm ở dưới cùng và cuốn sách đầu tiên chúng ta sẽ lấy ra khỏi hộp là cuốn sách ở trên cùng - tức là cuốn sách được cho vào hộp cuối cùng. Dưới đây là một hình ảnh gif để chứng minh nguyên tắc này.
Cấu trúc dữ liệu Stack để làm gì?
Một trong những ứng dụng quan trọng nhất của ngăn xếp là tổ chức các cuộc gọi chương trình con. Điểm gọi trên ngăn xếp lưu trữ địa chỉ trả về từ chương trình con sau khi nó kết thúc (và có thể cả các tham số được truyền vào). Với mỗi lệnh gọi lồng nhau (bao gồm cả đệ quy) của các chương trình con, các địa chỉ trả về mới được thêm vào ngăn xếp. Với mỗi thao tác trả về từ chương trình con (trả về), địa chỉ trả về sẽ bị xóa khỏi ngăn xếp và quyền điều khiển được chuyển đến nó. Ứng dụng này quan trọng đối với lập trình đến nỗi trong hầu hết các bộ xử lý, ngăn xếp trả về được triển khai trong phần cứng trong tập lệnh. Tuy nhiên, trong các trường hợp khác, ngăn xếp phải được mô hình hóa trên các cấu trúc dữ liệu tổng quát hơn.Lớp khung công tác bộ sưu tập Java Stack
Trong Java Lớp ngăn xếp là một lớp từ khung Bộ sưu tập thực hiện giao diện Danh sách và mở rộng lớp Vector. Nó cũng triển khai các giao diện Collection, Iterable, Cloneable, Serializable. Như bạn có thể đã đoán, lớp này đại diện cho chồng đối tượng LIFO. Đây là lệnh gọi hàm tạo của lớp Stack , nghĩa là tạo một đối tượng của lớp này.
Stack<E> stack = new Stack<E>();
Trong đó E là loại Đối tượng.
Phương pháp ngăn xếp Java
Lớp này chỉ có một hàm tạo mặc định và tất cả các phương thức của lớp Vector . Ngoài ra, Stack có 5 phương thức riêng:-
boolean empty() phương thức kiểm tra xem ngăn xếp có rỗng hay không. Trả về true nếu ngăn xếp trống, false nếu không.
-
Đối tượng peek() phương thức trả về phần tử ở trên cùng của ngăn xếp.
-
Object pop() phương thức trả về phần tử ở trên cùng của ngăn xếp và loại bỏ nó.
-
Đẩy đối tượng(Phần tử đối tượng) phương thức thêm phần tử đã chỉ định vào đầu ngăn xếp.
-
int search(Object element) phương thức tìm kiếm ngăn xếp cho phần tử đã chỉ định. Nếu phần tử được yêu cầu được tìm thấy, thì "khoảng cách" của nó từ trên cùng (số sê-ri) sẽ được trả về. Nếu phần tử không được tìm thấy, -1 được trả về.
Ví dụ mã ngăn xếp
Hãy tạo một ví dụ chương trình hoạt động như ảnh gif ở trên. Chúng tôi sẽ đặt ba "quả bóng", cam, tím và xanh lá cây, trên ngăn xếp. Hãy kiểm tra ngăn xếp xem có trống không. Sau đó, chúng tôi sẽ lấy các quả bóng từ ngăn xếp cho đến khi ngăn xếp trống.
import java.util.Stack;
public class myStackTest2 {
public static void main(String[] args)
{
Stack myStack= new Stack<>();
System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
myStack.push("Orange Ball");
myStack.push("Violet Ball");
myStack.push("Green Ball");
//prints elements of the stack
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
while (!myStack.isEmpty()) {
myStack.pop();
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
}
}
}
Đây là đầu ra của chương trình này:
import java.util.Stack;
public class myStackTest2 {
public static void main(String[] args)
{
Stack myStack= new Stack<>();
System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
myStack.add("Orange Ball");
myStack.add("Violet Ball");
myStack.add("Green Ball");
//prints elements of the stack
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
while (!myStack.isEmpty()) {
myStack.pop();
System.out.println("Elements in Stack: " + myStack);
System.out.println("Is my stack empty? " + myStack.empty());
}
}
}
Tất nhiên, kết quả của công việc chương trình sẽ giống hệt nhau.
Còn việc triển khai Stack của riêng bạn thì sao?
Bạn có thể tạo cấu trúc dữ liệu ngăn xếp của riêng mình trong Java bằng cách sử dụng mảng hoặc lớp danh sách liên kết. Trong trường hợp đầu tiên, một mảng ô liên tục được phân bổ để lưu trữ các giá trị trong bộ nhớ, được sử dụng khi cần thiết. Trong trường hợp thứ hai, đối với mỗi phần tử của ngăn xếp, một khối bộ nhớ được sắp xếp, đủ để lưu trữ giá trị và tham chiếu đến các phần tử trước đó và tiếp theo của ngăn xếp. Việc triển khai dựa trên mảng đơn giản hơn, hiệu quả hơn và tiết kiệm bộ nhớ hơn, nhưng nó yêu cầu kiến thức trước về giới hạn kích thước ngăn xếp và có thể dẫn đến các lỗi khó tìm. Việc triển khai dựa trên danh sách mạnh mẽ hơn nhưng kém hiệu quả hơn. Hãy thực hiện một triển khai ngăn xếp dựa trên mảng đơn giản. Nó sẽ bao gồm các chức năng.-
đẩy - một phương thức sẽ đảm bảo thêm một phần tử (ở vị trí trên cùng)
-
pop — một phương thức sẽ cung cấp việc loại bỏ một phần tử (từ vị trí trên cùng)
-
readTop — một phương thức sẽ trả về giá trị của phần tử ở vị trí trên cùng
-
sEmpty — một phương thức sẽ kiểm tra sự trống rỗng của ngăn xếp
-
isFull — một phương thức sẽ kiểm tra xem mảng mà chúng ta lưu trữ ngăn xếp có đầy không
import java.util.Arrays;
public class MyStack {
private int maxSize;
private String[] stackArray;
private int top;
public MyStack(int size) {
this.maxSize = size;
stackArray = new String[maxSize];
top = -1;
}
public String push (String element) {
return stackArray[++top] = element;
}
public String pop (String element) {
if (isEmpty())
{
System.out.println("Underflow\nProgram Terminated");
System.exit(-1);
}
System.out.println("Removing " + readTop());
return stackArray[top--];
}
public String readTop() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
public void printStack(){
System.out.println(Arrays.toString(stackArray));
}
}
Bây giờ, hãy thực hiện một ví dụ với ba quả bóng dựa trên ngăn xếp của chúng tôi:
public class myStackTest {
public static void main(String[] args) {
MyStack myStack = new MyStack(3);
System.out.println("Is my stack empty? " + myStack.isEmpty());
myStack.push("Orange Ball");
myStack.push("Violet Ball");
myStack.push("Green Ball");
myStack.printStack();
System.out.println("Is my stack empty? " + myStack.isEmpty());
while (!myStack.isEmpty()) {
myStack.pop(myStack.readTop());
System.out.println("Is my stack empty? " + myStack.isEmpty());
}
}
}
Đầu ra ở đây:
GO TO FULL VERSION