/*
不带头结点的链栈的操作集中包含的操作
说明：本版本在 main 函数里加入了 InitFlag 变量，用以识别传递的实参链表未初始化时的野指针问题。正常的操作时，这种情况应尽量避免，本版本没有刻意在操作里增加参数 InitFlag，目的是让操作更纯粹一些。在操作里加入，则操作的参数合法性审核会更健壮。根据需要选择吧。
1、初始化链栈S
Status InitStack_LS(LStack &S);
2、销毁链栈S
void DestroyStack_LS(LStack &S);
3、判断链栈S是否为空
Status StackEmpty_LS(LStack S);
4、清空链栈 S
void ClearStack_LS(LStack &S);
5、入栈操作
Status Push_LS(LStack &S,ElemType e);
6、出栈操作
Status Pop_LS(LStack &S,ElemType &e);
7、读取栈顶元素，并用 e 返回
Status GetTop_LS(LStack S, ElemType &e);
*/
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
// 数据元素的类型，使用时需根据问题的需求定义。
typedef int ElemType;
typedef struct LSNode{
ElemType data; // 数据域
struct LSNode* next; // 指针域
}LSNode,*LStack; // 结点和链栈类型
// 1、初始化链栈S
Status InitStack_LS(LStack &S){
S = NULL;
return OK;
}
// 2、销毁链栈S
void DestroyStack_LS(LStack &S){
LStack p = S;
LStack q = p;
while(p!=NULL){
p = q->next;
free(q);
q = p;
}
S = NULL; // 将 S 置空，避免指针悬挂
}
// 3、判断链栈S是否为空
Status StackEmpty_LS(LStack S){
if( S == NULL ){
return TRUE;
}else{
return FALSE;
}
}
// 4、清空链栈 S
void ClearStack_LS(LStack &S){
LStack p = S;
LStack q = p;
while(p!=NULL){
p = q->next;
free(q);
q = p;
}
S = NULL;
return OK;
}
// 5、入栈操作
Status Push_LS(LStack &S,ElemType e){
LSNode *t;
t = (LSNode*)malloc(sizeof(LSNode)); // 为元素e分配新的结点空间
if(t == NULL) return OVERFLOW; // 分配失败，返回
t->data = e;
t->next = S;
S = t; // 在栈顶位置插入新结点
return OK;
}
// 6、出栈
Status Pop_LS(LStack &S,ElemType &e){
LSNode *t;
if(S==NULL)return ERROR; // 判断栈 S 是否是空栈
t = S; // t 指向栈顶元素结点
e = S->data; // 用 e 返回栈顶元素值供外界使用
S = S->next; // 删除栈顶元素结点，栈顶指针S指向第二个结点
free(t); // 释放原栈顶结点的空间
return OK;
}
// 7、读取栈顶元素，并用 e 返回
Status GetTop_LS(LStack S, ElemType &e){
if(S == NULL) return ERROR;
e = S->data;
return OK;
}
int main(){
int i,e;
LStack S;
bool INITFLAG = FALSE; // 栈是否进行初始化标志
printf("1.初始化链栈\n");
printf("2.销毁链栈\n");
printf("3.判断链栈是否为空\n");
printf("4.清空链栈\n");
printf("5.将元素压入栈\n");
printf("6.栈顶元素出栈\n");
printf("7.取栈顶元素，并返回\n");
do{
printf("请输入你要进行的操作：\n");
scanf("%d",&i);
switch(i){
case 1 :
if(InitStack_LS(S) == OK){
printf("初始化成功\n");
INITFLAG = TRUE;
}else{
printf("初始化失败\n");
}
break;
case 2 :
if(INITFLAG == FALSE){
printf("参数错误或栈已销毁！\n");
}else{
DestroyStack_LS(S);
printf("栈已成功销毁。\n");
INITFLAG = FALSE;
}
break;
case 3 :
if(INITFLAG == FALSE){
printf("栈不存在，请先进行栈的初始化操作！\n");
}else{
if(StackEmpty_LS(S) == TRUE){
printf("链栈为空！\n");
}else{
printf("链栈不为空!\n");
}
}
break;
case 4 :
if(INITFLAG == FALSE){
printf("栈不存在，请先进行栈的初始化操作！\n");
}else{
ClearStack_LS(S);
printf("已为您清空链栈.\n");
}
break;
case 5 :
if(INITFLAG == FALSE){
printf("栈不存在，请先进行栈的初始化操作！\n");
}else{
printf("请输入要入栈的元素的值：\n");
scanf("%d",&e);
if(Push_LS(S,e) == OK){
printf("元素 %d 已成功入栈。\n",e);
}else{
printf("入栈失败！\n");
}
}
break;
case 6 :if(INITFLAG == FALSE){
printf("栈不存在，请先进行栈的初始化操作！\n");
}else{
if(Pop_LS(S, e) == OK){
printf("元素 %d 已成功出栈。\n",e);
}else{
printf("栈内没有元素，不能执行出栈操作！\n");
}
}
break;
case 7 :if(INITFLAG == FALSE){
printf("栈不存在，请先进行栈的初始化操作！\n");
}else{
if(GetTop_LS(S,e) == OK){
printf("取出栈顶元素的值：%d\n",e);
}else{
printf("栈内没有元素，不能执行读取栈顶元素操作！\n");
}
}
break;
}
}while(i>=1&&i<=7);
return 0;
}
