3-3 栈的表示和操作的实现(1)

栈的类型定义：

ADT Stack {
	数据对象：
		D = {ai|ai∈ElemSet, i=1,2,...,n,n>=0}
	数据关系：
		R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}
	基本操作：初始化、进栈、出栈、取栈顶元素等
}ADT Stack

3-3 栈的操作实现(2)

顺序栈的表示和实现：

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

• 附设top指针，指示栈顶元素在顺序栈中的位置
• 附设base指针，指示栈底元素在顺序栈中的位置

但是，为了方便操作，通常top指针指示真正的栈顶元素之上的下标地址。

另外，用StackSize表示栈可使用最大容量

空栈：base==top是空栈标志

栈满：top-base==StackSize（如不溢出则top-base<StackSize）

栈满时想继续压入元素的处理方法：

1. 报错，返回操作系统
2. 分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈

使用数组作为顺序栈的存储方式的特点：