定义:一种可以实现“先进后出”的数据存储结构
分类:静态栈:以数组为内核 动态栈:以链表为内核
算法:入栈(压栈)/出栈
应用:函数调用、中断、表达式求职、内存分配、缓冲处理、迷宫
【参考程序历程】
#include <stdio.h> #include <malloc.h> #include <stdlib.h> typedef struct Node { int data; struct Node * pNext; }NODE, * PNODE; typedef struct Stack { PNODE pTop; PNODE pBottom; }STACK, * PSTACK; void init(PSTACK);//初始化 void push(PSTACK, int);//压栈 void traverse(PSTACK);//遍历 bool pop(PSTACK, int *);//出栈 void clear(PSTACK pS);//清除 int main(void) { STACK S; int val; init(&S);//创建一个空栈 push(&S, 1);//压栈 push(&S, 2);// push(&S, 3); push(&S, 4); push(&S, 5); push(&S, 6); traverse(&S);//遍历输出 clear(&S); if( pop(&S, &val) ) { printf("出栈成功,出栈元素为%d ", val); } else { printf("出栈失败! "); } traverse(&S); return 0; } void init(PSTACK pS) { pS->pTop = (PNODE)malloc(sizeof(NODE));//动态分配一块内存(在堆中分配), if(NULL == pS->pTop) { printf("动态内存分配失败! "); exit(-1); } else { pS->pBottom = pS->pTop; pS->pTop->pNext = NULL; } } void push(PSTACK pS, int val) { PNODE pNew = (PNODE)malloc(sizeof(NODE)); pNew->data = val; pNew->pNext = pS->pTop; pS->pTop = pNew; return; } void traverse(PSTACK pS) { PNODE p = pS->pTop; while(p != pS->pBottom) { printf("%d ", p->data); p = p->pNext; } printf(" "); } bool empty(PSTACK pS) { if(pS->pTop == pS->pBottom) return true; else return false; } bool pop(PSTACK pS, int * pVal) { if(empty(pS)) { return false; } else { PNODE r = pS->pTop; *pVal = r->data; pS->pTop = r->pNext; free(r); r = NULL; return true; } } void clear(PSTACK pS) { if(empty(pS)) { return; } else { PNODE p = pS->pTop; PNODE q = NULL; while(p != pS->pBottom) { q = p->pNext; free(p); p = q; } pS->pTop = pS->pBottom; } }