Tìm hiểu về ngăn xếp, ứng dụng trong thực tế và cài đặt bằng lập trình c++

Trong bài viết này Stanford sẽ chia sẻ cho các bạn về ngăn xếp (stack) trong cấu trúc và giải thuật cũng như các ứng dụng của nó trong thực tế sau đó cài đặt ngăn xếp bằng lập trình c++.

Ngăn xếp (stack) là gì ?

Ngăn xếp (stack) là một cấu trúc dữ liệu tuyến tính hoạt động theo nguyên tắc "Last In, First Out" (LIFO), nghĩa là phần tử được thêm vào cuối cùng sẽ được lấy ra đầu tiên. Ngăn xếp thường được sử dụng trong các tình huống cần quản lý dữ liệu theo thứ tự ngược lại, như trong việc xử lý đệ quy, duyệt cây, hoặc quản lý các hoạt động undo/redo.

Các thao tác cơ bản trên ngăn xếp:

  • Push: Thêm một phần tử vào đỉnh ngăn xếp.
  • Pop: Lấy phần tử ở đỉnh ngăn xếp ra.
  • Peek/Top: Xem phần tử ở đỉnh ngăn xếp mà không lấy ra.
  • IsEmpty: Kiểm tra xem ngăn xếp có rỗng hay không.
  • Size: Trả về số lượng phần tử trong ngăn xếp.


Ứng dụng của ngăn xếp trong thực tế

Ngăn xếp có rất nhiều ứng dụng trong thực tế, đặc biệt trong các lĩnh vực liên quan đến quản lý dữ liệu và xử lý thứ tự. Dưới đây là một số ví dụ phổ biến:

  • Quản lý đệ quy: Ngăn xếp được sử dụng để lưu trữ trạng thái của các lời gọi đệ quy. Mỗi lần một hàm đệ quy được gọi, trạng thái hiện tại của hàm đó được lưu vào ngăn xếp. Khi hàm kết thúc, trạng thái được lấy ra từ ngăn xếp để tiếp tục thực hiện.
  • Duyệt cây: Ngăn xếp được sử dụng trong các thuật toán duyệt cây như duyệt theo chiều sâu (Depth-First Search - DFS). Ngăn xếp giúp lưu trữ các nút cần duyệt tiếp theo.
  • Quản lý biểu thức toán học: Ngăn xếp được sử dụng để chuyển đổi và tính toán các biểu thức toán học, chẳng hạn như chuyển đổi từ biểu thức trung tố (infix) sang hậu tố (postfix) và ngược lại.
  • Hệ thống undo/redo: Trong các ứng dụng như trình soạn thảo văn bản, ngăn xếp được sử dụng để lưu trữ các thao tác của người dùng. Khi người dùng thực hiện thao tác undo, thao tác cuối cùng được lấy ra từ ngăn xếp và hoàn tác.
  • Kiểm tra dấu ngoặc: Ngăn xếp được sử dụng để kiểm tra tính hợp lệ của các dấu ngoặc trong biểu thức. Mỗi khi gặp dấu ngoặc mở, nó được đẩy vào ngăn xếp. Khi gặp dấu ngoặc đóng, dấu ngoặc mở tương ứng được lấy ra từ ngăn xếp để kiểm tra tính hợp lệ.
  • Quản lý bộ nhớ trong hệ điều hành: Ngăn xếp được sử dụng để quản lý bộ nhớ trong quá trình thực thi chương trình. Mỗi lần một hàm được gọi, các biến cục bộ và tham số của hàm đó được lưu vào ngăn xếp. Khi hàm kết thúc, các biến này được giải phóng khỏi ngăn xếp.

Minh họa thuật toán ngăn xếp bằng C++:

Sau khi các bạn đã hiểu được ngăn xếp là gì cũng như ứng dụng của ngăn xếp (stack) trong thực tế. Tiếp theo dưới đây là một ví dụ đơn giản về cách triển khai ngăn xếp bằng mảng trong lập trình C++ mà Stanford hướng dẫn bạn cùng thực hiện như sau:

#include <iostream>
using namespace std;
 
class Stack {
private:
    int top;
    int size;
    int* stack;
public:
    Stack(int c) {
        top = -1;
        size = c;
        stack = new int[size];
    }
 
    ~Stack() {
        delete[] stack;
    }
 
    void push(int data) {
        if (top == size - 1) {
            cout << "Stack is full\n";
            return;
        } else {
            stack[++top] = data;
        }
    }
 
    void pop() {
        if (top == -1) {
            cout << "Stack is empty\n";
            return;
        } else {
            top--;
        }
    }
 
    int peek() {
        if (top == -1) {
            cout << "Stack is empty\n";
            return -1;
        }
        return stack[top];
    }
 
    bool isEmpty() {
        return top == -1;
    }
 
    int getSize() {
        return top + 1;
    }
 
    void display() {
        if (top == -1) {
            cout << "Stack is empty\n";
            return;
        }
        for (int i = 0; i <= top; i++) {
            cout << stack[i] << " ";
        }
        cout << endl;
    }
};
 
int main() {
    Stack s(5);
 
    s.push(10);
    s.push(20);
    s.push(30);
    s.push(40);
 
    cout << "Cac phan tu trong ngan xep: "<<endl;
    s.display();
 
    s.pop();
    cout << "Cac phan tu cua ngan xep sau khi lay phan tu tren cung: "<<endl;
    s.display();
 
    cout << "Phan tu tren cung la: " << s.peek() << endl;
 
    return 0;
}
Trong ví dụ trên, chúng ta đã tạo một lớp Stack với các phương thức cơ bản như push, pop, peek, isEmpty, getSize, và display. Bạn có thể thử chạy và điều chỉnh mã để hiểu rõ hơn về cách hoạt động của ngăn xếp. Nếu bạn có bất kỳ câu hỏi nào bạn có thể liên hệ với Stanford để được hỗ trợ và giải đáp. Bạn muốn tìm hiểu về hàng đợi (queue) trong cấu trúc và giải thuật xem ngay tại đây: tìm hiểu hàng đợi (queue). Chúc bạn học tập tốt !

Bên cạnh đó bạn có thể bắt đầu ngay con đường chinh phục trở thành lập trình viên chuyên nghiệp trong tương lai của mình bằng việc đăng ký tham gia khoá học lập trình tại đây: http://bit.ly/2SLPYFF. Hoặc gọi ngay cho Stanford theo hotline: 0963.723.236 - 0866.586.366 để được gọi lại tư vấn trực tiếp nhé.

==========🎬 🎬 🎬==========
☎️STANFORD – ĐÀO TẠO VÀ PHÁT TRIỂN CÔNG NGHỆ
Hotline: 0963 723 236 - 0866 586 366
Website: https://stanford.com.vn
Facebook: https://www.facebook.com/Stanford.com.vn
Youtube: http://bit.ly/2TkKT7I

Tags: ngăn xếp, stack là gì