3.4 顺序栈的表示和实现

• 由于栈本身就是线性表，于是栈也有顺序存储和链式存储两种实现方式
  • 栈的顺序存储——顺序栈
  • 栈的链式存储——链栈

顺序栈的表示和实现

存储方式：同一般线性表的顺序存储结构完全相同，
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低端地址。

• 附设top指针，指示栈顶元素在顺序栈中的位置。
• 另设base指针，指示栈底元素在顺序栈中的位置。
  但是，为了方便操作，通常top指示真正的栈顶元素之上的下标地址。
• 另外，用stackSize表示栈可使用的最大容量
• 例如：如下图所示
  

空栈：base==top 是栈空的标志
栈满时的处理方法：
1、报错返回
2、分配更大的空间，作为栈的存储空间， 将原栈的内容移入新栈。

使用数组作为顺序栈存储方式的特点：
简单、方便、但易产生溢出（数组大小固定）

• 上溢（overflow）：栈已经满，又要压入元素
• 下溢（underflow）：栈已经空，还要弹出元素。

注意：上溢是一种错误， 是问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束。

顺序栈的表示

#define  MaxSize 100
typedef struct {
  SElemType  *base;  // 栈底指针
  SElemType  *top;   // 栈顶指针
  int stackSize;     // 栈的最大容量
}SqStack;

顺序栈初始化

• 【算法描述】

  Status InitStack(SqStack &S){   // 构造空栈
    	S.base=new SElemType[MaxSize]
      // S.base=(SElemType*)malloc(sizeof(SElemType));
      if(!S.base)  exit (OVERFLOW);  // 存储分配失败
    	s.stackSize=MaxSize;
    	s.top=s.base;
    	return OK;
  }
  

判断顺序栈是否为空

• 【算法思想】栈为空的标志是：S.base=S.top,即栈顶与栈底指针相等

• 【算法描述】

  Status IsEmpty(SqStack S){
    // 若栈为空，返回TURE;否则返回FALSE
    if(S.base==S.top){
      return TRUE;
    }else{
      return FALSE;
    }
  }
  

顺序栈的清空

• 【算法思想】与栈空的标志息息相关，也就是强制使S.base=S.top,而不管里面存储内容，因为最后都可以进行内容覆盖就好。

• 【算法描述】

  Status ClearStack(SqStack &S){
     //1、 先判断栈是否存在
    if(!S.base){
      	return ERROR;
    }
    //2、使base=top
    S.base=S.top;
    return OK;
  }
  

顺序栈的销毁

• 【算法思想】销毁是将分配的内存空间进行释放掉，将栈的长度置为零，将两个指针置为空。

• 【算法描述】

    Status Del_Status(SqStack &S){
      	if(!S.base){
          return ERROR;
        }
         
      	delete S.base;
      	*S.stacksize=0;
      	S.base=S.top=null;
      	
      	return OK;
    }
  

顺序栈的入栈

• 【算法思想】 将添加栈的元素放置在栈顶中，并且将top指针上移一位。

• 【算法步骤】
  1、判断是否栈满，若满则出错（上溢）
  2、元素e压入栈顶
  3、栈顶指针加1

• 【算法描述】

  Status Push(SqStack &S,SElemType e){
      if(S.top-S.base==S.stacksize){
        	return ERROR;
      }
    
    	*S.top=e;
    	S.top++;
    	return OK;
  }
  

顺序栈的出栈

• 【算法思想】将栈顶元素进行出栈操作

• 【算法步骤】
  1、判断栈是否为空，若为空则出错（下溢）
  2、栈顶元素减一
  3、将元素e返回将该位置的置为空。

• 【算法描述】

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