Cài đặt và sử dụng Ngăn xếp – Stack trong C++

Chào mừng các bạn quay trở lại với series thuật toán – cấu trúc dữ liệu và giải thuật của VNTALKING. Bài viết hôm nay, chúng ta sẽ cùng nhau tìm hiểu một loại cấu trúc dữ liệu rất phổ biến, đó là ngăn xếp Stack.

Khi lập trình, chúng ta thường phải xử lý một lượng lớn dữ liệu thô và chưa được tổ chức. Điều này đỏi hỏi cần một cấu trúc dữ liệu để lưu dữ liệu và cho phép người dùng thao tác trên dữ liệu một cách hiệu quả.

😋 Đọc các bài viết thuật toán khác:

• Thuật toán Quick Sort
• Thuật toán tìm ước chung lớn nhất
• Thực hành cài đặt và sử dụng Hàng đợi – Queue trong C++

Giới thiệu ngăn xếp Stack

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 LIFO (Last In First Out). Tức là phần tử cuối cùng được đưa vào ngăn xếp sẽ là phần tử đầu tiên được lấy ra khỏi ngăn xếp stack khi cần.

Bạn có thể hình dung ngăn xếp stack như một chồng sách đặt trong một cái hộp. Khi thêm một sách mới thì nó sẽ được đặt lên trên, cuốn sách cuối cùng được đặt ở trên đỉnh cũng sẽ là cuốn được lấy ra đầu tiên.

Như bạn thấy ở hình trên, phần tử cuối cùng sẽ là phần tử đầu tiên được lấy ra khỏi ngăn xếp stack.

Việc xóa hay thêm mới một phần tử trong stack cũng sẽ luôn thực hiện ở cùng một đầu cuối cùng của stack.

Cách thao tác với Stack

Với ngăn xếp stack, chúng ta chỉ có các thao tác xử lý dữ liệu sau:

• push(): Thêm một phần tử mới vào ngăn xếp, số phần tử ngăn xếp tăng lên 1
• pop(): Xóa một phần tử khỏi stack
• top(): Trả về giá trị của phần tử trên đỉnh của stack. Số phần tử ngăn xếp không thay đổi.
• isEmpty(): Kiểm tra ngăn xếp stack có rỗng hay không.
• isFull(): Kiểm tra trạng thái stack đã đầy hay chưa.

Cài đặt ngăn xếp Stack trong C/C++

Chúng ta sẽ cùng nhau tìm hiểu cơ chế hoạt động của hai thao tác phổ biến nhất trên stack là Push() và Pop().

Thao tác PUSH (chèn mới):

• Đầu tiên, kiểm tra stack đã đầy hay chưa. Tức kiểm tra điều kiện tràn
• Trong trường hợp ngăn xếp stack đã đầy, thoát thao tác với thông báo: “Stack đã đầy”.
• Ngược lại, ngăn xếp chưa đầy, con trỏ “top” tăng lên 1, sau đó dữ liệu được thêm vào stack.

Dưới đây là code minh họa.

void stack_data::push (int a)
{
    if(top >= 5)
    {
        cout << "Overflow\n";
    }
    else
    {
        data[++top] = a;   
    }
}

Thao tác POP (xóa một phần tử):

• Trước tiên, kiểm tra xem ngăn xếp có rỗng hay không.
• Nếu ngăn xếp bị rỗng, thoát thao tác với thông báo: “Ngăn xếp rỗng”.
• Ngược lại, hiển thị giá trị phần tử đang được trỏ bởi con trỏ “top”. Sau đó giảm con trỏ “top” đi 1.

Code minh họa cho thao tác Pop

int stack_data::pop ()
{
    if(top < 0)
    {
        cout << "Underflow\n";
        return 0;
    }
    else
    {
        int pop = data[top--];
        return pop;
    }
}

Cuối cùng là chương trình cài đặt stack hoàn thiện như sau:

# include<iostream>
using namespace std;
 
class stack_data
{
    public:
    int top;
    int data[5];  
    stack_data()
    {
        top = -1;
    }
 
    void push (int a);
    int pop ();
    void isEmpty();
    void isFull();
    void display();
};
 
void stack_data::push (int a)
{
    if(top >= 5)
    {
        cout << "Overflow\n";
    }
    else
    {
        data[++top] = a;   
    }
}
 
int stack_data::pop ()
{
    if(top < 0)
    {
        cout << "Underflow\n";
        return 0;
    }
    else
    {
        int pop = data[top--];
        return pop;
    }
}
 
void stack_data::isEmpty()
{
    if(top < 0)
    {
        cout << "Stack Underflow\n";
    }
    else
    {
        cout << "Stack can occupy elements.\n";
    }
}
 
void stack_data::isFull()
{
    if(top >= 5)
    {
        cout << "Overflow\n";
    }
    else
    {
        cout << "Stack is not full.\n";
    }
}
 
void stack_data::display()
{
    for(int i=0;i<5;i++)
    {
        cout<<data[i]<<endl;
    }
}
 
int main() {
 
    stack_data obj;
    obj.isFull();
    obj.push (40);
    obj.push (99);
    obj.push (66);
    obj.push (40);
    obj.push (11);
     
    cout<<"Stack after insertion of elements:\n";
    obj.display();
   
    cout<<"Element popped from the stack:\n";
    cout<<obj.pop ()<<endl;
         
}

Kết quả khi chạy chương trình trên sẽ như dưới đây:

Stack is not full.
Stack after insertion of elements:
40
99
66
40
11
Element popped from the stack:
11

Ứng dụng của Stack

Tùy vào mỗi yêu cầu cụ thể mà bạn sẽ sử dụng stack để giải quyết. Dưới đây là một số ứng dụng phổ biến của ngăn xếp stack.

• Stack hay được dùng để hoán đổi vị trí của các phần tử trong Array hoặc String.
• Một Stack có thể cần thiết trong tình huống cần Backtracking trong một số thuật toán.
• Trong các ứng dụng kiểu như Text editor, các tính năng undo, redo có thể sẽ cần tới stack.
• Chuyển đổi Infix/Prefix/Postfix trong Binary Trees.

Độ phức tạp của các thao tác trong Stack

Độ phức tạp của push() và pop() là như nhau, đều là: O(1)

Lý do là việc thêm mới và xóa phần tử trong stack đều thực hiện ở một đầu – đỉnh của stack.

Lời kết

Như vậy, trong bài viết này, chúng ta đã hiểu được ngăn xếp stack là gì, cách thức hoạt động cũng như ứng dụng của nó trong lập trình.

Mình hi vọng, những kiến thức này sẽ giúp ích cho bạn trong các dự án sắp tới.

Hẹn gặp lại ở bài viết sau nhé.

💦 Đọc thêm bài viết hay khác:

• Thực hành Deploy dự án Nodejs từ A-Z bằng Docker
• [Design Pattern] Ứng dụng Adapter Design Pattern trong dự án
• Khóa học lập trình Angular từ A-Z FREE (thực hành Project hoàn chỉnh)

​Nhận sách ​Java Advanced Features

​Java là ngôn ngữ lập trình phổ biến nhất thế giới, là hình mẫu của tư tưởng OOP. Nếu bạn muốn bắt đầu với Java thì đây là cuốn sách không thể bỏ qua. Với 63 ví dụ thực hành, cùng với cách viết ngắn gọn dễ hiểu sẽ giúp bạn hiểu rõ bản chất của Java.

​Hiện Amazon đang bán với giá 16$, nhưng với VNTALKING thì miễn phí cho bạn. Còn chờ gì nữa?

DOWNLOAD