Stack
June 24, 2025
04:33 AM
No headings found
Loading content...
Related Posts
Theory Data Structure And Algorithms
No headings found
Related Posts
Theory Data Structure And Algorithms
| Tiêu chí | Array (Mảng) | Linked List (Danh sách liên kết) |
| Cấu trúc lưu trữ | Các phần tử lưu liên tục trong bộ nhớ, truy cập qua chỉ số (index) | Mỗi phần tử (node) chứa dữ liệu và con trỏ đến phần tử kế tiếp |
| Kích thước | Cố định khi khai báo (hoặc phải mở rộng thủ công nếu cần) | Linh hoạt, tự động tăng/giảm khi thêm/xóa phần tử |
| Truy cập phần tử | Truy cập trực tiếp (O(1)) qua chỉ số | Truy cập tuần tự (O(n)), phải duyệt từ đầu đến node cần tìm |
| Thêm/Xóa phần tử | Thêm/xóa ở cuối hiệu quả (O(1)), ở giữa/cuối cần dịch chuyển phần tử (O(n)) | Thêm/xóa ở đầu hoặc giữa đều O(1) nếu có con trỏ, không cần dịch chuyển |
| Hiệu quả bộ nhớ | Tiết kiệm bộ nhớ hơn, không cần lưu con trỏ | Tốn thêm bộ nhớ cho con trỏ (pointer) ở mỗi node |
| Tính cục bộ bộ nhớ | Tốt hơn, dễ tận dụng cache CPU | Kém hơn do các node nằm rải rác trong bộ nhớ |
| Cài đặt | Đơn giản hơn, dễ dùng | Phức tạp hơn, phải quản lý con trỏ |
| Stack Overflow | Có thể bị nếu vượt quá kích thước mảng đã khai báo | Không bị giới hạn kích thước (chỉ phụ thuộc vào bộ nhớ hệ thống) |
Solution - Array
1export default class Stack<T> {
2 _items: Array<T>;
3 constructor() {
4 this._items = [];
5 }
6
7 /**
8 * Pushes an item onto the top of the stack.
9 */
10 push(item: T): number {
11 return this._items.push(item);
12 }
13
14 /**
15 * Remove an item at the top of the stack.
16 */
17 pop(): T | undefined {
18 return this._items.pop();
19 }
20
21 /**
22 * Determines if the stack is empty.
23 */
24 isEmpty(): boolean {
25 return this._items.length === 0;
26 }
27
28 /**
29 * Returns the item at the top of the stack without removing it from the stack.
30 */
31 peek(): T | undefined {
32 return this._items.at(-1);
33 }
34
35 /**
36 * Returns the number of items in the stack.
37 */
38 length(): number {
39 return this._items.length;
40 }
41}
42Solution - Linked List
1class Node<T> {
2 value: T;
3 next: Node<T> | null;
4 constructor(value: T) {
5 this.value = value;
6 this.next = null;
7 }
8}
9
10export default class Stack<T> {
11 head: Node<T> | null;
12 _size: number;
13 constructor() {
14 this.head = null;
15 this._size = 0;
16 }
17
18 /**
19 * Pushes an item onto the top of the stack.
20 */
21 push(item: T): number {
22 const node = new Node(item);
23 node.next = this.head;
24 this.head = node;
25 this._size++;
26 return this._size;
27 }
28
29 /**
30 * Remove an item at the top of the stack.
31 */
32 pop(): T | undefined {
33 if (this.isEmpty()) return undefined;
34 const node = this.head!;
35 this.head = node.next;
36 this._size--;
37 return node.value;
38 }
39
40 /**
41 * Determines if the stack is empty.
42 */
43 isEmpty(): boolean {
44 return this._size === 0;
45 }
46
47 /**
48 * Returns the item at the top of the stack without removing it from the stack.
49 */
50 peek(): T | undefined {
51 return this.head?.value;
52 }
53
54 /**
55 * Returns the number of items in the stack.
56 */
57 length(): number {
58 return this._size;
59 }
60}
61