顺序栈是指利用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。
顺序栈的定义
//------顺序栈的存储结构------
#define MAXSIZE 100 //顺序栈存储空间的初始分配量
typedef struct{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //栈可用的最大容量
}SqStack;
顺序栈的初始化
(1)为顺序栈动态分配一个最大容量为MAXSIZE的数组空间,使base指向这段空间的基地址,即栈底。
(2)栈顶指针top初始为base,表示栈为空。
(3)stacksize置为栈的最大容量MAXSIZE。
//顺序栈的初始化
Status InitStack(SqStack &S){
//构造一个空栈
S.base = new SElemType[MAXSIZE]; //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
if(! S.base){
exit(OVERFLOW); //存储分配失败
}
S.top = S.base; //top初始为base,空栈
S.stacksize = MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
return OK;
}
顺序栈的入栈
(1)判断栈是否满,若满则返回ERROR。
(2)将新元素压入栈顶,栈顶指针加1。
//顺序栈的入栈
Status Push(SqStack &S, SElemType e){
//插入元素e为新的栈顶元素
if(S.top - S.base == S.stacksize){ //栈满
return ERROR;
}
*S.top ++ = e; //元素e压入栈顶,栈顶指针加1
return OK;
}
顺序栈的出栈
(1)判断栈是否空,若空则返回ERROR。
(2)栈顶指针减1,栈顶元素出栈。
//顺序栈的出栈
Status Pop(SqStack &S, SElemType e){
//删除S的栈顶元素,用e返回其值
if(S.top == S.base){ //栈空
return ERROR;
}
e == *--S.top; //栈顶指针减1,将栈顶元素赋给e
return OK;
}
取顺序栈的栈顶元素
//取顺序栈的栈顶元素
SElemType GetTop(SqStack S){
//返回S的栈顶元素,不修改栈顶指针
if(S.top != S.base){ //栈非空
return *(S.top - 1); //返回栈顶元素的值,栈顶指针不变
}
}
小结
由于顺序栈和顺序表一样,受到最大空间容量的限制,虽然可以在“满员”时重新分配空间扩大容量,但工作量较大,应该尽量避免。
网友评论