C++ Data Structure: Tìm hiểu và xây dựng Stack

Hi, chào các bạn.

Bài viết ngày hôm nay, tôi sẽ giới thiệu với các bạn một kiểu cấu trúc dữ liệu mới, đó là stack.

Chúng ta có thể xây dựng stack dựa trên nguyên lý của linked list.

1. Tìm hiểu về stack.

– Trong stl của c++, stack được coi như là một container (danh sách các thùng chứa).

– Và thực tế, stack chính là một danh sách lưu trữ dữ liệu. Nó có thực hiện theo nguyên lý. Vào sau ra trước.

– Stack được gọi là ngăn xếp, nó giống như việc xếp những quyển sách vào trong một chiếc thùng.

Quyển nào xếp trước thì sẽ ở dưới, quyển nào xếp sau thì sẽ ở trên, và như vậy khi đẩy dữ liệu ra ngoài thì ông sau sẽ ra trước.

– Hai phước thức push và pop là hai phương thức cơ bản thực hiện nhiệm vụ đẩy dữ liệu vào, và bỏ dữ liệu ra của stack.

2. Xây dựng lớp stack.

Bạn có thể sử dụng một mảng dữ liệu để lưu trữ dữ liệu cho stack và sau đó thực hiện logic theo nguyên lý ở trên.

Nhưng mảng có hạn chế đó là phải có số lượng cấp phát cụ thể rõ ràng.

Và như vậy diều đó không tối ưu cho việc áp dụng stack vào các dự án lớn.

Đòi hỏi tính linh hoạt trong việc sử dụng vùng nhớ.

Nhưng bù lại sẽ tránh được việc sử dụng con trỏ, mà vốn dĩ có nhiều phức tạp trong việc quản lý và hủy bỏ.

Vậy thì khi với những bài toán nhỏ gọn, phạm vi hẹp, bạn có thể xây dựng một kiểu stack dùng mảng để lưu trữ.

Trong bài viết này tôi sẽ sử dụng linked list để xây dựng stack theo một cách tổng quát nhất.

a. Xây dựng Class NodeData

template <typename T>
class NodeData
{
public:
    NodeData() : next_(NULL) { ; }
    void         set_data(T val) { data_ = val; }
    T            get_data() const { return data_; }
    void         set_next(NodeData<T>* next) { next_ = next; }
    NodeData<T>* get_next() const { return next_; };
private:
    T            data_;
    NodeData<T>* next_;
};

b. Xây dựng class stack dựa trên linked list. 

Ở đây tôi sử dụng single linked list, với 1 con trỏ pHead và một con trỏ next.

Do đó phương thức push và pop sẽ phức tạp hơn vì nó thực hiện nguyên lý chèn sau, và loại bỏ cuối.

Nhưng bù lại khi in dữ liệu tôi lại lợi thế hơn cho việc in danh sách đầu cho tới cuối.

– Có thể sử dụng phead và next 

– Có thể đổi ngược lại bằng ptail và prev.

– Nếu muốn linh hoạt hơn, các bạn có thể sử dụng cả ptail và phead, cả next và prev (doubly linked list)

template<typename T>
class Stack
{
public:
    Stack() : p_head_(NULL) {};
    ~Stack() { ; };

    void push(T val)
    {
        NodeData<T>* last = p_head_; // Tim ra node cuoi cung.
        if (last == NULL)            // neu chua co node nao
        {
            NodeData<T>* temp = new NodeData<T>(); \
            temp->set_data(val);
            p_head_ = temp;
        }
        else
        {
            while (last->get_next() != NULL)
            {
                last = last->get_next();
            }

            NodeData<T>* temp = new NodeData<T>(); \
            temp->set_data(val);
            temp->set_next(NULL); // next temp = NULL
            last->set_next(temp); // next cua last la temp
        }
    }

    void pop() // remove last element
    {
        if (p_head_ != NULL)
        {
            NodeData<T>* temp = p_head_;
            NodeData<T>* prev = NULL;
            while (temp->get_next() != NULL)
            {
                prev = temp;
                temp = temp->get_next();

            }

            delete temp;
            temp = NULL;
            if (prev != NULL)
              prev->set_next(NULL);
        }
    }

    NodeData<T>* head() { return p_head_; };

public:
    NodeData<T>* p_head_;
};

c. Sử dụng stack cho bài toán với dữ liệu thuần int.

#include <iostream>
#include <conio.h>
#include "Stack.h"


int main()
{

    Stack<int> stack_list;
    stack_list.push(1);
    stack_list.push(2);
    stack_list.push(3);

    stack_list.push(4);
    stack_list.push(5);
    stack_list.push(6);

    std::cout << "Danh sach sau khi push: \n";  // danh sách sẽ là 1 2 3 4 5 6
    NodeData<int>* p_head = stack_list.head();
    if (p_head != NULL)
    {
        NodeData<int>* temp = p_head;
        while (temp != NULL)
        {
            std::cout << "  " << temp->get_data();
            temp = temp->get_next();
        }
    }

    stack_list.pop();  // loại bỏ phần từ 6
    stack_list.pop();  // loại bỏ phân tử 5

    std::cout << "\n\n\n Danh sach sau khi pop: \n";
    p_head = stack_list.head();
    if (p_head != NULL)
    {
        NodeData<int>* temp = p_head;
        while (temp != NULL)
        {
            std::cout << "  " << temp->get_data();
            temp = temp->get_next();
        }
    }

    _getch();
    return 0;
}

Kết quả:

Ok. Đó là nguyên lý cơ bản của stack.

Khi bạn áp dụng cho dự án của mình, bạn có thể xử lý linh hoạt hơn, thông minh và hãy test thật kỹ.