栈的定义：
stack：一堆，一摞;堆；垛;
顺序栈和链栈的设计参考：
数据结构与算法基础（王卓）（7）：小结：关于链表和线性表的定义及操作_宇 -Yu的博客-CSDN博客
顺序栈：
前置条件：
（这里写的是线性表的构造形式，也可以写成链表的构造形式）
//基于线性表的定义所做的更改
#include<iostream>
using namespace std;
#include<stdlib.h>//存放exit
#include<math.h>//OVERFLOW,exit#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//#define OVERFLOW -2 #define MAXlength 100
//可按需修改，PPT中写的是MAXlengthstruct Poly
{float p;int e;bool operator==(Poly t){return t.p == p && t.e == e;}bool operator!=(Poly t){return t.p != p || t.e != e;}
};struct Sqlist
{Poly* elem;int length;
};typedef int Status;
typedef Poly Elemtype;
typedef Elemtype SElemType;
//注意：这一段必须写在调用SElemType类型及其指针之前struct SqStack
{SElemType* base; //栈底指针 SElemType* top;//栈顶指针int stacksize; //栈可用最大容量
};初始化：
Status InitStack(SqStack& S)//构造一个空栈
{S.base = new SElemType[MAXlength];//或//S.base = (SElemType*)malloc(MAXlength * sizeof(SElemType));if (!S.base) exit(OVERFLOW);// 存储分配失败S.top = S.base;//栈顶指针等于栈底指针S.stacksize = MAXlength;return true;
}简单操作：（求长度，是否为空，清空和销毁）
Status StackEmpty(SqStack S)
{// 若栈为空，返回TRUE；否则返回FALSE if (S.top == S.base)return TRUE;elsereturn FALSE;
}int StackLength(SqStack S)
{return S.top - S.base;
}Status ClearStack(SqStack S)//清空顺序栈
{if (S.base)S.top = S.base;return OK;
}Status DestroyStack(SqStack& S)//销毁
{if (S.base){delete S.base;S.stacksize = 0;S.base = S.top = NULL;}return OK;
}在这里，我们很容易产生这样的疑问：
关于清空和销毁，我们不是应该把元素一个一个置为NULL吗？？？
这里销毁和清空改变的只是指向这个位置的指针的值，可是没有把位置的内容置空（null）啊？？
实际原因解释如下：
清空：
这里我们其实只是让（将）栈回归到（置于）空栈的状态（两指针指向同一栈点）
至于栈的内容，清不清除其实都无所谓：
因为只要我们后面在写入元素，前面放在栈中没有被消除的元素自然都会被覆盖
销毁：
直接销毁base指针，这里我们或许会觉得：
你只不过是销毁base指针而已，你凭啥就说这样操作我们能实现销毁整个栈的内容和内存？
而事实上他确实办到了，至于原因，我们可以去看看该表的初始化操作：
在给该表初始化时，我们采用的操作是给base指针开辟内存空间：
S.base = new SElemType[MAXlength];
所以只要我们把base指针销毁就可以实现销毁整个栈的内容和内存的操作：
delete操作销毁了base指针内部的内容同时也销毁了以base指针作为头指针的整个栈的内存空间
压栈：
程序设计流程：
程序：
Status Push(SqStack& S, SElemType e)
{if (S.top-S.base==S.stacksize)//不是MAXlengthreturn OVERFLOW;*S.top = e;S.top++;//也可以写成：//*S.top++ = e;return true;
}ISSUES:
（1）：
注意，这里栈满的语句写的是：
if (S.top-S.base==S.stacksize)
其中的 S.stacksize 不能写 MAXlength
（2）：
关于 *S.top++ = e; 的优先级问题：
自增（算术运算符）的优先级大于赋值运算符
所以理论上说，这里应该是先自增，后运算
但是（然而），这里我们写的语句用的是：*S.top++
也就是说：在等到该语句中，所有其他操作都执行完成以后，再执行自增操作
所以才等价于先赋值，再自增
出栈：
程序设计流程：
程序：
Status Pop(SqStack& S, SElemType& e)
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK; 否则返回ERROR
{if (S.top == S.base) // 等价于 if(StackEmpty(S))return UNDERFLOW;//ERROR;e = *S.top;S.top--;//e = *--S.top;return true;
}同样的，这里先赋值，后自减；
这里不再赘述
链栈：
前置条件：
//基于链表的定义所做的更改
#include<iostream>
using namespace std;
#include<stdlib.h>//存放exit#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//#define OVERFLOW -2 #define MAXlength 100 //初始大小为100，可按需修改struct K//Poly
{float a;int b;string c;bool operator==(K& t){return t.a == a && t.b == b;//&& t.c = c;}bool operator!=(K& t){return t.a != a || t.b != b;//|| t.c = c;}
};
typedef K Elemtype; //函数调用状态struct Lnode//node:结; 结点;
{Elemtype data;Lnode* next;
};
typedef Lnode* LinkList;typedef int Status;
typedef K Elemtype;
typedef Elemtype SElemType;
//注意：这一段必须写在调用SElemType类型及其指针之前struct StackNode
{SElemType data;StackNode* next;
};
typedef StackNode *LinkStack;
LinkStack S;其中：（模块构造解析）
SElemType：Poly（复合）型
top，base：SElemType型指针
另外，在这里我们需要注意，定义结构体时可以实现嵌套自身，本质上就像：
#include<iostream>
using namespace std;struct S
{int data;S* next;
};int main()
{}简单操作：（初始化、是否为空、取栈顶元素）
int InitStack(LinkStack& S)
{//构造一个空栈，栈顶指针置为空S = NULL;return OK;
}Status StackEmpty(LinkStack S)
{if (S == NULL)return TRUE;else return FALSE;
}SElemType GetTop(LinkStack S)
{if (S != NULL)return S->data;
}入栈：
Status Push(LinkStack& S, SElemType e)
{StackNode* p = new StackNode;p->data = e;p->next = S;S = p;return true;
}出栈：
我写的：
Status Pop(LinkStack& S, SElemType e)
{LinkStack p = S;e = p->data;S = p->next;delete p;return true;
}参考PPT，我们可以发现，做出如下改动会更好更严谨：
加上语句：
if (S == NULL) return ERROR;
返回的e为引用类型
最终版：
Status Pop(LinkStack& S, SElemType &e)
{if (S == NULL) return ERROR;LinkStack p = S;e = p->data;S = p->next;delete p;return true;
}
