Ngăn xếp bằng danh sách liên kết

#ifndef STACK_LK_H
#define STACK_LK_H

#include <stddef.h>

typedef struct SNode {
    int           data;
    struct SNode *next;
} SNode;

/* Bất biến:
     1. top == NULL  khi và chỉ khi  size == 0
     2. size == số nút đi được từ top theo next
   Không cần con trỏ đáy: mọi thao tác chỉ đụng vào đỉnh.        */
typedef struct {
    SNode *top;
    size_t size;
} StackLK;

void   stack_khoi_tao(StackLK *s);
void   stack_huy(StackLK *s);
int    stack_rong(const StackLK *s);
size_t stack_so_phan_tu(const StackLK *s);
int    stack_push(StackLK *s, int v);
int    stack_pop(StackLK *s, int *out);
int    stack_peek(const StackLK *s, int *out);

#endif

#include <stdlib.h>

#include "stack-lk.h"

void stack_khoi_tao(StackLK *s)
{
    s->top  = NULL;
    s->size = 0;
}

int stack_rong(const StackLK *s)
{
    return s->top == NULL;
}

size_t stack_so_phan_tu(const StackLK *s)
{
    return s->size;
}

/* Trả về 0 nếu ổn, -1 nếu hết bộ nhớ. Không bao giờ đầy vì lý do khác. */
int stack_push(StackLK *s, int v)
{
    SNode *n = malloc(sizeof *n);

    if (n == NULL) return -1;

    n->data = v;
    n->next = s->top;      /* nút mới trỏ vào đỉnh cũ */
    s->top  = n;           /* nút mới thành đỉnh */

    ++s->size;

    return 0;
}

int stack_pop(StackLK *s, int *out)
{
    if (s->top == NULL) return -1;

    SNode *n = s->top;

    if (out != NULL) *out = n->data;

    s->top = n->next;      /* đọc next TRƯỚC khi free */

    free(n);
    --s->size;

    return 0;
}

int stack_peek(const StackLK *s, int *out)
{
    if (s->top == NULL) return -1;

    if (out != NULL) *out = s->top->data;

    return 0;
}

void stack_huy(StackLK *s)
{
    while (stack_pop(s, NULL) == 0) { }
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 5000000

/* --- Bản mảng động --- */
typedef struct { int *d; size_t n, cap; } SA;

static int sa_push(SA *s, int v)
{
    if (s->n == s->cap) {
        size_t moi = s->cap ? s->cap * 2 : 8;
        int   *t   = realloc(s->d, moi * sizeof *t);

        if (t == NULL) return -1;

        s->d = t; s->cap = moi;
    }

    s->d[s->n++] = v;

    return 0;
}

/* --- Bản liên kết --- */
typedef struct SNode { int data; struct SNode *next; } SNode;
typedef struct { SNode *top; } SL;

static int sl_push(SL *s, int v)
{
    SNode *n = malloc(sizeof *n);

    if (n == NULL) return -1;

    n->data = v; n->next = s->top; s->top = n;

    return 0;
}

int main(void)
{
    SA a = { NULL, 0, 0 };
    SL l = { NULL };

    clock_t t0 = clock();

    for (int i = 0; i < N; ++i) if (sa_push(&a, i) != 0) return 1;

    double g_a = (double)(clock() - t0) / CLOCKS_PER_SEC;

    t0 = clock();

    for (int i = 0; i < N; ++i) if (sl_push(&l, i) != 0) return 1;

    double g_l = (double)(clock() - t0) / CLOCKS_PER_SEC;

    /* Đo cả pop, tức duyệt ngược */
    long long tong = 0;

    t0 = clock();

    while (a.n > 0) tong += a.d[--a.n];

    double p_a = (double)(clock() - t0) / CLOCKS_PER_SEC;

    t0 = clock();

    while (l.top != NULL) {
        SNode *t = l.top->next;

        tong += l.top->data;
        free(l.top);
        l.top = t;
    }

    double p_l = (double)(clock() - t0) / CLOCKS_PER_SEC;

    printf("push mang      : %.3f s\n", g_a);
    printf("push danh sach : %.3f s  (%.1f lan cham hon)\n", g_l, g_l / g_a);
    printf("pop  mang      : %.3f s\n", p_a);
    printf("pop  danh sach : %.3f s  (%.1f lan cham hon)\n", p_l, p_l / p_a);
    printf("bo nho mang    : %zu byte\n", a.cap * sizeof *a.d);
    printf("bo nho danh sach: %zu byte\n", (size_t)N * 32);
    printf("(tong %lld)\n", tong);

    free(a.d);

    return 0;
}

#include <stdio.h>

#include "stack-lk.h"

int main(void)
{
    StackLK s;
    int     v;

    stack_khoi_tao(&s);

    printf("pop tren rong: %d\n", stack_pop(&s, &v));

    for (int i = 1; i <= 5; ++i)
        if (stack_push(&s, i * 10) != 0) { stack_huy(&s); return 1; }

    printf("so phan tu   : %zu\n", stack_so_phan_tu(&s));

    stack_peek(&s, &v);
    printf("dinh         : %d\n", v);

    printf("lay ra       : ");

    while (stack_pop(&s, &v) == 0) printf("%d ", v);

    printf("\nso phan tu   : %zu\n", stack_so_phan_tu(&s));

    /* Đẩy lại rồi hủy giữa chừng để kiểm rò rỉ */
    for (int i = 0; i < 1000; ++i)
        if (stack_push(&s, i) != 0) { stack_huy(&s); return 1; }

    stack_huy(&s);
    stack_huy(&s);      /* gọi lần hai vẫn an toàn */

    return 0;
}