顺序栈的表示与实现

顺序栈是指利用顺序存储结构实现的栈，即用一组连续地址的存储单元依次存放到栈底到栈顶的数据元素。

-----------------------------------------------------------------

1.顺序栈的存储结构：（这里以存储整数为例）

1 typedef struct{
2   elemtype data[maxsize];//为顺序栈分配最大容量的内存
3   int top;  //指向栈顶
4 }sqstack;

------------------------------------

2.基本操作

1）初始化：

1 void initstack(sqstack &s)
2 {
3     if(!s.data) exit(-1);   //判断是否成功分配内存，如果s.data为null,则分配失败
4     s.top = 0;                //使top为零，指向栈底
5 }

2）入栈：

1 status push(sqstack &s,elemtype e)
2 {
3     if(s.top==maxsize) return error;    //判断是否栈满
4     s.data[s.top++] = e;                         //赋值
5     return ok;
6 }

3）出栈：

1 status pop(sqstack &s)
2 {
3    if(s.top<=0) return error;  //先判断栈是否空了
4    s.top--;                                //指针下移
5    return ok;
6 }

4）获得栈顶元素：

1 void gettop(sqstack s)
2 {
3     printf("栈顶元素是 %d\n",s.data[s.top-1]);
4 }

5)遍历（这个大都会用到，不算其基本操作）：

1 void traverse(sqstack s)
2 {
3     printf("遍历结果:\n");
4     for(int i=0;i<s.top;i++)
5     {
6         printf("%d ",s.data[i]);
7     }
8     printf("\n");
9 }

------------------------------------------------------------------

完整代码：

#include<stdio.h>
#include<stdlib.h>

#define maxsize 100
#define error 0
#define ok 1

typedef int status;
typedef int elemtype;

typedef struct{
  elemtype data[maxsize];//为顺序栈分配最大容量的内存
  int top;  //指向栈顶
}sqstack;

void initstack(sqstack &s)
{
    if(!s.data) exit(-1);
    s.top = 0;
}

status push(sqstack &s,elemtype e)
{
    if(s.top==maxsize) return error;
    s.data[s.top++] = e;
    return ok;
}

status pop(sqstack &s)
{
   if(s.top<=0) return error;
   s.top--;
   return ok;
}
void gettop(sqstack s)
{
    printf("栈顶元素是 %d\n",s.data[s.top-1]);
}

void traverse(sqstack s)
{
    printf("遍历结果:\n");
    for(int i=0;i<s.top;i++)
    {
        printf("%d ",s.data[i]);
    }
    printf("\n");
}

int main()
{
    sqstack s;

    initstack(s);

    int n;
    push(s,3);
    push(s,4);
    push(s,5);
    push(s,7);
    push(s,8);
    traverse(s);

    pop(s);
    pop(s);
    gettop(s);
    traverse(s);

    return 0;
}