栈的顺序存储结构及实现

栈的顺序存储结构

下标为 0 的一段作为栈底比较好，因为首元素都存在栈底，变化量最小。

/* 顺序栈结构 */
typedef struct
{
        SElemType data[MAXSIZE];
        int top; /* 用于栈顶指针 */
}SqStack;

如图所示，栈结构定义。定义一个变量来指示栈顶元素在数组中的位置，它可以来回移动，若存储栈的长度为StackSize ，则栈顶位置 top 必须小于 StackSize 。当栈存在一个元素时， top 等于 0。因此通常把空栈的判定条件定位 top 等于 -1。

栈的顺序存储结构——进栈操作

代码如下：

/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{
        if(S->top == MAXSIZE -1) /* 栈满 */
        {
                return ERROR;
        }
        S->top++;				/* 栈顶指针增加一 */
        S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */
        return OK;
}

栈的顺序存储结构——出栈操作

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{ 
        if(S->top==-1)
                return ERROR;
        *e=S->data[S->top];	/* 将要删除的栈顶元素赋值给e */
        S->top--;				/* 栈顶指针减一 */
        return OK;
}

两者没有涉及到任何循环语句，因此时间复杂度均是 O(1)。

两栈共享空间

栈有个缺陷：必须事先确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数组的容量，很麻烦。但是对于两个相同类型的栈，我们可以做到最大限度地利用其事先开辟的存储空间来进行操作。

如何利用一个数组存储两个栈？

• 做法：数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标 0 处，另一个栈为栈的末端，即下标为数组长度 n - 1处。这样，两个栈如果增加元素，就是两端向中间延伸。
  
  两栈共享空间的结构代码：

/* 两栈共享空间结构 */
typedef struct 
{
        SElemType data[MAXSIZE];
        int top1;	/* 栈1栈顶指针 */
        int top2;	/* 栈2栈顶指针 */
}SqDoubleStack;

除了要插入元素值参数外，还需要有一个判断是栈 1 还是 栈 2 的栈号参数 stackNumber 。插入元素的代码如下：

/* 插入元素e为新的栈顶元素 */
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
        if (S->top1+1==S->top2)	/* 栈已满，不能再push新元素了 */
                return ERROR;	
        if (stackNumber==1)			/* 栈1有元素进栈 */
                S->data[++S->top1]=e; /* 若是栈1则先top1+1后给数组元素赋值。 */
        else if (stackNumber==2)	/* 栈2有元素进栈 */
                S->data[--S->top2]=e; /* 若是栈2则先top2-1后给数组元素赋值。 */
        return OK;
}

对于两栈共享空间的 pop 方法，参数只是判断栈 1栈 2 的参数 stackNumber ，代码：

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{ 
        if (stackNumber==1) 
        {
                if (S->top1==-1) 
                        return ERROR; /* 说明栈1已经是空栈，溢出 */
                *e=S->data[S->top1--]; /* 将栈1的栈顶元素出栈 */
        }
        else if (stackNumber==2)
        { 
                if (S->top2==MAXSIZE) 
                        return ERROR; /* 说明栈2已经是空栈，溢出 */
                *e=S->data[S->top2++]; /* 将栈2的栈顶元素出栈 */
        }
        return OK;
}

不相同的栈，这种办法并不适用。