顺序栈的表示和实现

2019-10-28  本文已影响0人  搬砖的猫

顺序栈是指利用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针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);    //返回栈顶元素的值,栈顶指针不变 
    }
} 

小结

由于顺序栈和顺序表一样,受到最大空间容量的限制,虽然可以在“满员”时重新分配空间扩大容量,但工作量较大,应该尽量避免。

上一篇下一篇

猜你喜欢

热点阅读