[数据结构与算法]数据结构-顺序栈的基础操作

?顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=0表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。 栈的顺序存储结构定义如下：

＃define  STACK_INIT_SIZE 100
＃define  STACKINCREMENT 10
＃define TRUE    1
＃define FALSE  0
typedef struct {
    SElemType  * base;
    SElemType  *top;
    int    stacksize;      //栈可使用的最大容量
} SqStack; 

按初始分配量进行第一次存储分配，base为栈底指针，始终指向栈底。top为栈顶指针，初值指向栈底，每插入一个元素，top增1；每删除一个元素，top减1，top始终在栈顶元素的下一个位置上。

????????进栈出栈示意图

(1) 初始化。

Status  InitStack (SqStack &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;
}

(2) 取栈顶元素

Status GetTop(SqStack S, SElemType &e){
    if (S.top = = S.base)  return  ERROR;
    e= *(S.top-1);
    return OK;

(3) 入栈

Status Push(SqStack &S, SElemType 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 OK;
} 

(4) 出栈

Status Pop(SqStack &S, SelemType &e){
    if( S.top= =S.base) return ERROR;
    e=*--S.top;
    return OK;
}

附录：完整测试代码

#include<iostream>
using namespace std;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define TURE 1
#define FALSE 0
typedef int SElemType;



typedef struct{
    SElemType *base;
    SElemType *top;
    int maxsize;
}SqStack;            //Sqtack 就是类型名

int InitStack(SqStack &S) // 初始化栈
{
    S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!S.base) return FALSE;
    S.top=S.base;
    S.maxsize=STACK_INIT_SIZE;
    return 1;
}
int GetTop(SqStack S,SElemType &e)  // 取栈顶元素
{
    if(S.top==S.base) return -1;
    e=*(S.top-1);
    return 1;
}
int Push(SqStack &s,SElemType e)  //压栈
{
    if(s.top-s.base==s.maxsize)
    {
        s.base=(SElemType*)realloc(s.base,(s.maxsize+STACK_INIT_SIZE)*sizeof(SElemType));
        if(!s.base) exit(0);
        s.top=s.base+s.maxsize;
        *s.top++=e;
        s.maxsize+=STACK_INIT_SIZE;
    }
    *s.top++=e;
    return 1;
}
int Pop(SqStack &S,SElemType &e)   // 出栈
{
    if(S.base==S.top) return -1;
    e=*--S.top;
    return 1;
}
void menu()
{
    cout<<"请输入你要执行的操作"<<endl;
    cout<<"初始化  :1"<<endl;
    cout<<"出栈    :2"<<endl;
    cout<<"入栈    :3"<<endl;
    cout<<"取栈顶元素:4"<<endl;
    cout<<"退出     :5"<<endl;
}

int main()
{
    SqStack S;
    while(true)
    {
        menu();
        int n,e=-1;
        scanf("%d",&n);
        switch (n)
        {
        case 1:
            InitStack(S);
            continue;
        case 2:
            Pop(S,e);
            printf("出栈元素%d\n\n",e);
            continue;
        case 3:
            cout<<"请输入元素";
            scanf("%d",&e);
            Push(S,e);
            continue;
        case 4:
            GetTop(S,e);
            printf("栈顶元素%d\n\n",e);
            continue;
        default:
            break;
        }
        if(n==5) exit(0);
    }
    return 0;
}