Viễn Đinh

Viễn Đinh

Khá Hơn 0,5% Mỗi Ngày

Cách Giải Ngăn Xếp (Stack), Dể Hiểu

Bạn có biết rằng nhiều cấu trúc dữ liệu được lấy cảm hứng từ cách con người tổ chức công việc hàng ngày? Ngăn xếp (Stack) là một ví dụ tiêu biểu. Hãy tưởng tượng bạn có một chồng sách: sách nào được đặt lên cuối cùng thì sẽ được lấy ra đầu tiên. Đây chính là nguyên lý cơ bản của Stack, hay còn gọi là nguyên tắc “vào sau, ra trước”.

Định Nghĩa

Ngăn xếp là một cấu trúc dữ liệu hoạt động theo nguyên tắc LIFO (Last In, First Out), nghĩa là phần tử cuối cùng được thêm vào sẽ là phần tử đầu tiên được lấy ra. Nếu bạn hình dung ngăn xếp như một chồng đĩa, thì khi cần lấy đĩa ra, bạn sẽ lấy đĩa ở trên cùng trước. Các phần tử lần lượt được thêm và xóa từ một đầu, gọi là “đỉnh” của ngăn xếp.

Stack có thể giúp chúng ta quản lý các tác vụ một cách logic và có thứ tự. Khi một tác vụ mới xuất hiện, nó sẽ được đẩy vào đầu ngăn xếp; khi hoàn thành, nó sẽ được lấy ra từ đó. Điều này rất hữu ích trong các chương trình máy tính khi cần quản lý các tác vụ theo trình tự cụ thể.

Stack thường chỉ cung cấp một số thao tác cơ bản, cho phép thêm phần tử vào “đỉnh” (push) và lấy phần tử ra khỏi “đỉnh” (pop). Đặc tính này giúp Stack trở nên rất hiệu quả trong các tình huống yêu cầu truy cập theo thứ tự cụ thể.

Khi hiểu được cách hoạt động của ngăn xếp, bạn sẽ thấy cấu trúc này đơn giản nhưng cực kỳ mạnh mẽ, có khả năng giải quyết nhiều bài toán khác nhau trong lập trình.

Cách Giải

Cấu trúc dữ liệu ngăn xếp hoạt động trên nguyên tắc LIFO (Last In, First Out); vào sau, ra trước. Sau đây là các phương thức của nó:

Bạn thấy đó, các phương thức này đơn giản nhưng đáp ứng mọi yêu cầu cần thiết cho một ngăn xếp. Chúng giúp chúng ta quản lý dữ liệu theo thứ tự chặt chẽ, phù hợp cho các tình huống yêu cầu tính nhất quán trong thứ tự xử lý.

Triển Khai bằng Array

Lý do nên triển khai ngăn xếp bằng mảng:

Lý do không nên sử dụng mảng để triển khai ngăn xếp:

Mã TypeScript sẽ trông như sau:

class Stack<T> {
  private items: T[] = [];

  // Thêm phần tử mới vào đầu ngăn xếp
  push(element: T): void {
    this.items.push(element);
  }

  // Xóa và trả về phần tử ở đầu ngăn xếp
  pop(): T | undefined {
    return this.items.pop();
  }

  // Trả về phần tử trên cùng của ngăn xếp mà không xóa
  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }

  // Kiểm tra xem ngăn xếp có rỗng không
  isEmpty(): boolean {
    return this.items.length === 0;
  }

  // Tìm số lượng phần tử trong ngăn xếp
  size(): number {
    return this.items.length;
  }
}

Triển Khai bằng Linked List

Lý do nên sử dụng danh sách liên kết để triển khai ngăn xếp:

Lý do không nên sử dụng danh sách liên kết để triển khai ngăn xếp:

Mã TypeScript sẽ trông như sau:

class Node<T> {
  constructor(
    public value: T,
    public next: Node<T> | null = null
  ) {}
}

class Stack<T> {
  private head: Node<T> | null = null;
  private count: number = 0;

  // Thêm phần tử mới vào đầu ngăn xếp
  push(element: T): void {
    const newNode = new Node(element, this.head);
    this.head = newNode;
    this.count++;
  }

  // Xóa và trả về phần tử ở đầu ngăn xếp
  pop(): T | undefined {
    if (!this.head) return undefined;
    const value = this.head.value;
    this.head = this.head.next;
    this.count--;
    return value;
  }

  // Trả về phần tử trên cùng của ngăn xếp mà không xóa
  peek(): T | undefined {
    return this.head ? this.head.value : undefined;
  }

  // Kiểm tra xem ngăn xếp có rỗng không
  isEmpty(): boolean {
    return this.count === 0;
  }

  // Tìm số lượng phần tử trong ngăn xếp
  size(): number {
    return this.count;
  }
}

Toàn Cảnh

