一、栈
栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。--百度百科
（类似于子弹夹，先压入的子弹最后才被发射出去，最后压入的子弹最先发射出去）
二、代码实现
#include<stdio.h> #include<stdlib.h> #include<malloc.h> //基于链表的动态栈 typedef struct node{ int data; struct node * pNext; }NODE,* PNODE; //设置指向栈顶的指针pTop，以及指向栈底（最下面的一个有效节点的下一个节点）的 指针pBottom typedef struct stack{ PNODE pTop; PNODE pBottom; }STACK,* PSTACK; //函数声明 void init(PSTACK pS); void push(PSTACK pS,int val); bool pop(PSTACK pS,int * pVal); void clear(PSTACK pS); void traverse(PSTACK pS); bool empty(PSTACK pS); int main(void) { STACK s; PSTACK pS = &s; int val; int * pVal = &val; init(pS); push(pS,1); push(pS,2); push(pS,3); push(pS,4); traverse(pS); if(pop(pS,pVal)) { printf("出栈成功，出栈元素为：%d ",*pVal); }else{ printf("出栈失败！！ "); } traverse(pS); clear(pS); traverse(pS); return 0; } //***************init()初始化栈**************************** void init(PSTACK pS) { pS->pTop = (PNODE)malloc(sizeof(NODE)); if(pS->pTop==NULL) { printf("动态内存分配失败！ "); exit(-1); }else{ pS->pBottom = pS->pTop; pS->pTop->pNext = NULL; } } //***************push()压栈***************************** void push(PSTACK pS,int val) { PNODE pNew = (PNODE)malloc(sizeof(NODE)); if(pNew==NULL) { printf("动态内存分配失败！ "); exit(-1); }else{ pNew->data = val; pNew->pNext = pS->pTop; pS->pTop = pNew; } } //***************traverse()遍历栈内元素**************************** void traverse(PSTACK pS) { PNODE p = pS->pTop; while(p!=pS->pBottom) { printf("%d ",p->data); p = p->pNext; } printf(" "); } bool pop(PSTACK pS,int * pVal) { if(empty(pS)) { return false; }else{ PNODE q = pS->pTop; *pVal = q->data; pS->pTop = q->pNext; free(q); q = NULL; } } //***************empty()判断栈是否为空**************************** bool empty(PSTACK pS) { if(pS->pTop==pS->pBottom) return true; else return false; } //***************clear()清空栈内元素，栈为空栈**************************** void clear(PSTACK pS) { if(empty(pS)) { printf("栈为空。。。 "); return; }else{ PNODE r1 = pS->pTop; PNODE r2 = NULL; while(r1!=pS->pBottom) { r2 = r1->pNext; free(r1); r1 = r2; } pS->pTop = pS->pBottom; printf("栈已被清空！！ "); } }
三、运行结果
四、应用
函数调用、中断、表达式求值、内存分配、缓冲处理、走迷宫等需要用到栈的知识，下面是一个可以利用栈“先进后出”特点写的一个可以
将十进制数转换成2-9进制数的函数。
#include<stdio.h> #include<stdlib.h> #include<malloc.h> //栈的应用--将十进制数转换成2-9进制数 //基于链表的动态栈 typedef struct node{ int data; struct node * pNext; }NODE,* PNODE; //设置指向栈顶的指针pTop，以及指向栈底（最下面的一个有效节点的下一个节点）的 指针pBottom typedef struct stack{ PNODE pTop; PNODE pBottom; }STACK,* PSTACK; //函数声明 void init(PSTACK pS); void push(PSTACK pS,int val); bool pop(PSTACK pS,int * pVal); void clear(PSTACK pS); void traverse(PSTACK pS); bool empty(PSTACK pS); //转换函数,将十进制数转换成2-9进制数，并输出 void transform(PSTACK pS,int num,int r); int main(void) { int num,r; STACK s; PSTACK pS = &s; init(pS); printf("请输入你想要转换的十进制数，num= "); scanf("%d",&num); printf("请输入你想要转换为几进制数，r= "); scanf("%d",&r); printf("十进制数 %d 被转换为：",num); transform(pS,num,r); return 0; } //***************init()初始化栈**************************** void init(PSTACK pS) { pS->pTop = (PNODE)malloc(sizeof(NODE)); if(pS->pTop==NULL) { printf("动态内存分配失败！ "); exit(-1); }else{ pS->pBottom = pS->pTop; pS->pTop->pNext = NULL; } } //***************push()压栈***************************** void push(PSTACK pS,int val) { PNODE pNew = (PNODE)malloc(sizeof(NODE)); if(pNew==NULL) { printf("动态内存分配失败！ "); exit(-1); }else{ pNew->data = val; pNew->pNext = pS->pTop; pS->pTop = pNew; } } //***************traverse()遍历栈内元素**************************** void traverse(PSTACK pS) { PNODE p = pS->pTop; while(p!=pS->pBottom) { printf("%d",p->data); p = p->pNext; } printf(" "); } //***************pop()出栈*************************** bool pop(PSTACK pS,int * pVal) { if(empty(pS)) { return false; }else{ PNODE q = pS->pTop; *pVal = q->data; pS->pTop = q->pNext; free(q); q = NULL; } } //***************empty()判断栈是否为空**************************** bool empty(PSTACK pS) { if(pS->pTop==pS->pBottom) return true; else return false; } //***************clear()清空栈内元素，栈为空栈**************************** void clear(PSTACK pS) { if(empty(pS)) { printf("栈为空。。。 "); return; }else{ PNODE r1 = pS->pTop; PNODE r2 = NULL; while(r1!=pS->pBottom) { r2 = r1->pNext; free(r1); r1 = r2; } pS->pTop = pS->pBottom; printf("栈已被清空！！ "); } } //*************void transform()转换函数,将十进制数转换成2-9进制数，并输出**************** void transform(PSTACK pS,int num,int r) { while(num!=0) { int yushu = (int)num%r; push(pS,yushu); num = num/r; } traverse(pS); }
运行结果：
