Ngăn xếp tổng quát

Thuộc phần Lập trình hướng đối tượng trong hành trình C của Coddy. Bài học 60 trên 61.

Thử thách

Dễ

Ngăn xếp là một cấu trúc dữ liệu cơ bản tuân theo nguyên tắc vào sau, ra trước (Last-In-First-Out, LIFO): phần tử được thêm vào sau cùng sẽ được lấy ra đầu tiên. Hãy hình dung một chồng đĩa: bạn thêm đĩa lên trên cùng và lấy đĩa từ trên cùng.

Hãy xây dựng một ngăn xếp tổng quát: một cấu trúc dữ liệu linh hoạt có thể lưu trữ mọi kiểu dữ liệu bằng các con trỏ void*. Ngăn xếp của bạn sẽ tuân theo nguyên tắc vào sau, ra trước và có đầy đủ các thao tác thiết yếu.

Bạn sẽ sắp xếp code trong ba tệp:

stack.h: Định nghĩa struct Stack với ba thành viên: một mảng void** để lưu các phần tử, một int làm chỉ số đỉnh (vị trí trống tiếp theo) và một int làm sức chứa. Khai báo nguyên mẫu các hàm để tạo ngăn xếp (nhận sức chứa), thêm một phần tử, lấy một phần tử ra, xem phần tử trên cùng, kiểm tra ngăn xếp có rỗng không và giải phóng ngăn xếp.
stack.c: Cài đặt ngăn xếp tổng quát của bạn:
- create_stack: cấp phát một Stack trên heap, cấp phát mảng phần tử với sức chứa đã cho, khởi tạo top bằng 0 và trả về con trỏ
- push: thêm một phần tử lên đỉnh nếu còn chỗ (khi top nhỏ hơn capacity)
- pop: lấy và trả về phần tử trên cùng, hoặc trả về NULL nếu ngăn xếp rỗng
- peek: trả về phần tử trên cùng mà không lấy nó ra, hoặc trả về NULL nếu ngăn xếp rỗng
- is_empty: trả về 1 nếu ngăn xếp không có phần tử nào, ngược lại trả về 0
- free_stack: giải phóng mảng phần tử trước, sau đó giải phóng chính struct Stack
main.c: Đọc số thao tác cần thực hiện. Sau đó, với mỗi thao tác, đọc một lệnh: push theo sau là một giá trị số nguyên, pop hoặc peek. Tạo ngăn xếp có sức chứa 10. Với push, cấp phát một số nguyên trên heap rồi thêm con trỏ của nó vào ngăn xếp. Với pop, lấy phần tử ra, in giá trị của nó rồi giải phóng số nguyên. Với peek, in giá trị mà không lấy phần tử ra. Nếu gọi pop hoặc peek khi ngăn xếp rỗng, hãy in empty. Sau khi thực hiện tất cả thao tác, giải phóng mọi phần tử còn lại và ngăn xếp.

Chương trình của bạn sẽ nhận:

Số thao tác
Mỗi thao tác trên một dòng riêng (push X, pop hoặc peek)

Đầu ra ví dụ khi đầu vào là 5, sau đó là push 10, push 20, peek, pop, pop:

20
20
10

Đầu ra ví dụ khi đầu vào là 3, sau đó là pop, push 42, peek:

empty
42

Đầu ra ví dụ khi đầu vào là 4, sau đó là push 5, push 15, pop, pop:

15
5

Hãy nhớ rằng ngăn xếp lưu các con trỏ void*: bên gọi chịu trách nhiệm cấp phát và giải phóng dữ liệu thực tế. Khi lấy phần tử ra, hãy ép kiểu void* được trả về thành int* để truy cập giá trị. Dùng strcmp từ <string.h> để so sánh các chuỗi lệnh.

Tự làm thử

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

int main() {
    int n;
    scanf("%d", &n);
    
    // TODO: Tạo ngăn xếp (stack) có sức chứa 10
    
    // TODO: Xử lý từng thao tác
    for (int i = 0; i < n; i++) {
        char command[10];
        scanf("%s", command);
        
        if (strcmp(command, "push") == 0) {
            int value;
            scanf("%d", &value);
            // TODO: Cấp phát một số nguyên trên vùng nhớ heap rồi push con trỏ của nó vào ngăn xếp
        }
        else if (strcmp(command, "pop") == 0) {
            // TODO: Lấy phần tử ra khỏi ngăn xếp
            // - Nếu khác NULL, in ra giá trị và giải phóng bộ nhớ của số nguyên
            // - Nếu là NULL (ngăn xếp rỗng), in ra "empty"
        }
        else if (strcmp(command, "peek") == 0) {
            // TODO: Xem phần tử trên cùng của ngăn xếp
            // - Nếu khác NULL, in ra giá trị (không lấy phần tử ra hoặc giải phóng bộ nhớ)
            // - Nếu là NULL (ngăn xếp rỗng), in ra "empty"
        }
    }
    
    // TODO: Giải phóng bộ nhớ của các phần tử còn lại trong ngăn xếp
    // TODO: Giải phóng bộ nhớ của chính ngăn xếp
    
    return 0;
}