Ngăn xếp (Stack)

Stack là gì?

Stack là cấu trúc dữ liệu hoạt động theo nguyên tắc LIFO (Last In, First Out) - phần tử vào sau cùng sẽ được lấy ra đầu tiên.


      ┌─────┐
      │  30 │ ← Top (đỉnh)
      ├─────┤
      │  20 │
      ├─────┤
      │  10 │ ← Bottom (đáy)
      └─────┘

💡

Stack giống như chồng đĩa - bạn chỉ có thể lấy đĩa trên cùng!

Các thao tác cơ bản

Thao tác	Mô tả	Độ phức tạp
`push(x)`	Thêm x vào đỉnh	O(1)
`pop()`	Lấy và xóa phần tử đỉnh	O(1)
`peek()`/`top()`	Xem phần tử đỉnh	O(1)
`isEmpty()`	Kiểm tra stack rỗng	O(1)

Sử dụng Stack

Python


from collections import deque
 
# Dùng deque (khuyên dùng)
stack = deque()
stack.append(10)    # push
stack.append(20)
stack.append(30)
 
print(stack[-1])    # peek: 30
print(stack.pop())  # pop: 30
print(len(stack))   # size: 2

Kotlin


// Dùng ArrayDeque
val stack = ArrayDeque<Int>()
stack.addLast(10)   // push
stack.addLast(20)
stack.addLast(30)
 
println(stack.last())     // peek: 30
println(stack.removeLast()) // pop: 30
println(stack.size)       // size: 2

Dart


// Dùng List
List<int> stack = [];
stack.add(10);      // push
stack.add(20);
stack.add(30);
 
print(stack.last);        // peek: 30
print(stack.removeLast()); // pop: 30
print(stack.length);      // size: 2

Swift


// Dùng Array
var stack = [Int]()
stack.append(10)    // push
stack.append(20)
stack.append(30)
 
print(stack.last!)       // peek: 30
print(stack.popLast()!)  // pop: 30
print(stack.count)       // size: 2

Java


// Dùng ArrayDeque (khuyên dùng thay Stack)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);     // push
stack.push(20);
stack.push(30);
 
System.out.println(stack.peek()); // peek: 30
System.out.println(stack.pop());  // pop: 30
System.out.println(stack.size()); // size: 2

Kiểm tra ngoặc hợp lệ

Python


def is_valid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:
            if not stack or stack.pop() != mapping[char]:
                return False
        else:
            stack.append(char)
    
    return len(stack) == 0
 
print(is_valid("()[]{}"))  # True
print(is_valid("([)]"))    # False

Kotlin


fun isValid(s: String): Boolean {
    val stack = ArrayDeque<Char>()
    val mapping = mapOf(')' to '(', '}' to '{', ']' to '[')
    
    for (char in s) {
        if (char in mapping) {
            if (stack.isEmpty() || stack.removeLast() != mapping[char])
                return false
        } else {
            stack.addLast(char)
        }
    }
    return stack.isEmpty()
}

Dart


bool isValid(String s) {
  List<String> stack = [];
  Map<String, String> mapping = {')': '(', '}': '{', ']': '['};
  
  for (var char in s.split('')) {
    if (mapping.containsKey(char)) {
      if (stack.isEmpty || stack.removeLast() != mapping[char])
        return false;
    } else {
      stack.add(char);
    }
  }
  return stack.isEmpty;
}

Swift


func isValid(_ s: String) -> Bool {
    var stack = [Character]()
    let mapping: [Character: Character] = [")": "(", "}": "{", "]": "["]
    
    for char in s {
        if let match = mapping[char] {
            if stack.isEmpty || stack.popLast() != match {
                return false
            }
        } else {
            stack.append(char)
        }
    }
    return stack.isEmpty
}

Java


boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> mapping = Map.of(')', '(', '}', '{', ']', '[');
    
    for (char c : s.toCharArray()) {
        if (mapping.containsKey(c)) {
            if (stack.isEmpty() || stack.pop() != mapping.get(c))
                return false;
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

Ứng dụng thực tế

Ứng dụng	Mô tả
Undo/Redo	Lưu trạng thái để hoàn tác
Browser back	Lịch sử trang đã xem
Call Stack	Quản lý lời gọi hàm
Expression eval	Tính toán biểu thức

⚠️

Luôn kiểm tra stack có rỗng không trước khi pop() hoặc peek() để tránh lỗi!

Tiếp theo: Hàng đợi (Queue)