Ngăn xếp không tồn tại riêng lẻ mà thường là một phần của hệ thống lớn hơn. Ví dụ, trong các ngôn ngữ lập trình, stack là một phần của bộ nhớ máy tính để lưu trữ thông tin về các hàm và biến cục bộ. Khi một hàm được gọi, thông tin của nó sẽ được đẩy vào ngăn xếp; khi hàm hoàn thành, thông tin sẽ được lấy ra.

Stack cũng được dùng trong các hệ thống điều khiển luồng, nơi các lệnh cần được thực thi theo thứ tự nhất định. Điều này giúp chương trình duy trì trạng thái nhất quán và dễ dàng quản lý các lệnh gọi đệ quy hoặc vòng lặp phức tạp.

Ngoài ra, ngăn xếp đóng vai trò quan trọng trong thuật toán tìm kiếm và phân loại, chẳng hạn như trong thuật toán tìm đường đi trong đồ thị hoặc sắp xếp ngăn xếp. Các thuật toán này dựa vào nguyên tắc LIFO để đảm bảo các bước được thực hiện theo thứ tự hợp lý.

Trong lập trình, Stack không chỉ là công cụ lưu trữ mà còn là công cụ tư duy, giúp bạn tổ chức ý tưởng theo trình tự và dễ dàng xử lý các vấn đề đòi hỏi tính chất LIFO.

Ứng Dụng

Ngăn xếp có thể được sử dụng để quản lý lịch sử duyệt web. Mỗi khi bạn mở một trang mới, trang đó sẽ được đẩy vào ngăn xếp. Khi bạn nhấn nút “quay lại”, trang đó sẽ được lấy ra khỏi đầu ngăn xếp, đưa bạn trở lại trang trước đó.

Stack cũng là công cụ quan trọng trong xử lý chuỗi ký tự, đặc biệt khi kiểm tra tính đối xứng hoặc tính hợp lệ của các ký tự như ngoặc đơn hoặc ngoặc kép trong một biểu thức. Điều này giúp tránh lỗi cú pháp trong các chương trình phức tạp.

Trong phát triển trò chơi, ngăn xếp giúp quản lý trạng thái các màn chơi. Khi người chơi hoàn thành một màn, trạng thái của màn đó có thể được lưu trữ vào ngăn xếp, cho phép dễ dàng quay lại trạng thái đó nếu cần.

Ngoài ra, ngăn xếp còn được ứng dụng trong các thuật toán đồ thị như thuật toán tìm kiếm theo chiều sâu (DFS), một công cụ quan trọng trong việc phân tích và tối ưu hóa mạng lưới hoặc hệ thống.

Hiểu Lầm

Một hiểu lầm phổ biến là ngăn xếp có thể truy cập ngẫu nhiên các phần tử như mảng. Nhưng thực tế là Stack chỉ cho phép truy cập phần tử ở đầu. Điều này là hạn chế nếu bạn muốn truy cập phần tử giữa.

Một số người mới học có thể cho rằng ngăn xếp có thể dễ dàng thay thế bằng mảng. Tuy nhiên, mỗi cấu trúc dữ liệu có vai trò riêng, và ngăn xếp được thiết kế đặc thù cho các tác vụ cần tính chất LIFO, trong khi mảng không có giới hạn như vậy.

Một nhầm lẫn khác là ngăn xếp chỉ hữu ích cho các thuật toán đơn giản. Trên thực tế, ngăn xếp là cơ sở của nhiều thuật toán và hệ thống phức tạp trong máy tính.

Ngăn xếp cũng bị hiểu sai là một cấu trúc dữ liệu “cứng nhắc” vì nó chỉ có hai thao tác chính là push và pop. Nhưng chính tính đơn giản này lại giúp nó trở thành một công cụ mạnh mẽ và linh hoạt khi ứng dụng đúng chỗ.

Tóm Tắt

Ngăn xếp là cấu trúc dữ liệu dựa trên nguyên tắc LIFO, với các thao tác đơn giản nhưng mạnh mẽ như push, pop, peek, isEmpty và size, giúp duy trì thứ tự chặt chẽ trong việc quản lý dữ liệu.

Sử dụng mảng hoặc danh sách liên kết, bạn có thể triển khai ngăn xếp dễ dàng trong nhiều ngôn ngữ lập trình như TypeScript, phù hợp cho cả tác vụ đơn giản và phức tạp.

Stack có mặt trong nhiều ứng dụng từ quản lý bộ nhớ, điều khiển luồng lệnh, đến xử lý chuỗi và thuật toán đồ thị, chứng minh sự linh hoạt của nó trong lập trình.

Khi hiểu rõ các giới hạn và khả năng của Stack, bạn sẽ thấy đây là công cụ cần thiết và hiệu quả, giúp tối ưu hóa tư duy và cách tiếp cận vấn đề trong nhiều tình huống lập trình thực tế.

Nguồn: Viễn Đinh - Cách Giải Ngăn Xếp