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

简介:

定义

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

逻辑结构

一对一关系

存储结构

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

运算规则

只能从栈顶运算,且访问结点时依照后进先出(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 
目录
相关文章
|
6月前
|
存储
【数据结构】栈和队列-->理解和实现(赋源码)
【数据结构】栈和队列-->理解和实现(赋源码)
38 5
|
6月前
|
存储 测试技术
【初阶数据结构篇】双向链表的实现(赋源码)
因为头结点的存在,plist指针始终指向头结点,不会改变。
49 0
|
6月前
|
存储 测试技术
【初阶数据结构篇】顺序表的实现(赋源码)
线性表(linearlist)是n个具有相同特性的数据元素的有限序列。
49 0
|
8月前
|
存储 算法
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
|
9月前
|
存储 编译器 C语言
【数据结构】深入浅出理解链表中二级指针的应用
【数据结构】深入浅出理解链表中二级指针的应用
135 0
|
存储
【数据结构】顺序表和链表重点知识汇总(附有代码)
【数据结构】顺序表和链表重点知识汇总(附有代码)
137 0
|
测试技术
【数据结构】顺序栈的原理及实现
【数据结构】顺序栈的原理及实现
【数据结构】顺序栈的原理及实现
数据结构循环双链表的完整代码复习
明天进军栈和队列,然后咱就开始刷题了
【数据结构初阶】数组栈和链式队列的实现
【数据结构初阶】数组栈和链式队列的实现
初阶数据结构 遍历二叉树问题 (一)
初阶数据结构 遍历二叉树问题 (一)
124 0
初阶数据结构 遍历二叉树问题 (一)