Java Stack 101: Đi sâu vào Lớp ngăn xếp

Ngăn xếp trong Java là một cấu trúc dữ liệu, giống như hàng đợi, mảng, danh sách liên kết hoặc cây. Điểm khác biệt so với những cái khác là Ngăn xếp Java dựa trên nguyên tắc Nhập sau, Xuất trước (LIFO). Điều này có nghĩa là khi bạn sử dụng hai lệnh để thêm và xóa một phần tử khỏi ngăn xếp, phần tử đầu tiên bạn xóa sẽ luôn là phần tử cuối cùng bạn thêm vào. Chúng ta hãy xem xét kỹ hơn về Lớp ngăn xếp Java

Khám phá Lớp ngăn xếp Java

Lớp ngăn xếp Java là một phần mở rộng của lớp Vector , chính lớp này mở rộng lớp Danh sách . Bởi vì các vectơ có thể thay đổi và có thể phát triển và co lại theo yêu cầu của các phần tử bên trong, Stack s cũng có thể thay đổi kích thước theo yêu cầu. Phần mở rộng của lớp Vector thêm năm thao tác biến Vector thành Stack . Năm hoạt động này là:

• .push(E item) – đặt một phần tử lên trên cùng của ngăn xếp
• .pop() – xóa phần tử ở đầu ngăn xếp và trả về phần tử đó dưới dạng giá trị của hàm
• .peek() – nhìn vào phần tử ở trên cùng của ngăn xếp mà không xóa nó
• .empty() – Hàm Boolean để kiểm tra xem ngăn xếp có trống hay không. Trả về 0 hoặc 1.
• .search(Object o) – Tìm kiếm o và trả về vị trí của nó. Giá trị dựa trên 1, không phải dựa trên 0

Stack cũng kế thừa tất cả các phương thức là một phần của Vector , bao gồm nhưng không giới hạn toString() , contains() , indexOf() và lastElement() .

Mã hóa một ví dụ về ngăn xếp Java

Bây giờ chúng ta đã biết các chức năng của Ngăn xếp , hãy viết mã một ví dụ về ngăn xếp java. Ngăn xếp rất hữu ích để xử lý dữ liệu phải được lưu trữ tạm thời và truy xuất nhanh chóng. Vì Ngăn xếp là LIFO nên nó đặc biệt hữu ích cho việc duyệt qua nút khi khám phá cấu trúc dữ liệu dạng cây. Trước khi chúng ta tìm hiểu tất cả những điều đó, hãy tạo một ngăn xếp cơ bản. Mã để triển khai ngăn xếp như sau:

import java.util.*;

class Main {
  public static void main(String[] args) {
    Stack<Integer> stackExample = new Stack<Integer>();

Đó là tất cả những gì bạn cần làm để tạo một Stack trống . Bạn cũng có thể chỉ cần khai báo nó một cách đơn giản mà không cần khai báo kiểu dữ liệu bằng cách sử dụng:

Stack example = new Stack();

Hãy nhớ rằng vì Stack có thể thay đổi nên khi chúng ta đẩy các phần tử vào ngăn xếp, nó sẽ tự động điều chỉnh kích thước. Bây giờ hãy xem cách sử dụng các hàm Stack .

Triển khai ngăn xếp Java

Hãy xem cách sử dụng năm phương pháp mà chúng ta đã khám phá ngắn gọn trước đó. Việc triển khai ngăn xếp Java rất dễ nhớ nếu bạn coi nó như một chồng đĩa. Bạn đặt những chiếc đĩa lên ngăn xếp, nhưng để lấy một chiếc đĩa, bạn không đi xuống đáy mà lấy một chiếc từ trên xuống. Cái cuối cùng bạn mặc vào là cái đầu tiên bạn cởi ra. Mở rộng ví dụ trước của chúng ta với stackExample , các chức năng như sau:

Xô

// pushing integers onto the Stack
    stackExample.push(5);
    stackExample.push(10);

Tại thời điểm này, chúng ta sẽ hiển thị các hàm khác như thể chúng ta đã đẩy hai số nguyên này vào ví dụ ngăn xếp Java mọi lúc.

Nhạc pop

//popping integers off of the Stack
System.out.println(stackExample.pop());
System.out.println(stackExample.pop());

Đầu ra:

10
5

Không có sản phẩm nào

Bây giờ, giả sử bạn muốn xóa tất cả các phần tử khỏi Ngăn xếp nhưng bạn không chắc có bao nhiêu phần tử. Bạn có thể kết hợp hàm Boolean.isEmpty() với vòng lặp while điều kiện tiên quyết để bật tất cả các phần tử từ Stack . Hãy xem cách triển khai ngăn xếp java này được thực hiện.

while(!stackExample.isEmpty()) {      
  System.out.println(stackExample.pop());
}

đầu ra

10
5

nhìn lén

Chúng ta có thể sử dụng .peek() làm triển khai ngăn xếp trong Java để xem xét mục tiếp theo trên Ngăn xếp mà không cần xóa mục đó.

System.out.println(stackExample.peek());

đầu ra

10

Nếu chúng ta bật và in Ngăn xếp , nó sẽ trả về 10 và 5 vì 10 vẫn còn trên ngăn xếp. Chúng tôi chỉ xem xét nó, chúng tôi không loại bỏ nó bằng chức năng bật lên. Chức năng peek là một công cụ tuyệt vời cho Stack s trong java.

Tìm kiếm

Nếu chúng ta muốn tìm một phần tử cụ thể, việc triển khai ngăn xếp trong Java sử dụng .search(e); để tìm thấy nó.

System.out.println(stackExample.search(5));

đầu ra

2

Hãy nhớ rằng điều này là do chúng ta đếm từ trên cùng của Stack và Java Stack s bắt đầu từ 1, không phải 0 như Array . Vì vậy, nhìn vào ngăn xếp, nó là (10) -> (5) và 5 ở vị trí số 2. Nếu bạn cố gắng tìm một phần tử không có trong Stack , bạn sẽ nhận được -1 làm đầu ra.

lặp đi lặp lại

Khi làm việc với bất kỳ bộ sưu tập nào, có thể có lúc bạn cần tìm nhiều phần tử. Để tiết kiệm độ phức tạp và phải tìm kiếm trong Stack nhiều lần, bạn có thể sử dụng phép lặp. Bởi vì Stack trong Java mở rộng lớp List nên có một số tùy chọn để lặp lại. Một trong những cách dễ nhất là chỉ sử dụng chức năng ListIterator . ListIterator hay ở chỗ nó cho phép bạn duyệt qua một Ngăn xếp từ trên xuống dưới hoặc từ dưới lên trên bằng cách sử dụng .hasPrevious() hoặc .hasNext() . Đây là giao diện của nó:

ListIterator<Integer> exampleIterator = stackExample.listIterator(stackExample.size());

  while (exampleIterator.hasPrevious()) {
    int iteration = exampleIterator.previous();
    System.out.println(iteration);
  }

đầu ra

10
5

Hãy nhớ rằng khi bạn lặp qua Stack trong Java, bạn không loại bỏ bất kỳ phần tử nào trong đó. Việc lặp lại về cơ bản cho phép bạn xem qua mọi phần tử trong ngăn xếp theo thứ tự. Khi bạn làm điều này, bạn có thể tìm kiếm các vị trí có các phần tử nhất định, sau đó đi qua và thao tác với chúng. Bạn có thể đếm, xóa hoặc thậm chí thay đổi chúng nếu cần.