4.4　栈的顺序存储结构及实现

4.4.1　栈的顺序存储结构

既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。线性表是用数组来实现的，想想看，对于栈这种只能一头插入删除的线性表来说，用数组哪一端来作为栈顶和栈底比较好？

对，没错，下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底。

我们定义一个top变量来指示栈顶元素在数组中的位置，这top就如同中学物理学过的游标卡尺的游标，如图4-4-1，它可以来回移动，意味着栈顶的top可以变大变小，但无论如何游标不能超出尺的长度。同理，若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判定条件定为top等于-1。

4.4　栈的顺序存储结构及实现 - 图1

图4-4-1

来看栈的结构定义

  1. /* SElemType类型根据实际情况而定，这里假设为int */
  2. typedef int SElemType;    
  3. typedef struct
  4. {
  5.     SElemType data[MAXSIZE];
  6.     /* 用于栈顶指针 */
  7.     int top;              
  8. }SqStack;

若现在有一个栈，StackSize是5，则栈普通情况、空栈和栈满的情况、空栈和栈满的情况示意图如图4-4-2所示。

4.4　栈的顺序存储结构及实现 - 图2

图4-4-2

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

对于栈的插入，即进栈操作，其实就是做了如图4-4-3所示的处理。

4.4　栈的顺序存储结构及实现 - 图3

图4-4-3

因此对于进栈操作push，其代码如下：

  1. /* 插入元素e为新的栈顶元素 */
  2. Status Push(SqStack *S, SElemType e)
  3. {
  4.     /* 栈满 */
  5.     if (S->top == MAXSIZE - 1)    
  6.     {
  7.         return ERROR;
  8.     }
  9.     /* 栈顶指针增加一 */
  10.     S->top++;                     
  11.     /* 将新插入元素赋值给栈顶空间 */
  12.     S->data[S->top] = e;          
  13.     return OK;
  14. }

4.4.3　栈的顺序存储结构——出栈

操作

出栈操作pop，代码如下：

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

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