Bài 22.122 phút đọc

Ngăn xếp bằng mảng

Sau bài này bạn sẽ làm được

Cài đủ push, pop, peek, kiểm tra rỗng và đầy
Phân biệt tràn trên và tràn dưới
Chọn kiểu cho chỉ số top và tránh lỗi khi ngăn xếp rỗng
Giải thích vì sao ngăn xếp mảng nhanh hơn ngăn xếp liên kết

Ngăn xếp chỉ cho phép đụng vào một đầu duy nhất. Ràng buộc nghe có vẻ thiệt thòi đó lại chính là thứ làm nó hữu ích: nó khớp chính xác với cách lời gọi hàm, cách biểu thức lồng nhau, và cách mọi thứ có cấu trúc ngoặc hoạt động.

#LIFO và bốn thao tác

LIFO

Last In, First Out. Phần tử vào sau cùng là phần tử ra trước tiên. Như chồng đĩa: bạn đặt lên trên và lấy từ trên xuống.

Cả push và pop đều làm việc ở cùng một đầu, nên đều là O(1) và không phải dịch phần tử nào.

Thao tác	Ý nghĩa	Độ phức tạp
push	Đặt một phần tử lên đỉnh	O(1)
pop	Lấy phần tử đỉnh ra và bỏ nó khỏi ngăn xếp	O(1)
peek	Xem phần tử đỉnh mà không lấy ra	O(1)
rỗng	Hỏi ngăn xếp có phần tử nào không	O(1)

#Cài đặt bằng mảng

stack.h

#ifndef STACK_H
#define STACK_H

#include <stddef.h>

#define STACK_MAX 1000

/* Bất biến:
     1. -1 <= top < STACK_MAX
     2. Các phần tử hợp lệ là data[0] tới data[top]
     3. top == -1 nghĩa là rỗng                                */
typedef struct {
    int  data[STACK_MAX];
    long top;              /* chỉ số phần tử đỉnh, -1 khi rỗng */
} Stack;

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

#endif

stack.c

#include "stack.h"

void stack_khoi_tao(Stack *s)
{
    s->top = -1;
}

int stack_rong(const Stack *s)
{
    return s->top < 0;
}

int stack_day(const Stack *s)
{
    return s->top >= STACK_MAX - 1;
}

size_t stack_so_phan_tu(const Stack *s)
{
    return (size_t)(s->top + 1);
}

/* Trả về 0 nếu đẩy được, -1 nếu ngăn xếp đầy. */
int stack_push(Stack *s, int v)
{
    if (stack_day(s)) return -1;

    s->data[++s->top] = v;      /* tăng top TRƯỚC rồi ghi */

    return 0;
}

/* Trả về 0 nếu lấy được, -1 nếu ngăn xếp rỗng. */
int stack_pop(Stack *s, int *out)
{
    if (stack_rong(s)) return -1;

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

    --s->top;                   /* đọc TRƯỚC rồi giảm top */

    return 0;
}

int stack_peek(const Stack *s, int *out)
{
    if (stack_rong(s)) return -1;

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

    return 0;
}

Vì sao top là chỉ số phần tử đỉnh chứ không phải chỗ trống kế tiếp

Hai quy ước đều dùng được. Quy ước ở đây làm peek viết thẳng là data[top], còn quy ước kia làm push viết thẳng là data[top++] nhưng peek phải là data[top - 1].

/* Quy ước A: top là chỉ số phần tử đỉnh, rỗng khi top == -1 */
push: s->data[++s->top] = v;
peek: *out = s->data[s->top];
rong: s->top < 0

/* Quy ước B: top là chỉ số ô trống kế tiếp, rỗng khi top == 0 */
push: s->data[s->top++] = v;
peek: *out = s->data[s->top - 1];
rong: s->top == 0

Quy ước B có một ưu điểm thật: top chính là số phần tử, và nó dùng được kiểu size_t không dấu mà không cần giá trị âm. Với mã sản xuất thì B thường tốt hơn. Ở đây dùng A vì nó là quy ước phổ biến trong sách giáo khoa và trong nhiều mã nguồn.

#Chọn kiểu cho chỉ số top

size_t với giá trị canh SIZE_MAX

typedef struct {
    int    data[STACK_MAX];
    size_t top;                 /* không dấu */
} Stack;

void stack_khoi_tao(Stack *s) { s->top = (size_t)-1; }   /* SIZE_MAX */

int stack_rong(const Stack *s) { return s->top == (size_t)-1; }

Kiểu có dấu, hoặc dùng quy ước B

typedef struct {
    int  data[STACK_MAX];
    long top;                   /* có dấu, -1 nghĩa là rỗng */
} Stack;

