定义
只能在表的一端(栈顶)进行插入和删除运算的线性表
逻辑结构
一对一关系
存储结构
用顺序栈或链栈存储均可,但以顺序栈更常见
运算规则
只能从栈顶运算,且访问结点时依照后进先出(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)设置栈底和栈顶指针
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