Vậy Stack là gì, hoạt động như thế nào và được ứng dụng ra sao trong lập trình? Hãy cùng tìm hiểu qua nội dung dưới đây.
1. Stack là gì?
Stack (ngăn xếp) là một cấu trúc dữ liệu tuyến tính, trong đó các phần tử được thêm vào và lấy ra theo nguyên tắc LIFO (Last In, First Out), nghĩa là phần tử được đưa vào sau cùng sẽ được lấy ra đầu tiên.
Bạn có thể hình dung Stack giống như một chồng đĩa: khi đặt đĩa mới lên trên, bạn phải lấy chiếc đĩa trên cùng ra trước nếu muốn lấy những chiếc bên dưới.
Trong Stack, các thao tác thêm và lấy phần tử thường được thực hiện tại cùng một đầu gọi là Top.
<AsyncImage query="stack data structure LIFO push pop diagram clean educational illustration"aspectRatio="16:9" width="100%" />
2. Cấu trúc và nguyên lý hoạt động của Stack
Stack hoạt động dựa trên nguyên tắc LIFO. Cấu trúc này thường có hai thành phần chính:
Các thao tác cơ bản gồm:
2.1. Push – Thêm phần tử
Push là thao tác đưa một phần tử mới vào đỉnh Stack.
Ví dụ, lần lượt thêm các phần tử A, B và C:
Push(A)
Push(B)
Push(C)
Sau khi thực hiện, phần tử C nằm trên cùng và là phần tử được lấy ra đầu tiên.
2.2. Pop – Lấy phần tử
Pop là thao tác loại bỏ và lấy giá trị của phần tử nằm trên đỉnh Stack.
Ví dụ:
Pop() → C
Pop() → B
Pop() → A
Các phần tử được lấy ra theo thứ tự ngược với thứ tự thêm vào.
2.3. Peek hoặc Top – Xem phần tử trên cùng
Thao tác Peek cho phép xem giá trị phần tử trên đỉnh Stack mà không loại bỏ phần tử đó.
Ví dụ, nếu Stack chứa A, B, C thì Peek() trả về C nhưng Stack vẫn giữ nguyên.
2.4. IsEmpty – Kiểm tra Stack rỗng
Thao tác này kiểm tra Stack có phần tử nào hay không. Nếu không có dữ liệu, kết quả trả về là đúng.
2.5. IsFull – Kiểm tra Stack đầy
Đối với Stack được triển khai bằng mảng có kích thước cố định, IsFull dùng để kiểm tra xem cấu trúc đã đạt giới hạn lưu trữ hay chưa.
3. Ví dụ minh họa cách Stack hoạt động
Giả sử một Stack ban đầu chưa có dữ liệu. Chúng ta lần lượt thực hiện các thao tác:
|
Thao tác |
Nội dung Stack (từ đáy lên đỉnh) |
|
Push(10) |
10 |
|
Push(20) |
10, 20 |
|
Push(30) |
10, 20, 30 |
|
Pop() |
10, 20 |
|
Push(40) |
10, 20, 40 |
|
Pop() |
10, 20 |
Qua ví dụ trên, có thể thấy phần tử được thêm vào sau cùng luôn nằm trên đỉnh và được lấy ra trước.
4. Cách triển khai Stack trong lập trình
Stack có thể được xây dựng bằng nhiều phương pháp khác nhau. Hai cách phổ biến là sử dụng mảng (Array) hoặc danh sách liên kết (Linked List).
4.1. Triển khai Stack bằng mảng
Với phương pháp này, các phần tử được lưu trong một mảng và sử dụng biến top để quản lý vị trí phần tử trên cùng.
Ví dụ bằng C#:
using System;
class StackExample
{
static void Main()
{
Stack<int> stack = new Stack<int>();
stack.Push(10);
stack.Push(20);
stack.Push(30);
Console.WriteLine(stack.Peek());
Console.WriteLine(stack.Pop());
Console.WriteLine(stack.Pop());
}
}
Kết quả:
30
30
20
Trong ví dụ trên, chương trình sử dụng lớp Stack<T> thuộc namespace System.Collections.Generic để quản lý dữ liệu theo nguyên tắc LIFO.
4.2. Triển khai Stack bằng danh sách liên kết
Stack cũng có thể được xây dựng bằng Linked List. Mỗi phần tử là một node chứa dữ liệu và liên kết đến node tiếp theo.
Khi thêm phần tử, node mới được đặt ở đầu danh sách. Khi lấy phần tử, node đầu tiên sẽ được loại bỏ.
Ưu điểm của phương pháp này là có thể mở rộng kích thước linh hoạt, không cần xác định trước số lượng phần tử như mảng cố định.
5. Độ phức tạp của các thao tác trong Stack
Các thao tác cơ bản của Stack thường có độ phức tạp như sau:
|
Thao tác |
Độ phức tạp |
|
Push |
O(1) |
|
Pop |
O(1) |
|
Peek |
O(1) |
|
IsEmpty |
O(1) |
|
Tìm kiếm phần tử |
O(n) |
Trong đó:
Độ phức tạp trên áp dụng cho các thao tác Stack thông thường. Riêng khi triển khai bằng mảng động, thao tác Push có thể cần mở rộng mảng và mất O(n) trong một lần thực hiện, nhưng độ phức tạp trung bình vẫn là O(1).
6. Ứng dụng thực tế của Stack
Stack được sử dụng trong nhiều lĩnh vực của khoa học máy tính và phát triển phần mềm.
6.1. Quản lý lời gọi hàm
Khi một hàm gọi hàm khác, hệ thống sử dụng Call Stack để lưu thông tin về các lời gọi hàm, biến cục bộ và vị trí cần tiếp tục thực thi.
Khi hàm được gọi sau cùng hoàn thành, chương trình quay lại hàm đã gọi nó trước đó.
6.2. Chức năng Undo và Redo
Các phần mềm soạn thảo văn bản, thiết kế đồ họa và chỉnh sửa hình ảnh thường sử dụng Stack để quản lý lịch sử thao tác.
Khi người dùng thực hiện Undo, thao tác gần nhất sẽ được lấy ra trước. Điều này phù hợp với nguyên tắc LIFO.
6.3. Kiểm tra dấu ngoặc trong biểu thức
Stack thường được sử dụng để kiểm tra tính hợp lệ của các cặp dấu ngoặc trong biểu thức toán học hoặc mã nguồn.
Ví dụ:
((A + B) * C)
Chương trình đưa dấu ngoặc mở vào Stack và lấy chúng ra khi gặp dấu ngoặc đóng tương ứng.
6.4. Thuật toán duyệt đồ thị và cây
Stack được sử dụng trong thuật toán DFS (Depth-First Search) để duyệt sâu các đỉnh của đồ thị hoặc các node trong cây.
Thuật toán có thể sử dụng Stack trực tiếp hoặc thông qua cơ chế đệ quy.
6.5. Đảo ngược dữ liệu
Do đặc điểm vào sau ra trước, Stack có thể hỗ trợ đảo ngược chuỗi ký tự, danh sách hoặc một tập hợp dữ liệu.
Ví dụ, khi đưa các ký tự A, B, C vào Stack và lấy lần lượt ra, kết quả thu được là C, B, A.
7. Ưu điểm và nhược điểm của Stack
Ưu điểm:
Nhược điểm:
-
Stack dùng mảng kích thước cố định có giới hạn dung lượng.
Trong đó, Stack Overflow xảy ra khi ngăn xếp vượt quá giới hạn bộ nhớ cho phép, còn Stack Underflow xảy ra khi thực hiện thao tác lấy phần tử trong lúc Stack đang rỗng.
8. Phân biệt Stack và Queue
Stack và Queue đều là cấu trúc dữ liệu tuyến tính nhưng có nguyên tắc hoạt động khác nhau.
|
Tiêu chí |
Stack |
Queue |
|
Nguyên tắc |
LIFO |
FIFO |
|
Thêm phần tử |
Tại đỉnh Stack |
Ở cuối hàng đợi |
|
Lấy phần tử |
Tại đỉnh Stack |
Ở đầu hàng đợi |
|
Ví dụ |
Chồng đĩa |
Hàng người chờ thanh toán |
|
Ứng dụng |
Undo, DFS, Call Stack |
Xử lý tác vụ, hàng đợi yêu cầu |