首页 计算机科学 数据结构 栈

# 顺序栈

# 1. 概念

顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。

顺序栈：顺序存储结构的栈称为顺序栈。

# 2. 定义

//1. 顺序栈的静态定义
#define MAXSIZE 1024
typedef struct
{
	ElemType data[MAXSIZE];
	int top;
}SqStack;
//2.顺序栈的动态定义
typedef struct{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

# 3. 静态栈的基本操作

当栈空：sq.top==0
入栈：sq.data[sq.top]=x; sq.top++;
出栈：sq.top--; x=sq.data[sq.top];
栈满：sq.top==Maxsize
上溢：当栈满时再做进栈运算时产生空间溢出称为上溢。出
错状态应当避免
下溢：当栈空时再做退栈运算也将产生溢出称为下溢。是正
常现象，可用作程序控制转移件
当栈空：sq.top==-1
入栈：sq.top++;sq.data[sq.top]=x;
出栈：x=sq.data[sq.top];sq.top--;
栈满：sq.top==Maxsize-1
上溢：当栈满时再做进栈运算时产生空间溢出称为上溢。出
错状态应当避免。
下溢：当栈空时再做退栈运算也将产生溢出称为下溢。是正
常现象，可用作程序控制转移件。

# 4. 动态栈的基本操作

栈空： sq.top == sq.base
栈满： sq.top-sq.base>=sq.stacksize
读栈顶元素： e = *(sq.top- 1)
入栈：*sq.top++ = e;
出栈: e = *--sq.top;

1) 初始化

Status InitStack (SqStack &S) {
	// 构造一个空栈 S
	S.base = (SElemType) *malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if (!S.base) exit (OVERFLOW); // 存储分配失败
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK;
}// InitStack

2) 读栈顶元素

Status GetTop(SqStack S, SELemType &e) {
	// 若栈不空，则用 e 返回 S 的栈顶元素并返回 0K; 否则返回 ERROR
	if(S.top == s.base) return ERROR;
	e = *(S.top- 1);
	return OK;
}// GetTop

3) 进栈

Status Push (SqStack &S, SElemType e){
	// 插入元素 e 为新的栈顶元素
	if(S.top - S.base >= S.stacksize) {// 栈满，追加存储空间
		S.base = (SElemType *) realloc (S.base,
		(S.stacksize + STACKINCREMENT)*sizeof(SElemType));
		if (!S.base) exit (OVERFLOW); // 存储分配失败
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*s.top++ =e;
	return 0K;
}// Push

4) 退栈

Status Pop (SqStack &S, SElenmType &e) {
	// 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回
	//0K; 否则返回 ERROR
	if(S.top == S.base) return EROR;
	e = * --S.top;
	return 0K;
}// Pop
-->