【数据结构(C语言版)系列二】 栈

栈和队列是两种重要的线性结构。从数据结构角度看,栈和队列也是线性表,但它们是操作受限的线性表,因此,可称为限定性的数据结构。但从数据类型角度看,它们是和线性表大不相同的两类重要的抽象数据类型。

栈的定义

栈(Stack) 是限定仅在表尾进行插入或删除操作的线性表。因此,对栈来说,表尾端称为栈顶top),表头端称为栈底bottom)。不含元素的空表称为空栈。

栈为后进先出的线性表,简称LIFO结构。

栈的表示和实现

和线性表类似,栈也有两种存储表示方法:顺序栈链栈

顺序栈,即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈订的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。通常的习惯做法是以top=0表示空栈,但与C语言中数组的下标从0开始冲突。另栈在使用过程中所需的最大空间大小难以估计,因此,在初始化时不应限定栈的最大容量,可先为栈分配一个基本容量,在应用过程中,当栈的空间不够使用时再逐段扩大。

则顺序栈可定义如下:

typedef struct{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

stacksize指示栈的当前可使用的最大容量。栈的初始化操作为:按设定的初始分量进行第一次存储分配,base为栈底指针,始终指向栈底位置,base值为null时,表明栈结构不存在。top为栈顶指针,初值指向栈底,即top = base可作为栈空的标记,每当插入新的栈顶元素时,指针top增1;删除栈顶元素时,指针top减1,因此非空栈中的栈顶指针始终在栈顶元素的下一个位置上

顺序栈的模块说明如下:

//-----栈的顺序存储表示-----//
#define STACK_INIT_SIZE 100; //存储空间初始分配量
#define STACKINCREMENT 10;  //存储空间分配增量
typedef struct{
    SElemType *base;     //在栈构造之前和销毁之后,base的值为null
    SElemType *top;       //栈顶指针
    int stacksize;            //当前已分配的存储空间,以元素为单位
}SqStack;

//-----基本操作的函数原型说明-----//
Status InitStack(SqStack &S);
    //构造一个空栈S
Status DestroyStack(SqStack &S);
    //销毁栈S,S不再存在
Status ClearStack(SqStack &S);
    //把S置为空栈
Status StackEmpty(SqStack S);
    //若栈S为空栈,则返回TRUE,否则返回FALSE
int StackLength(SqStack S);
    //返回S的元素个数,即栈的长度
Status GetTop(SqStack S,SElemType &e);
    //若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
Status Push(SqStack &S,SElemType e);
    //插入元素e为新的栈顶元素
Status Pop(SqStack &S,SElemType &e);
    //若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
Status StackTraverse(SqStack S,Status(*visit)());
    //从栈底到栈顶依次对栈中每个元素调用函数visit()。一旦visit()失败,则操作失败


//-----基本操作的算法描述-----//
Status InitStack(SqStack &S){
    //构造一个空栈S
    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType ));
    if (!S.base) 
    exit(OVERFLOW);//存储分配失败
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

Status DestroyStack(SqStack &S){
    //销毁栈S,S不再存在
  free(S.base);

  S.base = NULL;
  S.top  = NULL;
  S.stacksize = 0;
 
  return OK;
}

Status ClearStack(SqStack &S){
    //把S置为空栈
  S.top = S.base;
  return OK;
}

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

int StackLength(SqStack S){
    //返回S的元素个数,即栈的长度
  return S.top - S.base;
}

Status GetTop(SqStack S,SElemType &e);
    //若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
    if (S.top == S.base) 
    retun ERROR;
    e = *(S.top - 1);
    return OK;
}

Status Push(SqStack &S,SElemType e){
    //插入元素e为新的栈顶元素
    if (S.top - S.base>= S.stacksize){  //栈满,追加存储空间
        S.base= (SElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType));
        if (!S.base)
       exit(OVERFLOW);
     S.top = S.base + S.stacksize;
     S.stacksize += STACKINCREMENT;
  }  
  *S.top++ = e;
  return OK;
}

Status Pop(SqStack &S,SElemType &e){
    //若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
  if (S.top == S.base)
    return ERROR;
  e = *--S.top;
  return OK;
}

Status StackTraverse(SqStack S,Status(*visit)()){
    //从栈底到栈顶依次对栈中每个元素调用函数visit()。一旦visit()失败,则操作失败
  SElemType *p = S.base;
  while(p < S.top)
    Visit(*p++);
   return OK;
}

链栈如图所示:

附几个栈的应用举例:

3-2-进制转换-栈和队列-第3章-《数据结构》课本源码-严蔚敏吴伟民版

3-3-行编辑程序-栈和队列-第3章-《数据结构》课本源码-严蔚敏吴伟民版

3-4-迷宫寻路-栈和队列-第3章-《数据结构》课本源码-严蔚敏吴伟民版

3-5-表达式求值-栈和队列-第3章-《数据结构》课本源码-严蔚敏吴伟民版

3-6-汉诺塔(Hanoi Tower)问题-栈和队列-第3章-《数据结构》课本源码-严蔚敏吴伟民版

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏图形学与OpenGL

WebGL三角形平移变换(矩阵方式)

2801
来自专栏熊二哥

Java核心编程快速入门

Java核心编程部分的基础学习内容就不一一介绍了,本文的重点是JAVA中相对复杂的一些概念,主体内容如下图所示。 ? ? 反射reflect是理解Java语言...

2229
来自专栏达摩兵的技术空间

当JSON.parse”遇上”非键值对

在json大行其道并作为前后端主要通讯的数据格式之一时,对json本身的使用和了解多少人都会有些概念,当然随之而来的也是对json的对象以及其字符串形式的互相转...

3693
来自专栏偏前端工程师的驿站

JS魔法堂:再识instanceof

一、Breif                                  大家都知道instanceof一般就是用来检查A对象是否为B类或子类的实例。那...

2439
来自专栏码匠的流水账

聊聊storm的AggregateProcessor的execute及finishBatch方法

本文主要研究一下storm的AggregateProcessor的execute及finishBatch方法

1215
来自专栏技术博客

设计模式之八(原型模式)

ConcretePrototype1,ConcretePrototype2具体原型类,实现一个克隆自身的操作

1001
来自专栏从流域到海域

《笨办法学Python》 第39课手记

《笨办法学Python》 第39课手记 本节课讲列表的操作,用来做练习的代码中出现了之前用到过的几个函数,是一节复习课。你需要记住它们。 原代码如下: ten_...

2047
来自专栏码匠的流水账

聊聊storm trident spout的_maxTransactionActive

本文主要研究一下storm trident spout的_maxTransactionActive

842
来自专栏蘑菇先生的技术笔记

探索c#之不可变数据类型

2094
来自专栏数据结构与算法

洛谷P1200 [USACO1.1]你的飞碟在这儿

题目描述 众所周知,在每一个彗星后都有一只UFO。这些UFO时常来收集地球上的忠诚支持者。不幸的是,他们的飞碟每次出行都只能带上一组支持者。因此,他们要用一种聪...

3374

扫码关注云+社区

领取腾讯云代金券