void stack_khoi_tao(Stack *s) { s->top = -1; }

int stack_rong(const Stack *s) { return s->top < 0; }

Với size_t thì --s->top khi top bằng 0 cho ra SIZE_MAX, một con số khổng lồ, chứ không phải âm một. Điều đó không phải lỗi, vì kiểu không dấu quấn vòng có định nghĩa rõ ràng theo Bài 3.5. Nhưng nó biến một lỗi lập trình thành một giá trị hợp lệ khó nhận ra, và mọi phép so sánh top < 0 đều thành sai vĩnh viễn.

terminal

./top-khong-dau

sau khi pop tren stack rong:
top = 18446744073709551615
top < 0 ? khong
s->data[top] -> Segmentation fault (core dumped)

# Trình dò lỗi bắt được ngay

gcc -std=c17 -g -fsanitize=address,undefined top-khong-dau.c -o t-asan && ./t-asan

ERROR: AddressSanitizer: stack-buffer-overflow
READ of size 4 at 0x7ffd4c8a1234 thread T0
    #0 in stack_pop top-khong-dau.c:22

Cách tránh hẳn vấn đề: dùng quy ước B với size_t

typedef struct {
    int    data[STACK_MAX];
    size_t n;                   /* số phần tử, không bao giờ cần giá trị âm */
} Stack;

void stack_khoi_tao(Stack *s) { s->n = 0; }
int  stack_rong(const Stack *s) { return s->n == 0; }
int  stack_day(const Stack *s)  { return s->n >= STACK_MAX; }

int stack_push(Stack *s, int v)
{
    if (s->n >= STACK_MAX) return -1;

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

    return 0;
}

int stack_pop(Stack *s, int *out)
{
    if (s->n == 0) return -1;

    if (out != NULL) *out = s->data[s->n - 1];

    --s->n;

    return 0;
}

Bản này không cần giá trị canh nào, size_t tự nhiên vì số phần tử vốn không âm, và stack_so_phan_tu chỉ là trả về s->n. Đây là bản nên dùng trong dự án thật.

#Tràn trên và tràn dưới

Lỗi	Xảy ra khi	Hậu quả nếu không kiểm
Tràn trên	push khi ngăn xếp đã đầy	Ghi ra ngoài mảng, phá dữ liệu kề bên hoặc phá ngăn xếp lời gọi
Tràn dưới	pop hoặc peek khi ngăn xếp rỗng	Đọc data[-1], tức đọc ngoài mảng

Tràn trên là lỗ hổng bảo mật kinh điển

tran-tren.c

#define STACK_MAX 4

typedef struct {
    int  data[STACK_MAX];
    long top;
    long bi_mat;              /* nằm ngay sau mảng trong bộ nhớ */
} StackDeVo;

void push_khong_kiem(StackDeVo *s, int v)
{
    s->data[++s->top] = v;    /* không kiểm đầy */
}

int main(void)
{
    StackDeVo s = { { 0 }, -1, 0x1234 };

    for (int i = 0; i < 8; ++i) push_khong_kiem(&s, i);

    printf("bi_mat = 0x%lx\n", s.bi_mat);      /* đã bị ghi đè */

    return 0;
}

terminal

gcc -std=c17 -O0 tran-tren.c -o t && ./t

bi_mat = 0x7

gcc -std=c17 -g -fsanitize=address tran-tren.c -o t-asan && ./t-asan

ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffe1c8a2050
WRITE of size 4 at 0x7ffe1c8a2050 thread T0
    #0 in push_khong_kiem tran-tren.c:11

Đây chính xác là cơ chế của lỗ hổng tràn bộ đệm ngăn xếp mà Bài 11.7 đã nói. Chỉ cần một hàm push quên kiểm là kẻ tấn công ghi được vào biến kề bên, và trong trường hợp xấu là ghi được vào địa chỉ trả về của hàm.

Chương trình thử

main.c

#include <stdio.h>

#include "stack.h"

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

    stack_khoi_tao(&s);

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

    for (int i = 1; i <= 5; ++i)
        if (stack_push(&s, i * 10) != 0) { printf("day\n"); break; }

    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));

    return 0;
}

terminal

gcc -std=c17 -Wall -Wextra -g stack.c main.c -o t && ./t

pop tren stack rong : -1
peek tren stack rong: -1
so phan tu = 5
dinh = 50
lay ra: 50 40 30 20 10 
so phan tu = 0

Thứ tự lấy ra đúng là ngược với thứ tự đẩy vào. Đó là toàn bộ nội dung của chữ LIFO.

#Bản mảng tự lớn

