Ngăn Xếp (Stack): Cấu Trúc Dữ Liệu LIFO và Ứng Dụng Thực Tế

Chào mừng bạn đến với bài viết thứ 5 trong series về cấu trúc dữ liệu và giải thuật.

Trong bài viết này, chúng ta sẽ khám phá một cấu trúc dữ liệu tuyến tính quan trọng: Ngăn xếp (Stack).

Chúng ta sẽ tìm hiểu về nguyên lý hoạt động LIFO (Last-In, First-Out) của nó.

Chúng ta cũng sẽ xem xét các thao tác cơ bản và các ứng dụng thực tế của Stack.

Cuối cùng, chúng ta sẽ cùng nhau triển khai Stack bằng ngôn ngữ lập trình Java.

Ngăn Xếp (Stack) là gì?

Ngăn xếp (Stack) là một cấu trúc dữ liệu tuyến tính.

Nó hoạt động dựa trên nguyên lý LIFO (Last-In, First-Out), hay còn gọi là “vào sau ra trước”.

Hãy tưởng tượng một chồng đĩa. Bạn chỉ có thể thêm đĩa mới lên trên cùng và lấy đĩa từ trên cùng.

Đĩa nào được đặt vào sau cùng sẽ là đĩa được lấy ra đầu tiên.

Đó chính là nguyên lý LIFO.

Nguyên lý LIFO (Last-In, First-Out)

LIFO là viết tắt của Last-In, First-Out.

Nguyên lý này mô tả cách thức các phần tử được thêm vào và lấy ra khỏi Stack.

Phần tử cuối cùng được thêm vào Stack sẽ là phần tử đầu tiên được lấy ra.

Điều này khác với các cấu trúc dữ liệu khác như Queue (hàng đợi), hoạt động theo nguyên lý FIFO (First-In, First-Out).

Hãy nhớ rằng Stack tuân theo quy tắc: "Ai đến sau, người ấy được phục vụ trước".

Các Thao Tác Cơ Bản của Stack

Stack có ba thao tác cơ bản:

• Push: Thêm một phần tử vào đỉnh của Stack.
• Pop: Lấy một phần tử từ đỉnh của Stack.
• Peek: Xem giá trị của phần tử ở đỉnh Stack mà không loại bỏ nó.

Thao Tác Push

Thao tác push thêm một phần tử mới vào đỉnh của Stack.

Trước khi thêm, cần kiểm tra xem Stack đã đầy chưa (overflow).

Nếu Stack chưa đầy, phần tử mới sẽ được thêm vào và vị trí đỉnh (top) sẽ được cập nhật.

Ví dụ, nếu chúng ta push số 5 vào một Stack rỗng, số 5 sẽ trở thành phần tử duy nhất và là đỉnh của Stack.

Thao Tác Pop

Thao tác pop loại bỏ phần tử ở đỉnh của Stack.

Trước khi loại bỏ, cần kiểm tra xem Stack có rỗng không (underflow).

Nếu Stack không rỗng, phần tử ở đỉnh sẽ được loại bỏ và vị trí đỉnh sẽ được cập nhật.

Ví dụ, nếu chúng ta pop từ Stack chứa [1, 2, 3], số 3 sẽ được loại bỏ và Stack trở thành [1, 2].

Thao Tác Peek

Thao tác peek trả về giá trị của phần tử ở đỉnh của Stack mà không loại bỏ nó.

Tương tự như pop, cần kiểm tra xem Stack có rỗng không trước khi thực hiện peek.

Nếu Stack rỗng, thao tác peek thường trả về một giá trị đặc biệt (ví dụ: null hoặc -1) để báo hiệu Stack rỗng.

Ví dụ, nếu chúng ta peek vào Stack chứa [1, 2, 3], thao tác sẽ trả về 3 mà không làm thay đổi Stack.

Ví Dụ Ứng Dụng Thực Tế

Stack có rất nhiều ứng dụng trong thực tế.

Dưới đây là một vài ví dụ điển hình:

• Trình duyệt web: Nút “back” (quay lại) trong trình duyệt web sử dụng Stack để lưu trữ lịch sử các trang web đã truy cập. Khi bạn nhấn nút “back”, trình duyệt sẽ pop trang web hiện tại ra khỏi Stack và hiển thị trang web trước đó.
• Undo/Redo trong phần mềm: Các phần mềm như Microsoft Word, Photoshop sử dụng Stack để thực hiện chức năng undo/redo. Mỗi hành động được lưu vào Stack. Undo sẽ pop hành động cuối cùng và redo sẽ push hành động đó trở lại.
• Biên dịch và thực thi chương trình: Stack được sử dụng trong quá trình biên dịch và thực thi chương trình, đặc biệt là trong việc quản lý các hàm gọi và biến cục bộ.
• Đánh giá biểu thức toán học: Stack có thể được sử dụng để đánh giá các biểu thức toán học, đặc biệt là các biểu thức ở dạng hậu tố (postfix notation).

Triển Khai Stack bằng Java

Có nhiều cách để triển khai Stack trong Java.

Chúng ta có thể sử dụng java.util.Stack class hoặc tự triển khai bằng cách sử dụng mảng hoặc danh sách liên kết.

Dưới đây là ví dụ triển khai Stack bằng mảng:

public class MyStack {
 private int[] arr;
 private int top;
 private int capacity;

 public MyStack(int size) {
 arr = new int[size];
 capacity = size;
 top = -1;
 }

 public void push(int x) {
 if (isFull()) {
 System.out.println("Overflow\nProgram Terminated\n");
 System.exit(1);
 }

 System.out.println("Inserting " + x);
 arr[++top] = x;
 }

 public int pop() {
 if (isEmpty()) {
 System.out.println("Underflow\nProgram Terminated");
 System.exit(1);
 }
 System.out.println("Removing " + peek());
 return arr[top--];
 }

 public int peek() {
 if (!isEmpty()) {
 return arr[top];
 }
 else {
 System.exit(1);
 }

 return -1; // Never reached
 }

 public int size() {
 return top + 1;
 }

 public boolean isEmpty() {
 return top == -1;
 }

 public boolean isFull() {
 return top == capacity - 1;
 }

 public static void main(String[] args) {
 MyStack stack = new MyStack(5);

 stack.push(1);
 stack.push(2);
 stack.push(3);

 System.out.println("\nTop element is " + stack.peek());

 stack.pop();
 stack.pop();
 stack.pop();

 if (stack.isEmpty()) {
 System.out.println("\nStack Is Empty");
 }
 }
}

Trong ví dụ trên, chúng ta tạo một lớp MyStack với các thuộc tính:

• arr: Mảng để lưu trữ các phần tử của Stack.
• top: Chỉ số của phần tử ở đỉnh Stack.
• capacity: Kích thước tối đa của Stack.

Chúng ta cũng triển khai các phương thức push, pop, peek, size, isEmpty và isFull để thực hiện các thao tác cơ bản của Stack.

Kết luận

Ngăn xếp (Stack) là một cấu trúc dữ liệu tuyến tính đơn giản nhưng mạnh mẽ.

Nó hoạt động dựa trên nguyên lý LIFO và có nhiều ứng dụng thực tế.

Trong bài viết này, chúng ta đã tìm hiểu về Stack, các thao tác cơ bản và cách triển khai nó bằng Java.

Hy vọng bài viết này hữu ích cho bạn.

Hãy tiếp tục khám phá các cấu trúc dữ liệu và giải thuật khác để nâng cao kỹ năng lập trình của bạn!