牛骨文教育服务平台(让学习变的简单)

定义

只能在表的一端(栈顶)进行插入和删除运算的线性表

逻辑结构

一对一关系

存储结构

用顺序栈或链栈存储均可,但以顺序栈更常见
栈示意图

运算规则

只能从栈顶运算,且访问结点时依照后进先出(LIFO)或后进后出(FILO)的原则

实现方法

关键是编写入栈和出栈函数,具体实现依顺序栈或链栈的不同而不同

基本操作

  • 入栈
  • 出栈
  • 读栈顶元素值
  • 建栈
  • 判断栈满
  • 栈空

栈与一般线性表的区别

栈是一种特殊的线性表,它只能在表的一端(栈顶)进行插入或删除运算

** 一般线性 表
逻辑结构 一对一 一对一
存储结构 顺序表、链表 顺序栈、链栈
运算规则 随机、顺序存储 后进先出

它们之间在于运算规则不同

栈顶栈底

我们在平常的程序设计中,如果需要按照保存数据时相反的顺序来使用数据,可以利用栈来实现。

顺序栈的表示

#define MAXSIZE 100
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack; 

stacksize 指示栈的最大容量;base为栈底指针,它始终指向栈底位置,若base的值为NULL,则表明栈结构不存在;top为栈顶指针,其初值指向栈底,即top=base可作为栈空的标记。每当插入新的栈顶元素时,指针top增加1;删除栈顶元素时,指针top减1.因此,非空栈中的栈顶指针始终在栈顶元素的下一个位置上。

base == top 是栈空的重要标志

栈满时的处理方法

  1. 报错,返回操作系统。

  2. 分更大的空间,作为栈的存储空间,将原栈的内容移入新栈。

初始化

顺序栈

(1)分配空间并检查空间是否分配失败,若失败则返回错误

(2)设置栈底和栈顶指针
S.top = S.base;

(3)设置栈大小

【算法描述】

 Status InitStack(SqStack &S)
{
S.base=new SElemType[MAXSIZE];
if(!S.base) return OVERFLOW;
S.top=S.base;
S.stackSize=MAXSIZE;
return OK;
}

判断顺序栈是否为空

bool StackEmpty(SqStack S)
{
if(S.top == S.base) return true;
 else
return false;
}

求顺序栈的长度

 int StackLength(SqStack S)
{
 return S.top-S.base;
}

清空顺序栈

Status ClearStack(SqStack S)
{
if(S.base)S.top = S.base;
return OK;
}

销毁顺序栈

 Status DestroyStack(SqStack &S)
{
if(S.base)
{
delete S.base;
S.stacksize = 0;
S.base = S.top =NULL;
}
return OK;
 }

顺序栈进栈

(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)获取栈顶元素e
(3)栈顶指针减1
Status Pop(SqStack &S,SElemType &e)
{
if(S.top == S.base)//栈空
return ERROR;
–S.top;
e= *S.top;
return OK;
}

取顺序栈栈顶元素

判断是否为空栈,若为空则返回错误

否则通过栈顶指针获取栈顶元素

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