Ngăn xếp¶
Một ngăn xếp (stack) là một cấu trúc dữ liệu tuyến tính (linear data structure) tuân theo nguyên lý Vào sau Ra trước (Last In, First Out - LIFO).
Chúng ta có thể so sánh ngăn xếp với một chồng đĩa trên bàn. Nếu chỉ cho phép di chuyển mỗi lần một chiếc đĩa, thì để lấy được chiếc đĩa ở dưới cùng, trước tiên chúng ta phải lần lượt lấy các chiếc đĩa ở phía trên nó ra. Nếu thay thế các đĩa bằng các loại phần tử khác nhau (như số nguyên, ký tự, đối tượng, v.v.), chúng ta sẽ có cấu trúc dữ liệu ngăn xếp.
Như được hiển thị trong hình bên dưới, chúng ta gọi phần đầu của các phần tử được xếp chồng lên nhau là đỉnh (top) và phần dưới cùng là đáy (bottom). Thao tác thêm một phần tử vào đỉnh được gọi là đẩy vào (push), và thao tác loại bỏ phần tử ở đỉnh được gọi là lấy ra (pop).
Các thao tác ngăn xếp thông thường¶
Các thao tác thông thường trên một ngăn xếp được hiển thị trong bảng dưới đây. Tên phương thức cụ thể phụ thuộc vào ngôn ngữ lập trình được sử dụng. Ở đây, chúng ta sử dụng quy ước đặt tên phổ biến là push(), pop() và peek().
Bảng
| Phương thức | Mô tả | Độ phức tạp thời gian |
|---|---|---|
push() |
Đẩy phần tử vào ngăn xếp (thêm vào đỉnh) | \(O(1)\) |
pop() |
Lấy phần tử đỉnh ra khỏi ngăn xếp | \(O(1)\) |
peek() |
Truy cập phần tử đỉnh | \(O(1)\) |
Thông thường, chúng ta có thể sử dụng trực tiếp lớp ngăn xếp tích hợp sẵn do ngôn ngữ lập trình cung cấp. Tuy nhiên, một số ngôn ngữ có thể không cung cấp một lớp ngăn xếp chuyên dụng. Trong những trường hợp như vậy, chúng ta có thể sử dụng mảng (array) hoặc danh sách liên kết (linked list) của ngôn ngữ đó làm ngăn xếp và chỉ cần tránh sử dụng các thao tác không liên quan đến hành vi của ngăn xếp.
# Khởi tạo ngăn xếp
# Python không có lớp ngăn xếp tích hợp sẵn, có thể dùng list làm ngăn xếp
stack: list[int] = []
# Đẩy các phần tử vào ngăn xếp
stack.append(1)
stack.append(3)
stack.append(2)
stack.append(5)
stack.append(4)
# Truy cập phần tử đỉnh
peek: int = stack[-1]
# Lấy phần tử ra khỏi ngăn xếp
pop: int = stack.pop()
# Lấy độ dài ngăn xếp
size: int = len(stack)
# Kiểm tra xem ngăn xếp có trống không
is_empty: bool = len(stack) == 0
/* Khởi tạo ngăn xếp */
stack<int> stack;
/* Đẩy các phần tử vào ngăn xếp */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);
/* Truy cập phần tử đỉnh */
int top = stack.top();
/* Lấy phần tử ra khỏi ngăn xếp */
stack.pop(); // Không trả về giá trị
/* Lấy độ dài ngăn xếp */
int size = stack.size();
/* Kiểm tra xem ngăn xếp có trống không */
bool empty = stack.empty();
/* Khởi tạo ngăn xếp */
Stack<Integer> stack = new Stack<>();
/* Đẩy các phần tử vào ngăn xếp */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);
/* Truy cập phần tử đỉnh */
int peek = stack.peek();
/* Lấy phần tử ra khỏi ngăn xếp */
int pop = stack.pop();
/* Lấy độ dài ngăn xếp */
int size = stack.size();
/* Kiểm tra xem ngăn xếp có trống không */
boolean isEmpty = stack.isEmpty();
/* Khởi tạo ngăn xếp */
Stack<int> stack = new();
/* Đẩy các phần tử vào ngăn xếp */
stack.Push(1);
stack.Push(3);
stack.Push(2);
stack.Push(5);
stack.Push(4);
/* Truy cập phần tử đỉnh */
int peek = stack.Peek();
/* Lấy phần tử ra khỏi ngăn xếp */
int pop = stack.Pop();
/* Lấy độ dài ngăn xếp */
int size = stack.Count;
/* Kiểm tra xem ngăn xếp có trống không */
bool isEmpty = stack.Count == 0;
/* Khởi tạo ngăn xếp */
// Trong Go, khuyến nghị sử dụng Slice làm ngăn xếp
var stack []int
/* Đẩy các phần tử vào ngăn xếp */
stack = append(stack, 1)
stack = append(stack, 3)
stack = append(stack, 2)
stack = append(stack, 5)
stack = append(stack, 4)
/* Truy cập phần tử đỉnh */
peek := stack[len(stack)-1]
/* Lấy phần tử ra khỏi ngăn xếp */
pop := stack[len(stack)-1]
stack = stack[:len(stack)-1]
/* Lấy độ dài ngăn xếp */
size := len(stack)
/* Kiểm tra xem ngăn xếp có trống không */
isEmpty := len(stack) == 0
/* Khởi tạo ngăn xếp */
// Swift không có lớp ngăn xếp tích hợp sẵn, có thể dùng Array làm ngăn xếp
var stack: [Int] = []
/* Đẩy các phần tử vào ngăn xếp */
stack.append(1)
stack.append(3)
stack.append(2)
stack.append(5)
stack.append(4)
/* Truy cập phần tử đỉnh */
let peek = stack.last!
/* Lấy phần tử ra khỏi ngăn xếp */
let pop = stack.removeLast()
/* Lấy độ dài ngăn xếp */
let size = stack.count
/* Kiểm tra xem ngăn xếp có trống không */
let isEmpty = stack.isEmpty
/* Khởi tạo ngăn xếp */
// JavaScript không có lớp ngăn xếp tích hợp sẵn, có thể dùng Array làm ngăn xếp
const stack = [];
/* Đẩy các phần tử vào ngăn xếp */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);
/* Truy cập phần tử đỉnh */
const peek = stack[stack.length-1];
/* Lấy phần tử ra khỏi ngăn xếp */
const pop = stack.pop();
/* Lấy độ dài ngăn xếp */
const size = stack.length;
/* Kiểm tra xem ngăn xếp có trống không */
const is_empty = stack.length === 0;
/* Khởi tạo ngăn xếp */
// TypeScript không có lớp ngăn xếp tích hợp sẵn, có thể dùng Array làm ngăn xếp
const stack: number[] = [];
/* Đẩy các phần tử vào ngăn xếp */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);
/* Truy cập phần tử đỉnh */
const peek = stack[stack.length - 1];
/* Lấy phần tử ra khỏi ngăn xếp */
const pop = stack.pop();
/* Lấy độ dài ngăn xếp */
const size = stack.length;
/* Kiểm tra xem ngăn xếp có trống không */
const is_empty = stack.length === 0;
/* Khởi tạo ngăn xếp */
// Dart không có lớp ngăn xếp tích hợp sẵn, có thể dùng List làm ngăn xếp
List<int> stack = [];
/* Đẩy các phần tử vào ngăn xếp */
stack.add(1);
stack.add(3);
stack.add(2);
stack.add(5);
stack.add(4);
/* Truy cập phần tử đỉnh */
int peek = stack.last;
/* Lấy phần tử ra khỏi ngăn xếp */
int pop = stack.removeLast();
/* Lấy độ dài ngăn xếp */
int size = stack.length;
/* Kiểm tra xem ngăn xếp có trống không */
bool isEmpty = stack.isEmpty;
/* Khởi tạo ngăn xếp */
// Sử dụng Vec làm ngăn xếp
let mut stack: Vec<i32> = Vec::new();
/* Đẩy các phần tử vào ngăn xếp */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);
/* Truy cập phần tử đỉnh */
let top = stack.last().unwrap();
/* Lấy phần tử ra khỏi ngăn xếp */
let pop = stack.pop().unwrap();
/* Lấy độ dài ngăn xếp */
let size = stack.len();
/* Kiểm tra xem ngăn xếp có trống không */
let is_empty = stack.is_empty();
/* Khởi tạo ngăn xếp */
val stack = Stack<Int>()
/* Đẩy các phần tử vào ngăn xếp */
stack.push(1)
stack.push(3)
stack.push(2)
stack.push(5)
stack.push(4)
/* Truy cập phần tử đỉnh */
val peek = stack.peek()
/* Lấy phần tử ra khỏi ngăn xếp */
val pop = stack.pop()
/* Lấy độ dài ngăn xếp */
val size = stack.size
/* Kiểm tra xem ngăn xếp có trống không */
val isEmpty = stack.isEmpty()
# Khởi tạo ngăn xếp
# Ruby không có lớp ngăn xếp tích hợp sẵn, có thể dùng Array làm ngăn xếp
stack = []
# Đẩy các phần tử vào ngăn xếp
stack << 1
stack << 3
stack << 2
stack << 5
stack << 4
# Truy cập phần tử đỉnh
peek = stack.last
# Lấy phần tử ra khỏi ngăn xếp
pop = stack.pop
# Lấy độ dài ngăn xếp
size = stack.length
# Kiểm tra xem ngăn xếp có trống không
is_empty = stack.empty?
Trực quan hóa mã nguồn
https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E6%A0%88%0A%20%20%20%20%23%20Python%20%E6%B2%A1%E6%9C%89%E5%86%85%E7%BD%AE%E7%9A%84%E6%A0%88%E7%B1%BB%EF%BC%8C%E5%8F%AF%E4%BB%A5%E6%8A%8A%20list%20%E5%BD%93%E4%BD%9C%E6%A0%88%E6%9D%A5%E4%BD%BF%E7%94%A8%0A%20%20%20%20stack%20%3D%20%5B%5D%0A%0A%20%20%20%20%23%20%E5%85%83%E7%B4%A0%E5%85%A5%E6%A0%88%0A%20%20%20%20stack.append%281%29%0A%20%20%20%20stack.append%283%29%0A%20%20%20%20stack.append%282%29%0A%20%20%20%20stack.append%285%29%0A%20%20%20%20stack.append%284%29%0A%20%20%20%20print%28%22%E6%A0%88%20stack%20%3D%22,%20stack%29%0A%0A%20%20%20%20%23%20%E8%AE%BF%E9%97%AE%E6%A0%88%E9%A1%B6%E5%85%83%E7%B4%A0%0A%20%20%20%20peek%20%3D%20stack%5B-1%5D%0A%20%20%20%20print%28%22%E6%A0%88%E9%A1%B6%E5%85%83%E7%B4%A0%20peek%20%3D%22,%20peek%29%0A%0A%20%20%20%20%23%20%E5%85%83%E7%B4%A0%E5%87%BA%E6%A0%88%0A%20%20%20%20pop%20%3D%20stack.pop%28%29%0A%20%20%20%20print%28%22%E5%87%BA%E6%A0%88%E5%85%83%E7%B4%A0%20pop%20%3D%22,%20pop%29%0A%20%20%20%20print%28%22%E5%87%BA%E6%A0%88%E5%90%8E%20stack%20%3D%22,%20stack%29%0A%0A%20%20%20%20%23%20%E8%8E%B7%E5%8F%96%E6%A0%88%E7%9A%84%E9%95%BF%E5%BA%A6%0A%20%20%20%20size%20%3D%20len%28stack%29%0A%20%20%20%20print%28%22%E6%A0%88%E7%9A%84%E9%95%BF%E5%BA%A6%20size%20%3D%22,%20size%29%0A%0A%20%20%20%20%23%20%E5%88%A4%E6%96%AD%E6%98%AF%E5%90%A6%E4%B8%BA%E7%A9%BA%0A%20%20%20%20is_empty%20%3D%20len%28stack%29%20%3D%3D%200%0A%20%20%20%20print%28%22%E6%A0%88%E6%98%AF%E5%90%A6%E4%B8%BA%E7%A9%BA%20%3D%22,%20is_empty%29&cumulative=false&curInstr=2&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false
Triển khai Ngăn xếp¶
Để hiểu sâu hơn về cách hoạt động của ngăn xếp, hãy tự thử triển khai một lớp ngăn xếp.
Ngăn xếp tuân theo nguyên lý LIFO, vì vậy chúng ta chỉ có thể thêm hoặc loại bỏ các phần tử ở đỉnh. Tuy nhiên, cả mảng và danh sách liên kết đều cho phép thêm và loại bỏ phần tử ở bất kỳ vị trí nào. Do đó, ngăn xếp có thể được coi là một mảng hoặc danh sách liên kết bị giới hạn. Nói cách khác, chúng ta có thể "che giấu" một số thao tác không liên quan của mảng hoặc danh sách liên kết để logic bên ngoài của chúng tuân thủ các đặc tính của ngăn xếp.
Triển khai bằng Danh sách liên kết¶
Khi triển khai ngăn xếp bằng danh sách liên kết, chúng ta có thể coi nút đầu (head node) của danh sách liên kết là đỉnh ngăn xếp và nút đuôi (tail node) là đáy ngăn xếp.
Như được hiển thị trong hình dưới đây, đối với thao tác đẩy vào (push), chúng ta chỉ cần chèn một phần tử vào đầu danh sách liên kết. Phương pháp chèn nút này được gọi là phương pháp chèn đầu (head insertion method). Đối với thao tác lấy ra (pop), chúng ta chỉ cần loại bỏ nút đầu ra khỏi danh sách liên kết.
Dưới đây là mã nguồn ví dụ để triển khai một ngăn xếp dựa trên danh sách liên kết:
Triển khai bằng Mảng¶
Khi triển khai ngăn xếp bằng mảng, chúng ta có thể coi cuối mảng là đỉnh ngăn xếp. Như được hiển thị trong hình dưới đây, các thao tác đẩy vào và lấy ra tương ứng với việc thêm và loại bỏ các phần tử ở cuối mảng, cả hai đều có độ phức tạp thời gian là \(O(1)\).
Vì các phần tử được đẩy vào ngăn xếp có thể tăng lên liên tục, chúng ta có thể sử dụng một mảng động (dynamic array), giúp loại bỏ việc phải tự xử lý mở rộng mảng. Dưới đây là mã nguồn ví dụ:
So sánh hai cách triển khai¶
Các thao tác được hỗ trợ
Cả hai cách triển khai đều hỗ trợ tất cả các thao tác được định nghĩa bởi ngăn xếp. Cách triển khai bằng mảng hỗ trợ thêm truy cập ngẫu nhiên, nhưng điều này vượt ra ngoài định nghĩa của ngăn xếp và thường không được sử dụng.
Hiệu suất thời gian
Trong cách triển khai bằng mảng, cả thao tác đẩy vào và lấy ra đều diễn ra trong bộ nhớ liên tục được cấp phát trước, vốn có tính cục bộ bộ nhớ đệm (cache locality) tốt và do đó hiệu quả hơn. Tuy nhiên, nếu thao tác đẩy vào vượt quá dung lượng mảng, nó sẽ kích hoạt cơ chế mở rộng, khiến độ phức tạp thời gian của thao tác đẩy vào cụ thể đó trở thành \(O(n)\).
Trong cách triển khai bằng danh sách liên kết, việc mở rộng danh sách rất linh hoạt và không có vấn đề giảm hiệu suất do mở rộng mảng. Tuy nhiên, thao tác đẩy vào yêu cầu khởi tạo một đối tượng nút và sửa đổi các con trỏ, vì vậy hiệu suất tương đối thấp hơn. Mặc dù vậy, nếu các phần tử được đẩy vào đã là các đối tượng nút, bước khởi tạo có thể được bỏ qua, từ đó cải thiện hiệu suất.
Tóm lại, khi các phần tử được đẩy vào và lấy ra là các kiểu dữ liệu cơ bản như int hoặc double, chúng ta có thể rút ra các kết luận sau:
- Triển khai ngăn xếp bằng mảng có hiệu suất giảm khi kích hoạt mở rộng, nhưng vì mở rộng là một thao tác không thường xuyên, nên hiệu suất trung bình vẫn cao hơn.
- Triển khai ngăn xếp bằng danh sách liên kết có thể cung cấp hiệu suất ổn định hơn.
Hiệu suất không gian
Khi khởi tạo một danh sách, hệ thống sẽ cấp phát một "dung lượng ban đầu" có thể vượt quá nhu cầu thực tế. Ngoài ra, cơ chế mở rộng thường mở rộng theo một tỷ lệ nhất định (ví dụ: gấp đôi), và dung lượng sau khi mở rộng cũng có thể vượt quá nhu cầu thực tế. Do đó, triển khai ngăn xếp bằng mảng có thể gây ra một số lãng phí không gian.
Tuy nhiên, vì các nút danh sách liên kết cần lưu trữ thêm các con trỏ, nên không gian bị chiếm dụng bởi các nút danh sách liên kết tương đối lớn.
Tóm lại, chúng ta không thể đơn giản xác định cách triển khai nào tiết kiệm bộ nhớ hơn mà cần phân tích tình huống cụ thể.
Các ứng dụng điển hình của Ngăn xếp¶
- Quay lại và tiếp tục trong trình duyệt, hoàn tác và làm lại trong phần mềm. Mỗi khi chúng ta mở một trang web mới, trình duyệt sẽ đẩy trang web trước đó vào ngăn xếp, cho phép chúng ta quay lại trang trước thông qua thao tác quay lại (back). Thao tác quay lại thực chất là thực hiện một thao tác lấy ra (pop). Để hỗ trợ cả quay lại và tiếp tục (forward), cần có hai ngăn xếp phối hợp hoạt động cùng nhau.
- Quản lý bộ nhớ chương trình. Mỗi khi một hàm được gọi, hệ thống sẽ thêm một khung ngăn xếp (stack frame) vào đỉnh ngăn xếp để ghi lại thông tin ngữ cảnh của hàm. Trong quá trình đệ quy, giai đoạn gọi đệ quy đi xuống liên tục thực hiện các thao tác đẩy vào, trong khi giai đoạn quay lui đi lên liên tục thực hiện các thao tác lấy ra.