链栈

链栈顾名思义，采用链表实现，其优点是不存在栈满上溢出的情况，其操作都是在头结点之后进行的，入栈类似与头插法建立链表。

非空链式栈的一般形式缺点：进出栈时间开销大，进栈需要找到最后一个结点，出栈时删除最后一个结点。

stack.png
解决办法：将指针次序颠倒过来，top指向an
stack.png
1.进栈时将新结点作为首结点；
2.出栈时删除首结点。
优点：进出栈时间开销为常数。

数据结构

#include <stdlib.h>
typedef int ElemType;
typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
}StackNode, *ListStack;

初始化

//初始化建立空栈
void stack_init(ListStack *stack) {
    *stack = (StackNode *)malloc(sizeof(StackNode));
    (*stack)->next = NULL;
}

结点

//创建结点
ListStack NewStackNonde(ElemType data) {
    ListStack new = (StackNode *)malloc(sizeof(StackNode));
    new->data = data;
    new->next = NULL;
    return new;
}

判空

//判空
int stack_empty(ListStack stack) {
    if (stack->next == NULL) {
//        printf("空栈...\n");
        return 0;
    }
    else {
        printf("非空栈...\n");
        return -1;
    }
}

进栈

//入栈
void stack_push(ListStack *stack, ElemType data) {
    ListStack new = NewStackNonde(data);
    new->next = (*stack)->next;
    (*stack)->next = new;
}

出栈

//出栈
int stack_pop(ListStack *stack) {
    if ((*stack)->next == NULL) {
//        printf("空栈...\n");
        return -1;
    }
    else {
        int tmp;
        ListStack s = (*stack)->next;
        tmp = s->data;
        (*stack)->next = s->next;
        free(s);//释放空间
        return tmp;
    }
}

获取栈顶元素

//获取栈顶元素
int stack_get(ListStack *stack) {
    ListStack s = (*stack)->next;
    if (s == NULL) {
        printf("空栈...\n");
        return -1;
    }
    int data = s->data;
    return data;
}

销毁栈

//销毁栈
void stack_destroy(ListStack *stack) {
    ListStack p = *stack;
    while (p != NULL) {
        *stack = (*stack)->next;
        free(p);
        p = *stack;
    }
}

进制转换

//进制转换 N传入需要转换进制的数， d需要转换的进制，2，8，16
void conversion(ListStack *stack, unsigned int N, const unsigned int d) {
    if (*stack == NULL) {//当传入参数为指针
        exit(-1);
    }
    int tmp;//保存mod=N%d;
    printf("...将10进制的%d转化为%d进制后...", N, d);
    while (N) {
        tmp = N % d;
        stack_push(stack, tmp);
        N = N / d;
    }
    int data;
    while ((data=stack_pop(stack)) >= 0) {
        printf("%d", data);
    }
    printf("\n");
}

测试

//测试
void test_stack_link() {
    StackNode node;
    ListStack top = &node;
    stack_init(&top);
//    stack_empty(top);
//    stack_push(&top, 23);
//    stack_push(&top, 34);
//    stack_push(&top, 45);
//    stack_push(&top, 60);
//    printf("%d\n", stack_get(&top));
//    stack_pop(&top);
//    printf("%d\n", stack_get(&top));
//    stack_destroy(&top);
    conversion(&top, 16, 16);
}