Mảng cố định có giới hạn cứng. Ghép ý tưởng mảng động ở Bài 14.8 vào thì ngăn xếp lớn tùy ý mà vẫn giữ được ưu thế về bộ nhớ đệm so với danh sách liên kết.

stack-dong.h

#ifndef STACK_DONG_H
#define STACK_DONG_H

#include <stddef.h>

typedef struct {
    int   *data;
    size_t n;          /* số phần tử đang có */
    size_t suc_chua;   /* số phần tử chứa được */
} StackD;

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

#endif

stack-dong.c

#include <stdint.h>
#include <stdlib.h>

#include "stack-dong.h"

void stack_khoi_tao(StackD *s)
{
    s->data     = NULL;
    s->n        = 0;
    s->suc_chua = 0;
}

void stack_huy(StackD *s)
{
    free(s->data);
    stack_khoi_tao(s);
}

int stack_rong(const StackD *s)
{
    return s->n == 0;
}

/* Nhân đôi sức chứa khi hết chỗ. Trả về 0 nếu ổn. */
static int bao_dam(StackD *s)
{
    if (s->n < s->suc_chua) return 0;

    size_t moi = s->suc_chua ? s->suc_chua * 2 : 8;

    if (moi > SIZE_MAX / sizeof *s->data) return -1;      /* tránh tràn */

    int *tam = realloc(s->data, moi * sizeof *tam);

    if (tam == NULL) return -1;                           /* data cũ vẫn nguyên */

    s->data     = tam;
    s->suc_chua = moi;

    return 0;
}

int stack_push(StackD *s, int v)
{
    if (bao_dam(s) != 0) return -1;

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

    return 0;
}

int stack_pop(StackD *s, int *out)
{
    if (s->n == 0) return -1;

    if (out != NULL) *out = s->data[s->n - 1];

    --s->n;

    return 0;
}

int stack_peek(const StackD *s, int *out)
{
    if (s->n == 0) return -1;

    if (out != NULL) *out = s->data[s->n - 1];

    return 0;
}

Không thu nhỏ ngay khi pop

Thu nhỏ ở ngưỡng một nửa

int stack_pop(StackD *s, int *out)
{
    ...
    --s->n;

    if (s->n < s->suc_chua / 2)      /* thu nhỏ ngay khi xuống nửa */
        realloc(s->data, (s->suc_chua /= 2) * sizeof *s->data);

    return 0;
}

Ngưỡng một phần tư

/* Chỉ thu nhỏ khi xuống dưới MỘT PHẦN TƯ, và chỉ về một nửa. */
if (s->suc_chua > 8 && s->n < s->suc_chua / 4) {
    size_t moi = s->suc_chua / 2;
    int   *tam = realloc(s->data, moi * sizeof *tam);

    if (tam != NULL) { s->data = tam; s->suc_chua = moi; }
}

Với ngưỡng một nửa, một dãy push, pop, push, pop ngay tại mốc sẽ cấp phát lại mỗi lần, biến O(1) khấu hao thành O(n) mỗi thao tác. Để khoảng đệm giữa ngưỡng lớn lên và ngưỡng nhỏ đi thì hiện tượng đó biến mất.

Tự làm thử

Cài Stack mảng cố định theo cả hai quy ước top, rồi so xem bản nào ít chỗ dễ sai hơn.
Viết bản push không kiểm đầy, chạy dưới -fsanitize=address và đọc báo cáo tràn.
Cài StackD tự lớn, rồi in suc_chua sau mỗi lần push để thấy dãy 8, 16, 32.
Đo thời gian push một triệu phần tử vào StackD với hệ số lớn lên là 1.5, 2 và 4. Giải thích chênh lệch.
Cài stack_dao(StackD *s) đảo ngược ngăn xếp chỉ dùng thêm một ngăn xếp phụ, rồi thử với ngăn xếp rỗng và một phần tử.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

Ngăn xếp chỉ cho đụng vào một đầu, nên push, pop và peek đều là O(1) và không phải dịch phần tử nào.
Quy ước top là chỉ số ô trống kế tiếp kèm size_t tránh được giá trị canh âm và nên dùng trong mã thật.
Tràn trên là ghi ra ngoài mảng, một lỗ hổng bảo mật thật. Tràn dưới là đọc data[-1]. Cả hai chỉ tránh được bằng cách kiểm trước khi thao tác.
Hàm pop nên trả về mã lỗi và ghi giá trị qua tham số ra, vì không có giá trị int nào an toàn để làm dấu hiệu rỗng.
Bản mảng tự lớn cho push chi phí khấu hao O(1), và phải thu nhỏ ở ngưỡng một phần tư để tránh cấp phát lại liên tục.