Cấu trúc Stack là gì, cơ chế hoạt động và ứng dụng trong thực tiễn của Stack

Stack là gì? Stack là một cấu trúc dữ liệu quan trọng, cung cấp một cơ chế phức tạp hơn so với mảng, giúp tăng tốc độ tính toán và tạo sự thuận tiện khi lập trình. Vậy stack là gì, ý nghĩa của cấu trúc Stack và khi nào chúng ta nên sử dụng nó?

1. Ngăn xếp Stack là gì?

Nếu bạn là một lập trình viên mới chẳn hẳn sẽ đang rất thắc mắc nghĩa Stack là gì? Là một loại danh sách tuyến tính đặc biệt, trong đó các phép bổ sung và loại bỏ luôn được thực hiện ở một đầu, được gọi là đỉnh.

Một định nghĩa khác cho rằng đây chính là một cấu trúc dữ liệu trừu tượng hoạt động theo nguyên lý “vào sau, ra trước” (Last In First Out – LIFO).

Ví dụ thực tế: Khi chúng ta đặt các chiếc bánh vào một hộp, hành động này tương đương với phép Push trong Stack, vì chúng ta sẽ đặt các chiếc bánh lần lượt lên đỉnh của hộp. Khi muốn lấy một chiếc bánh ra, chúng ta cũng phải lấy chiếc ở đỉnh ra trước, tương tự như phép Pop trong Stack.

Stack là gì nhỉ? Stack là một cấu trúc dữ liệu dạng thùng chứa các phần tử, thường được gọi là các Node. Có hai phép toán cơ bản:

• Push: Thêm một phần tử vào đỉnh của ngăn xếp, nghĩa là phần tử đó sẽ được thêm vào sau các phần tử đã có trong ngăn xếp.
• Pop: Loại bỏ và trả về phần tử đang đứng ở đỉnh của ngăn xếp. Phần tử này sau khi được lấy sẽ bị xóa khỏi ngăn xếp.

Ngoài ra, ngăn xếp còn có các phép toán bổ sung khác như isEmpty() để kiểm tra xem có rỗng hay không và Top() để trả về giá trị của phần tử đầu tiên mà không xóa nó khỏi Stack. Vậy bạn đã hiểu rõ Stack là gì chưa, tiếp theo bài viết cùng tìm hiểu nguyên nhân gây ra hiện tượng Stack là gì nhé.

2. Nguyên nhân Stack tràn là gì?

Trong lập trình, nguyên nhân Stack tràn xảy ra khi các con trỏ ngăn xếp vượt quá giới hạn của ngăn xếp. Ngăn xếp thường bao gồm một số hữu hạn các địa chỉ không gian, thường được xác định từ điểm bắt đầu của chương trình.

Kích thước của ngăn xếp còn phụ thuộc vào nhiều yếu tố khác nhau, bao gồm các chương trình, hay ngôn ngữ lập trình, kiến trúc, đơn/đa luồng và có cả lượng bộ nhớ có sẵn.

Khi một chương trình đang cố gắng sử dụng quá tải số lượng bố nhợ nhiều hơn lượng có sẵn  (tức là khi chương trình cố gắng truy cập vùng bộ nhớ ngoài giới hạn của ngăn xếp, tạo thành lỗi tràn bộ nhớ đệm), ngăn xếp sẽ bị coi là tràn và thường dẫn đến lỗi hoặc hành vi không mong muốn của chương trình.

3. Mô tả ngăn xếp 

Trong phần này, chúng ta sẽ trình bày hai cách mô tả Stack là gì: Bằng mảng và bằng danh sách liên kết đơn. Hãy xem xét những điểm tương đồng và khác biệt giữa hai cách này.

3.1. Mô tả Stack bằng mảng

Khi mô tả bằng mảng, chúng ta có các đặc điểm sau:

• Việc thêm một phần tử vào tương đương với việc thêm một phần tử vào cuối mảng.
• Khi loại bớt một phần tử khỏi ngăn xếp, điều này có nghĩa loại bỏ một phần tử ở cuối mảng.
• Cấu hình Stack sẽ bị tràn nếu thêm vào mảng đã đầy.
• Stack được coi là rỗng khi số phần tử thực sự trong mảng là 0.

3.2. Mô tả ngăn xếp bằng danh sách liên kết đơn

Khi mô tả bằng danh sách liên kết đơn, chúng ta cũng có các đặc điểm sau:

