Ngăn xếp Java

Ngăn xếp trong Java thường có nghĩa là lớp từ Bộ sưu tập Khung triển khai giao diện Danh sách. Nó hoạt động theo nguyên tắc cấu trúc dữ liệu Stack, được sử dụng để tổ chức một trong các loại bộ nhớ. Ngoài ra, nó có thể là một phần của bộ nhớ để lưu giữ dữ liệu, Trong bài viết này, trước hết chúng ta sẽ chú ý đến lớp Stack , xem xét các phương thức của nó và đưa ra các ví dụ. Nhưng chúng ta cũng sẽ nói về cấu trúc dữ liệu như Stack và nó được sử dụng để làm gì.

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. Những gì đang xảy ra ở đây? Chúng tôi có một cái bình trong đó mỗi lần chỉ có thể đánh một quả bóng. Đầu tiên trong bình là một quả bóng màu cam, sau đó là màu tím và cuối cùng là màu xanh lá cây (tôi xin lỗi những ai biết tên chính xác hơn của những màu này). Tuy nhiên, để lấy một quả bóng màu cam từ ngăn xếp bình của chúng ta, trước tiên chúng ta cần lấy quả bóng ở đó cuối cùng (quả màu xanh lá cây), sau đó là quả bóng áp chót (nhưng tại thời điểm lấy nó là quả cuối cùng). một). Cấu trúc dữ liệu ngăn xếp trong Java hay bất kỳ nơi nào khác trong lập trình có hai thao tác quan trọng nhất là đẩy và bật . Thao tác đẩy chèn một phần tử vào ngăn xếp và thao tác pop loại bỏ một phần tử khỏi đỉnh ngăn xếp.

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: Do Stack được kế thừa từ Lớp Vector và triển khai giao diện Danh sách , nên ngoài các thao tác đẩy và bật cổ điển cho cấu trúc dữ liệu này để thêm và trích xuất các phần tử, Stack còn có tiêu chuẩn cho các thao tác thêm () và xóa () của cấu trúc danh sách . Trong ví dụ của chúng tôi, việc thêm các phần tử có thể được thực hiện theo cách tương tự bằng cách sử dụng phương thức add() . Tuy nhiên, bạn chỉ có thể trích xuất bằng cách sử dụng remove() với một phần tử được chỉ định, điều này không có ý nghĩa gì đối với cấu trúc dữ liệu ngăn xếp.

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: Nếu bạn nhìn kỹ, biến trên cùng thực sự chứa chỉ mục của phần tử cuối cùng và tham chiếu đến đối tượng vẫn còn trong mảng. Vì vậy, việc thực hiện này cần một số cải tiến. Hãy suy nghĩ về cách dễ nhất để làm điều này.

Chúng ta có nên sử dụng Java Stack không?

Trên thực tế, Java Stack , giống như Vector cha của nó, là một lớp kế thừa. Thay vào đó, lớp ArrayList thường được sử dụng. ArrayList không được đồng bộ hóa trong khi Vector được đồng bộ hóa. Điều đó có nghĩa là với Vector, chỉ một luồng tại một thời điểm có thể truy cập mã, trong khi ArrayList có thể hoạt động với nhiều luồng. Ngoài ra, ArrayList hiệu quả hơn và nhanh hơn. Vì vậy, rất có thể bạn sẽ chỉ thấy lớp này trong mã kế thừa. Nhưng cấu trúc dữ liệu Stack được sử dụng rất thường xuyên trong lập trình.