Ngăn xếp

Trong phần này chúng tôi sẽ giới thiệu tới các bạn cấu trúc dữ liệu ngăn xếp hay còn gọi là stack. Để hiểu rõ được các hoạt động và thực hiện của loại cấu trúc dữ liệu này bạn cần có những kiến thức về:

Mảng
Danh sách liên kết (linked list)

Bới vì cấu trúc dữ liệu ngăn xếp có thể được xây dựng từ mảng hoặc danh sách liên kết.

Giới thiệu về ngăn xếp (Stack)

Ngăn xếp là loại cấu trúc dữ liệu có tính chất “vào trước thì ra sau” (Last In First Out - LIFO).

Nó có thể được thể hiện như sau:

Hình 1: Mô tả cấu trúc dữ liệu ngăn xếp

Push: Chèn dữ liệu vào ngăn xếp.

Pop: Lấy dữ liệu ra từ đỉnh của ngăn xếp.

Top: Biến lưu trữ vị trí đỉnh của ngăn xếp.

Khác so với hàng đợi. vị trí lấy chèn dữ liệu vào và lấy dữ liệu ra là khác nhau, thì với ngăn xếp ta chèn và lấy dữ liệu từ ngăn xếp trên cũng một vị trí gọi là vị trí đỉnh (top).

Ta sẽ đi vào tìm hiểu chi tiết hơn quá trình chèn dữ liệu vào ngăn xếp và lấy chúng ra dưới đây.

Chèn dữ liệu vào ngăn xếp - push

Như đã nói ở trên, chúng ta luôn luôn chèn dữ liệu vào ngăn xếp tại đỉnh (top). Khi ta chèn 1 phần tử dữ liệu vào ngăn xếp ta phải tăng top lên một. Vị trí đỉnh mới này sẽ là vị trí chèn dữ liệu cho lần chèn tiếp theo.

Hình 2: Chèn dữ liệu vào ngăn xếp (push)

Lấy dữ liệu ra khỏi ngăn xếp - pop

Khi lấy một phần tử dữ liệu ra khỏi khỏi stack, nghĩa là ta đã lấy dữ liệu tại đỉnh của stack nên giá trị của đỉnh (top) sau khi dữ liệu được lấy ra phải giảm đi 1.

Hình 3: Lấy dữ liệu từ đỉnh ngăn xếp (pop)

Một số chú ý với ngăn xếp

Kích thước của ngăn xếp không phải là vô tận, giả sử ta cấp phát cho một ngăn xếp có kích thước là SIZE, khi đó ta phải chú ý các vấn đề có thể ra trong quá trình push và pop phần tử dữ liệu của ngăn xếp. Khi ngăn xếp đã đầy nếu ta vẫn chèn dữ liệu vào thì sẽ xảy ra hiện tượng tràn ngăn xếp.

Vậy nên khi ngăn xếp đã đầy, ta cần ngăn chặn việc chèn thêm dữ liệu vào ngăn xếp.

Cũng như vậy, khi ngăn xếp rỗng, ta không thể lấy phần tử nào của ngăn xếp ra cả.

Cách hoạt động của stack

Để mô phỏng hoạt động của stack, có thể sử dụng mảng tĩnh một chiều. Giả sử ta có mảng các số nguyên với kích thước bằng 7 “int stack[7]”.

Khi mới khởi tạo, stack rỗng, top = 0.

Hình 4: Mô phỏng hoạt động của stack

Stack rỗng khi top == 0.

Stack đầy khi top == 7 (bằng kích thước của stack).

Các ứng dụng thực tế của stack

