小菜一步一步学数据结构之(五)顺序栈

简介:

定义

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

逻辑结构

一对一关系

存储结构

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

运算规则

只能从栈顶运算,且访问结点时依照后进先出(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 
目录
相关文章
|
存储 编译器
初阶数据结构(五) 栈的介绍与实现
初阶数据结构(五) 栈的介绍与实现
76 0
|
3月前
|
测试技术
【初阶数据结构篇】栈的实现(附源码)
在每一个方法的第一排都使用assert宏来判断ps是否为空(避免使用时传入空指针,后续解引用都会报错)。
40 2
|
5月前
数据结构初阶 栈
数据结构初阶 栈
29 1
|
存储 算法
【数据结构】一篇带你彻底吃透 顺序表
【数据结构】一篇带你彻底吃透 顺序表
56 1
|
存储 C语言
【数据结构初阶】二、顺序表的实现
目录 一、线性表 二、顺序表 2.1 顺序表概念及结构 2.2 顺序表接口实现 2.2.1 顺序表初始化 2.2.2 顺序表的销毁 2.2.3 顺序表的打印 2.2.4 顺序表增加数据(插入,头插、尾插) 2.2.5 顺序表删除数据(删除,头删、尾删) 2.2.6 顺序表查找数据 2.2.7 顺序表修改数据 三、顺序表完整代码(C语言) 3.1 SeqList.h 3.2 SeqList.c 3.3 Test.c 四、顺序表的优缺点
5784 0
【数据结构初阶】二、顺序表的实现
|
测试技术
【数据结构】顺序栈的原理及实现
【数据结构】顺序栈的原理及实现
【数据结构】顺序栈的原理及实现
|
存储
【初阶数据结构】——顺序表详解(C描述)
【初阶数据结构】——顺序表详解(C描述)
108 0
【数据结构初阶】数组栈和链式队列的实现
【数据结构初阶】数组栈和链式队列的实现
|
存储 C++
【初阶数据结构之顺序表实现】(一)
【初阶数据结构之顺序表实现】(一)
【初阶数据结构之顺序表实现】(一)
|
缓存
初阶数据结构 栈
初阶数据结构 栈
72 0
初阶数据结构 栈