• Khi thêm một phần tử vào Stack IT, điều này tương đương với việc thêm một phần tử vào cuối danh sách (insertlast).
• Việc loại bỏ một phần tử từ Stack cũng tương đương với việc loại bỏ một phần tử ở cuối danh sách.
• Cấu hình bị tràn khi không gian nhớ dành cho các biến động không đủ để thêm một phần tử mới. Tuy nhiên, việc kiểm tra này khá phức tạp và phụ thuộc vào máy tính và ngôn ngữ lập trình. Do đó, khi triển khai, ta có thể bỏ qua việc kiểm tra Stack tràn.

4. Các hoạt động cơ bản trên Stack bạn cần biết

Các thao tác cơ bản trên cấu trúc dữ liệu ngăn xếp liên quan đến việc khởi tạo, sử dụng và sau đó xóa nó. Ngoài những thao tác cơ bản này, ngăn xếp còn có hai hoạt động cơ bản liên quan đến khái niệm như sau:

• Hoạt động push(): Thêm một phần tử vào đỉnh của ngăn xếp.
• Hoạt động pop(): Xóa một phần tử từ đỉnh của ngăn xếp.

Khi dữ liệu đã được push lên ngăn xếp, để sử dụng ngăn xếp một cách hiệu quả, chúng ta cần kiểm tra trạng thái của ngăn xếp. Để thực hiện được điều này một cách chuẩn xác nhất, chúng ta sẽ cùng tham khảo một số tính năng hỗ trợ khác của Stack:

• Hoạt động peek(): Lấy phần tử ở đỉnh của ngăn xếp mà không xóa nó.
• Hoạt động isFull(): Kiểm tra ngăn xếp đầy chưa.
• Hoạt động isEmpty(): Kiểm tra xem ngăn xếp có trống không.

Tại mọi thời điểm, chúng ta duy trì một con trỏ trỏ tới phần tử dữ liệu được push vào trên cùng của ngăn xếp. Con trỏ này luôn biểu diễn vị trí của phần tử trên cùng của ngăn xếp và thường được gọi là “top”. Con trỏ top cung cấp giá trị của phần tử trên cùng của ngăn xếp mà không cần thực hiện hoạt động pop.

5. Cấu hình Stack là gì?

Cấu hình Stack phần mềm (Software Stack) là gì? Dưới đây là sơ đồ ngăn xếp Stack là gì minh họa các hoạt động diễn ra trên ngăn xếp, hãy cùng chúng tôi khám phá nhé.

Một Stack có thể được triển khai thành công thông qua mảng (Array), cấu trúc (Struct), Con trỏ (Pointer) và danh sách liên kết (Linked List). 

Ngăn xếp Stack là gì? Ngăn xếp Stack có thể có 2 dạng như sau: Dạng kích cỡ cố định hoặc có thể thay đổi kích cỡ. Trong phần dưới đây, chúng ta sẽ triển khai ngăn xếp bằng cách sử dụng mảng với việc triển khai ngăn xếp có kích cỡ cố định.

6. Cài đặt ngăn xếp bằng mảng

Trong phần hướng dẫn này, chúng ta sẽ đi chi tiết từng thao tác của cấu trúc dữ liệu ngăn xếp và triển khai cài đặt ngăn xếp sử dụng mảng. Ở phần tiếp theo, tôi sẽ giới thiệu một số cách cài đặt khác.

Chúng ta sẽ phân tích kỹ thuật và sử dụng một mảng một chiều kiểu int để tạo ngăn xếp, cùng với biến capacity để lưu kích thước và biến top để theo dõi chỉ số của phần tử ở đỉnh.

6.1. Kiểm tra stack đầy (IsFull)

Hàm này kiểm tra xem stack đã đầy chưa. Nếu chỉ số top bằng capacity – 1, tức là đã đầy.

bool IsFull(int capacity){

    if(top >= capacity – 1){

        return true;

    }else{

        return false;

    }

}

6.2. Kiểm tra stack rỗng(IsEmpty)

Nếu không có phần tử nào, ta gán top = -1 để đánh dấu. Do đó, để kiểm tra stack có đang rỗng hay không, ta chỉ cần so sánh giá trị top với -1.

bool IsEmpty(){

    if(top == -1){

        return true;

    }else{

        return false;

    }

}

6.3. Thêm phần tử vào đỉnh stack (Push)

Chỉ trong điều kiện Stack chưa đầy, chúng ta có thể push (thêm phần tử) vào đỉnh stack. Nếu stack đầy, ta thông báo và không thực hiện push. Ngược lại, ta tăng top lên một và gán giá trị cho phần tử tại chỉ số top.

