链栈顾名思义，采用链表实现，其优点是不存在栈满上溢出的情况，其操作都是在头结点之后进行的，入栈类似与头插法建立链表。
非空链式栈的一般形式缺点：进出栈时间开销大，进栈需要找到最后一个结点，出栈时删除最后一个结点。
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);
}
