Cấu trúc dữ liệu ngăn xếp (Stack)

Kiến thức cần biết:

• Khái niệm Cấu trúc dữ liệu
• Khái niệm Giải thuật
• Biết Lập trình bằng ngôn ngữ C:
  • Biết lập trình với mảng
  • Biết lập trình hàm
  • Biết đến khái niệm con trỏ
  • Sử dụng được kiểu dữ liệu do người dùng định nghĩa (struct)

Khái niệm ngăn xếp (Stack)

Ngăn xếp là một kiểu dữ liệu trừu tượng thường được sử dụng trong phần lớn các ngôn ngữ lập trình. 

Ngăn xếp là một cấu trúc dữ liệu tuyến tính tuân theo nguyên tắc Vào Cuối Ra Trước – Last In First Out (LIFO). Điều này có nghĩa là phần tử cuối cùng được chèn vào bên trong ngăn xếp sẽ bị loại bỏ đầu tiên. Bạn có thể nghĩ về cấu trúc dữ liệu ngăn xếp như một chồng đĩa xếp chồng lên nhau.

Một ngăn xếp trong thế giới thực chỉ cho phép hoạt động ở một đầu mà thôi. 

Ví dụ:

Với hình ảnh ở trên, chúng ta chỉ có thể thấy cấu trúc ngăn xếp

• Một ngăn xếp đồng xu xếp chồng lên nhau
• Một chồng đĩa đặt trong hộp
• Hộp đựng quả bóng Tennis
• Một chồng sách đặt đề lên nhau

Về cơ bản nếu bạn muốn lấy phần tử (có thể là đồng xu, cái đĩa, quả bóng tennis, quyển sách) ở dưới cùng, trước tiên bạn phải loại bỏ tất cả các phẩn tử ở trên ở trên. Đây chính xác là cách cấu trúc dữ liệu ngăn xếp hoạt động. 

Nguyên tắc LIFO của ngăn xếp

Theo thuật ngữ trong lập trình, đặt một mục lên trên ngăn xếp được gọi là đẩy và loại bỏ một mục được gọi là thao tác pop.

Trong hình minh hoạ trên, mặc dù mục 3 được giữ sau cùng nhưng nó đã bị loại bỏ trước. Đây chính là cách thức hoạt động của nguyên tắc LIFO (Last In First Out). Chúng ta có thể triển khai một ngăn xếp bằng bất kỳ ngôn ngữ lập trình nào như C, C++, Java, Python hoặc C #, nhưng đặc điểm kỹ thuật là khá giống nhau.

Các thao tác cơ bản của ngăn xếp

Có một số hoạt động cơ bản cho phép chúng tôi thực hiện các hành động khác nhau trên một ngăn xếp.

• push: Thêm một phần tử vào đầu ngăn xếp
• pop: Xóa một phần tử khỏi đầu ngăn xếp
• isEmpty: Kiểm tra xem ngăn xếp có trống không
• isFull: Kiểm tra xem ngăn xếp đã đầy chưa
• peek: Nhận giá trị của phần tử trên cùng mà không cần xóa nó

Cài đặt cấu trúc dữ liệu ngăn xếp

Để cài đặt được cấu trúc dữ liệu ngăn xếp thông thường chúng ta sẽ có 2 cách thức tiếp cận:

• Sử dụng mảng
• Sử dụng danh sách liên kết

Tùy thuộc vào chúng ta xây dựng ngăn xếp cho dữ liệu nào và từng bài toán cụ thể chúng ta sẽ lựa chọn cách cài đặt sao cho phù hợp

 

Cài đặt ngăn xếp sử dụng mảng

Chúng ta lấy một ví dụ đơn giản nhất là cần xây dựng cấu trúc dữ liệu ngăn xếp cho một số nguyên ta xây dựng cấu trúc như sau:

typedef struct {
    int data[50];
    int top;
} stack;

• Mảng dữ liệu data[50] là nơi lưu trữ dữ liệu
• Biến top được sử dụng để theo dõi phần tử trên cùng trong ngăn xếp.
• Khi khởi tạo ngăn xếp, chúng ta đặt giá trị của top thành -1 để có thể kiểm tra xem ngăn xếp có trống hay không bằng cách so sánh top == -1
• Khi đẩy một phần tử vào ngăn xếp, chúng ta tăng giá trị của top và đặt phần tử mới vào vị trí mà top chỉ đến.
• Khi lấy một phần tử, chúng tôi trả về phần tử được trỏ đến bởi top và giảm giá trị của nó.
• Trước khi đẩy vào ngăn xếp, chúng ta kiểm tra xem ngăn xếp đã đầy chưa?
• Trước khi lấy phần tử, chúng ta kiểm tra xem ngăn xếp đã trống chưa?

Cài đặt thao tác kiểm tra ngăn xếp rỗng (isEmpty)

Để cài đặt thao tác này chúng ta chỉ cần kiểm tra biến top như sau:

• Nếu top == -1 hoặc top < 0 có nghĩa là ngăn xếp rỗng -> trả về đúng (true/1)
• Nếu top >= 0 có nghĩa là ngăn xếp có phần tử -> trả về sai (false/0)

int isEmpty(stack *s){
    if (s->top == -1) {
        return 1;
    } else {
        return 0;
    }
}

Cài đặt thao tác kiểm tra ngăn xếp đầy (isFull)

Để cài đặt thao tác này chúng ta chỉ cần kiểm tra biến top như sau:

• Nếu top == 49 (do ta khai bảo mảng data[50]) có nghĩa là mảng đã sử dụng hết hay ngăn xếp đầy -> trả về đúng (true/1)
• Nếu top < 49 có nghĩa là ngăn xếp vẫn chưa đầy -> trả về sai (false/0)

int isFull(stack *s) {
    if (s->top == 49) {
        return 1;
    } else {
        return 0;
    }
}

Cài đặt thao tác đẩy một phẩn tử vào ngăn xếp (push)

Để thực hiện thao tác này ta làm các bước như sau:

• Kiểm tra ngăn xếp đã đầy hay chưa?
  • Nếu đầy thì không thêm được -> trả về sai (false/0)
  • Nếu không đầy thực hiện thao tác:
    • Tăng biến top lên 1 đơn vị
    • Gán giá trị mới vào phần tử thứ top của mảng data[top] = newValue
    • Trả về đúng (true/1)

int push(int value, stack *s){
    //Step 1:
    if(isFull(s)){
        //Step 2:
        return 0;
    }
    //Step 3:
    s->top += 1;
    //Step 4:
    s->data[s->top] = value;
    //Step 5:
    return 1;
}

Cài đặt thao tác lấy một phẩn tử trên đỉnh ngăn xếp và xóa phần tử đó (pop)

Để thực hiện thao tác này ta làm các bước như sau:

• Kiểm tra ngăn xếp có rỗng hay không?
  • Nếu rỗng thì không lấy ra được -> trả về sai (false/0)
  • Nếu không rỗng thực hiện thao tác:
    
    • Gán giá trị phần tử thứ top của mảng cho tham số topValue = data[top]
    • Giảm biến top đi 1 đơn vị
    • Trả về đúng (true/1)

int pop(int *topValue, stack *s){
    //Step 1:
    if(isEmpty(s)){
        //Step 2:
        return 0;
    }
    //Step 3:
    *topValue = s->data[s->top];
    //Step 4:
    s->top -= 1;
    //Step 5:
    return 1;
}

Tài liệu tham khảo

• Mã nguồn tham khảo: https://github.com/sinhdev/dsa/blob/master/Stack/StackUsingArray.c