04 数据结构与算法之栈（C语言实现）

注：本文只给出C语言实现代码，涉及到的数据结构相关概念请自行阅读相关书籍或参考其他博文；

①版本1(数据采用顺序表存储方法)：

#include 
#include 
#include 

typedef struct Stack {
    int *data; //连续存储空间的首地址
    int top, capacity; //top栈顶位置， capacity栈容量
} Stack;

Stack *init_stack(int n) {
    Stack *s = (Stack *)malloc(sizeof(Stack));//用指针需要开辟栈存储空间，记录栈首地址
    s->data = (int *)malloc(sizeof(int) * n); //开辟一片连续的数据存储区域
    s->capacity = n;
    s->top = -1; //栈空
    return s;
}

void clear(Stack *s) {
    if (s == NULL) return ;
    free(s->data);
    free(s);
    return ;
}

int top(Stack *s) { //返回栈顶元素
    return s->data[s->top];
}

int empty(Stack *s) {//判空操作
    return s->top == -1;
}

int push(Stack *s, int val) {
    if (s == NULL) return 0;
    if (s->top == s->capacity - 1) return 0; //判断栈是否满了
    s->data[++(s->top)] = val;
    return 1;
}

int pop(Stack *s) {
    if (s == NULL) return 0;
    if (empty(s)) return 0;
    s->top -= 1;
    return 1;
}

void output(Stack *s) {
    if (s == NULL) return ;
    printf("stack(%d):[", s->top);
    for (int i = 0; i <= s->top; i++) {
        i && printf(",");
        printf("%d", s->data[i]);
    }
    printf("]n");
    return ;
}

int main(int argc, int **argv) {
    srand(time(0));
    #define MAX_OP 20
    Stack *s = init_stack(MAX_OP);
    for (int i = 0 ; i < MAX_OP; i++) {
        int op = rand() % 4;
        int val = rand() % 100;
        switch(op) {
            case 0: case 1: case 2: {
                printf("push %d to the stack = %dn", val, push(s, val));
            } break;
            case 3: {
                printf("pop %d from the stack = ", top(s));
                printf("%dn", pop(s)); //另起一行输出是因为不同编译器的操作顺序不同，同一行可能先执行pop再执行top
            } break;
        }
        output(s);
    }
    #undef MAX_OP
    clear(s);
    return 0;
}

②版本2(增加自动扩容)：

#include 
#include 
#include 

#define COLOR(a, b) "33[" #b "m" a "33[0m"
#define RED(a) COLOR(a, 32)
#define GREEN(a) COLOR(a, 33)

typedef struct Stack {
    int *data; //连续存储空间的首地址
    int top, capacity; //top栈顶位置， capacity栈容量
} Stack;

Stack *init_stack(int n) {
    Stack *s = (Stack *)malloc(sizeof(Stack));//用指针需要开辟栈存储空间，记录栈首地址
    s->data = (int *)malloc(sizeof(int) * n); //开辟一片连续的数据存储区域
    s->capacity = n;
    s->top = -1; //栈空
    return s;
}

void clear(Stack *s) {
    if (s == NULL) return ;
    free(s->data);
    free(s);
    return ;
}

int top(Stack *s) { //返回栈顶元素
    return s->data[s->top];
}

int empty(Stack *s) {//判空操作
    return s->top == -1;
}

int expand(Stack *s) {
    int extr_size = s->capacity;
    int *p;
    while (extr_size) {
        p = (int *)realloc(s->data, sizeof(int) * (s->capacity + extr_size));
        if (p) break; //扩容成功
        extr_size >>= 1; //扩容申请的内存空间不足时，将新容量减半继续申请
    }
    if (p == NULL) return 0; //申请失败；
    s->data = p;
    s->capacity += extr_size;
    printf(GREEN("expand successfully! the capacity is %dn"), s->capacity);
    return 1;
}

int push(Stack *s, int val) {
    if (s == NULL) return 0;
    if (s->top == s->capacity - 1) {
        if (!expand(s)) printf(RED("Failed to expand!n"));
    }
    s->data[++(s->top)] = val;
    return 1;
}

int pop(Stack *s) {
    if (s == NULL) return 0;
    if (empty(s)) return 0;
    s->top -= 1;
    return 1;
}

void output(Stack *s) {
    if (s == NULL) return ;
    printf("stack(%d):[", s->top);
    for (int i = 0; i <= s->top; i++) {
        i && printf(",");
        printf("%d", s->data[i]);
    }
    printf("]n");
    return ;
}

int main(int argc, int **argv) {
    srand(time(0));
    #define MAX_OP 20
    Stack *s = init_stack(1);
    for (int i = 0 ; i < MAX_OP; i++) {
        int op = rand() % 4;
        int val = rand() % 100;
        switch(op) {
            case 0: case 1: case 2: {
                printf("push %d to the stack = %dn", val, push(s, val));
            } break;
            case 3: {
                printf("pop %d from the stack = ", top(s));
                printf("%dn", pop(s)); //另起一行输出是因为不同编译器的操作顺序不同，同一行可能先执行pop再执行top
            } break;
        }
        output(s);
    }
    #undef MAX_OP
    clear(s);
    return 0;
}

③ 版本3(数据采用链式存储方法)：

#include 
#include 
#include 

//链式存储版
typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

typedef struct ListStack {
    StackNode *top;
    int size;
} ListStack;

StackNode *init_node(int val) {
    StackNode *p =(StackNode *)malloc(sizeof(StackNode));
    p->data = val;
    p->next = NULL;
    return p;
}

void clear_node(StackNode *node) {
    if (node == NULL) return ;
    free(node);
    return ;
}

ListStack *init_stack() {
    ListStack *s = (ListStack *)malloc(sizeof(ListStack));
    s->top = NULL;
    s->size = 0;
    return s;
}

void clear_ListStack(ListStack *s) {
    if (s == NULL) return ;
    StackNode *p = s->top, *q;
    while (p) {
        q = p->next;
        clear_node(p);
        p = q;
    }
    free(s);
    return ;
}

int empty(ListStack *s) {
    return s->top == NULL;
}

int top(ListStack *s) {
    if (empty(s)) return -1;
    return s->top->data;
}

int push(ListStack *s, int val) {
    if (s == NULL) return 0;
    StackNode *node = init_node(val);
    node->next = s->top;
    s->top = node;
    ++(s->size);
    return 1;
}

int pop(ListStack *s) {
    if (s == NULL) return 0;
    if (empty(s)) return 0;
    StackNode *p = s->top;
    s->top = p->next;
    clear_node(p);
    --(s->size);
    return 1;
}

void output(ListStack *s) {
    if (s == NULL) return ;
    printf("ListStack(%d): [", s->size);
    for (StackNode *p = s->top; p; p = p->next) {
        printf("%d->", p->data);
    }
    printf("NULL]n");
    return ;
}

int main(int argc, int **argv) {
    srand(time(0));
    #define MAX_OP 20
    ListStack *s = init_stack();
    for (int i = 0; i < MAX_OP; i++) {
        int op = rand() % 4;
        int val = rand() % 100;
        switch(op) {
            case 0: case 1: case 2: {
                printf("push %d to the ListStack = %dn", val, push(s, val));
            } break;
            case 3: {
                printf("pop %d from the ListStack = ", top(s));
                printf("%dn", pop(s));
            } break;
        }
        output(s), printf("n");
    }
    #undef MAX_OP
    clear_ListStack(s);
    return 0;
}