栈是在链表的基础上删去一些功能，其本质仍是链表（程序"栈"）
更为准确的说栈的定义很广泛，“倒水的杯子”，“盛放物品的箱子”....均满足“后进先出”。
栈的相关应用有“括号配对问题”，链接： http://blog.csdn.net/u013806814/article/details/38593091
“火车进站问题”，链接：http://blog.csdn.net/u013806814/article/details/38636407
——参考《郝斌数据结构自学视频》、《数据结构C语言版》
ADT{
基本操作：
InitStack(&S)
操作结果：构造一个空栈S。
ClearStack(&S)
初始条件：栈S已存在。
操作结果：将S清为空栈。
Push(&S,e)栈S已存在。
初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop(&S,&e)
初始条件：栈S已存在且非空。
操作结果删除S的栈顶元素，并用e返回其值。
StackTraverse(S,visit())
初始条件：栈S已存在且非空。
操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit().
一旦visit()失败，则操作失败。
}ADT Stack
/*
目的：构造一个栈InitStack();
作用：可完成Push(压栈)、Pop(出栈)、StackTraverse(遍历栈)、StackEmpty(判断栈空)的操作。
*/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Node{
int date;
struct Node *next;
}NODE, *PNODE;
typedef struct Stack{
PNODE top;
PNODE base;
}STACK, *PSTACK;
/********栈的初始化******/
void InitStack(PSTACK pS){
pS->top = (PNODE)malloc(sizeof(NODE));
if(NULL == pS->top){
printf("内存分配失败！\n");
exit(-1);
}
else{
pS->base = pS->top;
pS->top->next = NULL;
}
}
/***********栈空**************/
int StackEmpty(PSTACK pS){
if(pS->base == pS->top){
return 1;
}
else return 0;
}
/************压栈*************/
void Push(PSTACK pS, int val){
PNODE pNew = (PNODE)malloc(sizeof(NODE));
pNew->date = val;
pNew->next = pS->top;
pS->top = pNew;
}
/*************遍历*************/
void StackTraverse(PSTACK pS){
PNODE p = pS->top;
while(p != pS->base){
printf("%d ",p->date);
p = p->next;
}
printf("\n");
return ;
}
/**************出栈***********/
bool Pop(PSTACK pS, int *pVal){
if(StackEmpty(pS)){
return 0;
}
else{
PNODE r = pS -> top;
*pVal = r -> date;
pS -> top = r -> next;
free(r);
r = NULL;
return 1;
}
}
/***********清空栈*************/
int ClearStack(PSTACK pS){
if(StackEmpty(pS)){
return 1;
}
else{
PNODE p = pS->top;
PNODE q;
while(p != pS->base){
q = p->next;
free(p);
p = q;
}
pS->base = pS->top;
return 1;
}
return 0;
}
int main(){
int val;
STACK S;
InitStack(&S);
Push(&S,1);
Push(&S,2);
Push(&S,3);
Push(&S,4);
Push(&S,5);
StackTraverse(&S);
if(Pop(&S,&val)){
printf("出栈成功，出栈元素是%d\n",val);
}
else{
printf("栈空，出栈失败\n!");
}
if(ClearStack(&S)){ //为了显示清空操作
printf("清空成功！\n");
}
StackTraverse(&S);
return 0;
}