定义：一种可以实现“先进后出”的数据存储结构

分类：静态栈：以数组为内核        动态栈：以链表为内核 算法：入栈（压栈）/出栈 应用：函数调用、中断、表达式求职、内存分配、缓冲处理、迷宫 【参考程序】 #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\n", val); 　　} 　　else 　　{ 　　　　printf("出栈失败！\n"); 　　} 　　traverse(&S);   　　return 0; }   void init(PSTACK pS) { 　　pS->pTop = (PNODE)malloc(sizeof(NODE));//动态分配一块内存(在堆中分配)， 　　if(NULL == pS->pTop) 　　{ 　　　　printf("动态内存分配失败!\n"); 　　　　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\n", p->data); 　　　　p = p->pNext; 　　} 　　printf("\n"); }   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; 　　} }