void Push(int stack[], int value, int capacity){

    if(IsFull(capacity) == true){

        printf(“nStack is full. Overflow condition!”);

    }else{

        ++top;

        stack[top] = value;

    }

}

6.4. Xóa phần tử khỏi đỉnh stack (Pop)

Chỉ có thể pop (xóa phần tử) từ đỉnh stack khi stack không rỗng. Nếu stack rỗng, ta thông báo và không thực hiện pop. Ngược lại, ta giảm top đi một.

void Pop(){

    if(IsEmpty() == true){

        printf(“nStack is empty. Underflow condition!”);

    }else{

        –top;

    }

}

6.5. Lấy giá trị phần tử ở đỉnh stack (Top)

Để lấy giá trị phần tử ở đỉnh stack, ta sử dụng thao tác đơn giản sau:

int Top(int stack[]){

    return stack[top];

}

6.6. Lấy số lượng phần tử trong stack (Size)

Biến top lưu chỉ số lớn nhất của stack. Vì vậy, việc lấy kích thước của stack rất đơn giản:

int Size(){

    return top + 1;

}

Và kết quả cuối cùng, chúng ta sẽ có chương trình đã được cài đặt stack hoàn thiện như sau:

#include <stdio.h>

int top = -1;

bool IsFull(int capacity){

    if(top >= capacity – 1){

        return true;

    }else{

        return false;

    }

}

bool IsEmpty(){

    if(top == -1){

        return true;

    }else{

        return false;

    }

}

void Push(int stack[], int value, int capacity){

    if(IsFull(capacity) == true){

        printf(“nStack is full. Overflow condition!”);

    }else{

        ++top;

        stack[top] = value;

    }

}

void Pop(){

    if(IsEmpty() == true){

        printf(“nStack is empty. Underflow condition!”);

    }else{

        –top;

    }

}

int Top(int stack[]){

    return stack[top];

}

int Size(){

    return top + 1;

}

int main(){

    int capacity = 3; 

    int top = -1; 

    int stack[capacity];   

    // pushing element 5 in the stack .

    Push(stack, 5, capacity);   

    printf(“nCurrent size of stack is %d”, Size());    

    Push(stack, 10, capacity);

    Push(stack, 24, capacity);   

    printf(“nCurrent size of stack is %d”, Size());

    // As the stack is full, further pushing will show an overflow condition.

    Push(stack, 12, capacity);     

    //Accessing the top element

    printf(“nThe current top element in stack is %d”, Top(stack));

    //Removing all the elements from the stack

    for(int i = 0 ; i < 3;i++)

        Pop();

    printf(“nCurrent size of stack is %d”, Size()); 

    //As the stack is empty , further popping will show an underflow condition.

    Pop();  

}

Kết quả chạy chương trình trên:

Current size of stack is 1

Current size of stack is 3

Stack is full. Overflow condition!

The current top element in stack is 24

Current size of stack is 0

Stack is empty. Underflow condition!

7. Ứng dụng Stack vào trong thực tế

Chúng ta sẽ cùng tìm hiểu về ý nghĩa của Stack là gì khi ứng dụng vào trong thực tế trong lĩnh vực phát triển phần mềm như thế nào thông qua phần thông tin dưới đây: 

Đảo ngược xâu: Ta nhập xâu vào Stack, sau đó lấy lần lượt các phần tử sẽ ra từ đỉnh của nó. Như vậy, ta thu được xâu đã được đảo ngược.

Chuyển đổi số từ hệ cơ số thập phân sang hệ nhị phân: Ta lấy số dư n%2 và lưu vào stack, sau đó gán n=n/2. Tiếp tục quá trình này cho đến khi n=1, ta cũng lưu đây. Sau đó, ta lấy lần lượt các phần tử để có được xâu biểu diễn nhị phân của n.

Hy vọng thông qua bài viết này, các bạn đã hiểu phần nào ngăn xếp và nó được sử dụng để làm gì trong thực tế, ý nghĩa của sự phát triển Stack mang lại những cơ hội gì. 

Bạn có thể dựa vào kiến thức về công nghệ Stack là gì (Technology Stack) và ngôn ngữ lập trình mà bạn đang học để triển khai cách sử dụng ngăn xếp giúp bạn hiểu rõ hơn vấn đề này. Trong các bài tiếp theo, chúng tôi sẽ giới thiệu về ý nghĩa của công nghệ đang phát triển nhất hiện nay.