【顺序栈的表示和实现，顺序栈的初始化，是否为空，清空顺序栈，销毁顺序栈，】

一、栈和队列的定义和特点

栈和队列是限定插入和删除只能在表的==“端点”==进行的线性表。

栈是先进后出。
队列是先进先出。
栈（stack）是一个特殊的线性表，是限定仅在一端（通常是在表尾）。

1.1顺序栈的表示和实现

存储方式：同一般线性表的顺序存储结构完全相同。
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端
附设top指针，指示栈顶元素在顺序栈的位置。
附设base指针，指示栈底元素在顺序栈中的位置。

用stacksize表示栈可使用的最大容量。

①先建立一个空栈：base == top 是空栈的标志。

②A进栈，top指向下一个进栈点。

③依次进栈,最后top指针指向的top在最上面的一个栈点。栈满的标志：top-base=stacksize
后面不能在插入元素，再插入就溢出了。上溢。
栈满时候的处理方法：1.报错，返回操作系统。2.分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈。

④出栈，每出栈一个元素top指针就下移一个。

⑤最后没有可出栈的元素还要继续出栈的话就会发生下溢。
总结：使用数组作为顺序栈的存储方式的特点：
简单，方便，但易产生溢出（数组元素固定）。

• 上溢：栈已经满了，又要压入元素。
• 下溢：栈已空，还要弹出元素。

1.2顺序栈的基本操作

//顺序栈的表示
typedef struct{
	SElemType* base;//栈底指针
	SElemType* top;//栈顶指针
	int stacksize;//栈的最大容量
}SqStack;
1
2
3
4
5
6

注:stacksize:5;top:2;base:0;栈中元素个数=top-base=2。
当top-base=stacksize时，说明栈满了。

1.2.1顺序栈的初始化

//顺序栈的初始化
int InitStack(SqStack& S) {
	//构造一个空栈
	S.base = new SElemType[MAXSIZE];
	if (!S.base) {//分配存储失败
		exit(0);
	}
	S.top = S.base;//栈顶指针等于栈顶指针
	S.stacksize = MAXSIZE;
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11

1.2.2判断顺序栈是否为空

//顺序栈是否为空
bool StackEmpty(SqStack S) {
	//若栈为空，返回TRUE，否则返回FALSE
	if (S.top == S.base) {
		return true;
	}
	else {
		return false;
	}
}
1
2
3
4
5
6
7
8
9
10

1.2.3清空顺序栈

//清空顺序栈
int ClearStack(SqStack S) {
if (S.base) {
S.top = S.base = 0;//这里是将栈顶和栈底都置为0；
return 1;
}
}

1.2.4销毁顺序栈

//销毁顺序栈
int DestroyStack(SqStack& S) {
	if (S.base) {
		delete S.base;//先销毁栈底指针
		S.stacksize = 0;//再将栈的容量设为0
		S.base = S.top = NULL;//再将栈底栈顶设为空
	}
	return 1;
}
1
2
3
4
5
6
7
8
9

1.2.5顺序栈的入栈

//顺序栈的入栈
int Push(SqStack& S, SElemType e) {
	if (S.top - S.base == S.stacksize) {//栈满
		return 0;
	}
	*S.top++ = e;
	//相当于*S.top=e;S.top++;
	return 1;
	}
1
2
3
4
5
6
7
8
9