Kiểm tra sự cân bằng của các ký tự (ví dụ các dấu ngoặc trong các trình soạn thảo văn bản hay các IDE).
Thực hiện tính năng undo trong các trình soạn thảo văn bản (ví dụ trong MS Word khi ta nhấn tổ hợp phím ctrl+Z).
Thực hiện tính năng trở về trang trước trong các trình duyệt web (hay phím back trên điện thoại thông minh (smart phone).
Sử dụng trong các thuật toán tìm đường (DFS).

Xây dựng cấu trúc dữ liệu ngăn xếp

Như đã được đề cập ở các phần trên, ngăn xếp có thể được xây dựng từ mảng hoặc danh sách liên kết. Ta sẽ đi vào tìm hiểu chi tiết cách xây dựng ngăn xếp với cả hai loại trên.

Các hàm thao tác với ngăn xếp:

push(X): Chèn dữ liệu “X” vào ngăn xếp.
pop(): Lấy dữ liệu ra từ đỉnh của ngăn xếp (xóa bỏ phẩn từ đỉnh khỏi stack).
top(): Trả về giá trị của phần tử ở đỉnh của stack mà không xóa bỏ phần tử đó khỏi stack.
isEmpty(): Kiểm tra xem stack có rỗng không.

Các hàm này đều có độ phức tạp về thời gian thực hiện là O(1). tức là chúng có thể thực hiện ngay tức thì.

Xây dựng ngăn xếp từ mảng

Trong bài học này tôi sử dụng C++ để xây dựng ngăn xếp.

#include <iostream>
using namespace std;
#define SIZE 500

class Stack
{
private:
         int A[SIZE];  /* Mảng để chứa ngăn xếp */
         int top;   /* Biến đánh dấu vị trí đỉnh của ngăn xếp */
public:
	/* Hàm khởi tạo của lớp Stack */
	Stack()
	{
		top = 0; /* Khi stack rỗng, top = 0 */
	}

	/* Chèn phần tử vào đỉnh stack. */ 
	void Push(int n) 
	{
	  if(top == SIZE) { /* Xử lý ngoại lệ khi stack bị tràn */ 
                            cout << "ERROR: Stack overflow!" << endl;
			return;
		}
		A[top++] = n;
	}
 
	/* Xóa bỏ phần tử từ đỉnh của stack.*/
	void Pop() 
	{
		if(top == 0) { /* Kiểm tra nếu stack rỗng */
			cout << "ERROR: Stack is empty" << endl;
			return;
		}
		top--;
	}
 
	int Top() 
	{
		return A[--top]; /* Trả về phần tử ở đỉnh của stack */
	}
 
	/* Kiểm tra stack có rỗng hay không, nếu rỗng trả về true, ngược lại 
              trả về false */
	bool isEmpty()
	{
		if(top == 0) return true;
		return false;
	}

	/* HÀM IN RA CÁC PH ̀N TỬ CỦA STACK */
	void Print() {
		int i;
		for(i = 0; i<top; i++)
			cout << A[i] << " ";
		cout << endl;
	}
};

int main()
{
    /* Code để kiểm tra hoạt động của chương trình,
    gọi hàm Print() sau mỗi bước để kiểm tra tính đúng đắn */
	Stack S;
	S.Push(1); /* 1 */
	S.Push(2); /* 1, 2 */
	S.Print(); 
	S.Push(5); /* 1, 2, 5 */
	S.Print();
	S.Pop();    /* 1, 2 */
	S.Print();
	
	return 0;
}

Xây dựng ngăn xếp từ danh sách liên kết


#include <iostream>

using namespace std;

#define INT_MIN -2147483648
#define INT_MAX 2147483648


/* Cấu trúc để chứa danh sách liên kết */
struct sNode {
    int data;
    struct sNode* next;
};

class Stack {
public:
    /* Node root có thuộc tính public để có thể được sửa đổi và tác động 
        từ bên ngoài */
    struct sNode* root;
    
    /* Khởi tạo stack rỗng */
    Stack()
    {
        root = NULL;
    }
    
    /* Hàm để tạo ra một node mới tham tham số truyền 
        vào là một số nguyên */
    struct sNode* newNode(int data)
    {
        struct sNode* s_node = (struct sNode*)malloc(sizeof(struct sNode));
        s_node->data = data;
        s_node->next = NULL;
        return s_node;
    }
    
    /* 
         Thêm dữ liệu vào đỉnh ngăn xếp,
         Đỉnh của ngăn xếp chính là node gốc của danh sách sách liên kết,
         việc chèn phần tủ vào đầu danh sách liên kết thay vì chèn vào cuối danh 
         sách tránh được việc phải duyệt qua toàn bộ danh sách rồi mới chèn,
         chèn ở đầu danh sách có độ phức tạp thời gian là O(1)
    */
    void Push(int data)
    {
        /* Không cần kiểm tra điều kiện tràn ngăn xếp vì ta sử dụng danh sách
            liên kết (cấp phát động) */
        struct sNode* s_node = newNode(data);
        s_node->next = root;
        root = s_node;
    }
    
    /* Xóa phần tử từ đỉnh ngăn xếp (xóa đi phần tử đầu tiên trong danh sách
        liên kết */
    void Pop()
    {
        if (isEmpty()) {
            printf("ERROR: Stack is empty\n");
            return;
        }
        struct sNode* temp = root;
        root = root->next;
        int popped = temp->data;
        free(temp);
    }
    
    /* Trả về giá trị của phần tử đỉnh ngăn xếp */
    int Top()
    {
        if (isEmpty()) {
            printf("ERROR: Stack is empty\n");
            return INT_MIN;
        }
        return root->data;
    }
    
    /* Nếu ngăn xếp rỗng, trả về true. Ngược lại trả về false */
    int isEmpty()
    {
        return !root;
    }
    
    /* Hàm in danh sách liên kết theo thứ tự từ đầu tới cuối */
    void Print()
    {
        if (!isEmpty()) {
            struct sNode* current = root;
            while (current->next != NULL) {
                printf("%d ", current->data);
                current = current->next;
            }
            printf("%d ", current->data);
            printf("\n");
        }
    }


    /* Hàm in danh sách liên kết (ngăn xếp) theo thứ tự đảo ngược 
        dùng đệ quy */
    void rPrint(struct sNode* temp)
    {
        struct sNode* current = temp;
        if (current == NULL) {
            printf("\n");
            return;
        }
        rPrint(current->next);
        printf("%d ", current->data);
    }
};

int main()
{
    /* Code để kiểm tra hoạt động của chương trình,
    gọi hàm Print() hoặc rPrint() sau mỗi bước để kiểm tra tính đúng đắn */
    Stack S;
    S.Push(1); /* 1 */
    S.Push(2); /* 2, 1 */
    //S.Print();
    S.rPrint(S.root);
    S.Push(5); /* 5, 2, 1 */
    //S.Print();
    S.rPrint(S.root);
    S.Pop(); /* 2, 1 */
    //S.Print();
    S.rPrint(S.root);

    return 0;
}

Các bạn có thể xem mã nguồn cài đặt ngăn xếp trên gitlab

1. Cài đặt ngăn xếp sử dụng mảng, ngôn ngữ thực hiện C++:

https://gitlab.com/thevngeek/basic-data-structure/blob/master/nganxep_sudungmang.cpp

2. Cài đặt ngăn xếp sử dụng danh sách liên kết, ngôn ngữ thực hiện C++:

https://gitlab.com/thevngeek/basic-data-structure/blob/master/nganxep_sudungdanhsachlienket.cpp

3. Cài đặt ngăn xếp sử dụng danh sách liên kết, ngôn ngữ thực hiện C:

https://gitlab.com/thevngeek/basic-data-structure/blob/master/stack_danhsachlienket_C.c

Kết luận

Ngăn xếp là loại cấu trúc dữ liệu dễ cài đặt và được sử dụng rộng rãi. Ngày nay trong hầu hết các ngôn ngữ đã hỗ trợ sẵn việc cài đặt ngăn xếp, và ta chỉ cần học cách sử dụng nó.

Tuy nhiên hiểu được việc cài đặt ngăn xếp là vô cùng quan trọng để ta có thể kiểm soát chương trình của mình hiệu quả hơn

Bài học trước Bài kế tiếp

ngăn xếp cấu trúc dữ liệu data structure stack