当前位置:  编程技术>c/c++/嵌入式

C++中栈结构建立与操作详细解析

    来源: 互联网  发布时间:2014-10-22

    本文导语:  什么是栈结构 栈结构是从数据的运算来分类的,也就是说栈结构具有特殊的运算规则,即:后进先出。 我们可以把栈理解成一个大仓库,放在仓库门口(栈顶)的货物会优先被取出,然后再取出里面的货物。 而从数据的逻辑...

什么是栈结构

栈结构是从数据的运算来分类的,也就是说栈结构具有特殊的运算规则,即:后进先出。

我们可以把栈理解成一个大仓库,放在仓库门口(栈顶)的货物会优先被取出,然后再取出里面的货物。

而从数据的逻辑结构来看,栈结构起始就是一种线性结构。

如果从数据的存储结构来进一步划分,栈结构包括两类:
顺序栈结构:

即使用一组地址连续的内存单元依次保存栈中的数据。在程序中,可以定义一个指定大小的结构数组来作为栈,序号为0的元素就是栈低,再定义一个变量top保存栈顶的序号即可。
链式栈结构:

即使用链表的的形式保存栈中各元素的值。链表首部(head指针所指向元素)为栈顶,链表尾部(指向地址为NULL)为栈底。

在栈结构中只能在一端进行操作,该操作端称为栈顶,另一端称为栈底。也就是说,保存和取出的数据都只能从栈结构的一端进行。从数据的运算角度来分析,栈结构是按照“后进先出”的原则处理结点数据的。

在栈结构中,只有栈顶元素是可以访问的,栈结构的数据运算也是非常简单。一般栈结构的基本操作只有两个:

入栈(Push):将数据保存到栈顶的操作。进行入栈操作前,先修改栈顶指针,使其向上移一个元素位置,然后将数据保存到栈顶指针所指的位置。

出栈(Pop):将栈顶数据弹出的操作。通过修改栈顶指针,使其指向栈中的下一个元素。

接下来,我们使用C++语言建立顺序栈,并完成顺序栈结构的基本运算
准备数据

准备在栈操作中需要用到的变量及数据结构等。

代码如下:

#define MAXLEN 50
struct DATA
{
 string name;
 int age;
};
struct StackType
{
 DATA data[MAXLEN+1];
 int top;
};


定义栈结构的长度MAXLEN,栈结构的数据元素类型DATA,以及栈结构的数据结构StackType。在数据结构StackType中,data为数据元素,top为栈顶的序号。当top=0时,表示栈为空,当top=MAXLEN时表示栈满。

数组元素都是充下标0开始的,这里为了讲述和理解方便,我们从下标1开始记录数据结点,下标0的位置不用。
初始化栈结构

在使用栈结构之前,首先需要创建一个空的顺序栈,也就是初始化顺序栈。顺序栈的初始化操作如下:

(1)按照符号常量MAXLEN指定大小申请一片内存空间,用来保存栈中的数据

(2)设置栈顶指针的值为0,表示一个空栈。

示例代码如下:

代码如下:

StackType *STInit()
{
 StackType *p;
 if(p=new StackType)   //申请栈空间
 {
  p->top=0;     //设置栈顶为0
  return p;     //返回栈顶指针
 } 
 return NULL; 
}

首先用new申请内存,然后设置栈顶为0,然后返回申请内存的首地址,申请失败返回NULL;

判断空栈

判断栈结构是否为空,如果是空栈,则表示该栈结构中没有数据,此时可以进行入栈操作,但是不可以进行出栈操作。

示例代码如下:

代码如下:

int STIsEmpty(StackType *s)
{
 int t;
 t=(s->top==0);     //通过栈顶的值进行判断
 return t;
}

输入参数s为一个指向操作的栈的指针。根据栈顶指针top判断是否为0,判断栈是否为空。

判断满栈

判断栈结构是否为满。如果是满栈,则表示该栈结构中没有多余的空间来保存额外数据。此时不可以进行入栈操作,但是可以进行进栈操作。

示例代码如下:

代码如下:

int STIsFull(StackType *s)
{
 int t;
 t=(s->top==MAXLEN);
 return t;
}

输入参数s为一个指向操作的栈的指针。根据栈顶指针top判断是否和MAXLEN相等,判断栈是否已满。

清空栈

清空栈就是栈中所有的数据被清除。 示例代码如下:

代码如下:

void STClear(StackType *s)
{
 s->top=0;
}

将栈顶指针top设置为0,表示执行清空栈操作。(这里只是逻辑上将栈中数据清空,实际上只是将top设置为0,以后再添加数据会覆盖原来的数据)

释放空间

释放空间是释放栈结构所占用的内存单元,使用delete释放用new运算符申请的内存空间。

示例代码如下:

代码如下:

void STFree(StackType *s)
{
 delete s;
}

在程序中直接调用delete运算符释放已分配的内存空间。一般在不需要使用栈结构时调用该函数,特别是在程序结束的时候。

入栈

入栈(Push)是栈结构的基本操作,主要操作是将数据元素保存到栈结构。入栈操作的具体步骤如下:

(1)首先判断栈顶top,如果top大于等于MAXLEN,则表示溢出,进行出错处理。否则执行以下操作。

(2)设置top=top+1(栈顶指针加1,指向入栈地址)

(3)将入栈呀U尿素保存到top指向的位置。

示例代码如下:

代码如下:

int PushST(StackType *s,DATA data)
{
 if((s->top+1)>MAXLEN)
 {
  couttop=0;
}
/********************释放空间********************/
void STFree(StackType *s)
{
 delete s;
}
/**********************入栈***********************/
int PushST(StackType *s,DATA data)
{
 if((s->top+1)>MAXLEN)
 {
  cout

    
 
 

您可能感兴趣的文章:

  • C与C++中结构体的区别
  • C和C++的结构体运用是否有这样的区别?
  • C++并发数据结构算法库 CDS
  • 使用TCP协议通讯,如果有很多种数据要传输,如:注册信息等,在C++中,我们可以使用结构,java中通常大家又是如何打包的呢?
  • C++联合体转换成C#结构的实现方法
  • 一道超经典的C++结构体的题目
  • C++中指向结构体变量的指针
  • C++结构体数组详细解析
  • C++ 冒泡排序数据结构、算法及改进算法
  • 浅析C++中结构体的定义、初始化和引用
  • C++二叉树结构的建立与基本操作
  • Java结构化数据解析包 Lycia
  • C#枚举类型与结构类型实例解析
  • 操作系统 iis7站长之家
  • 解析数字签名的substring结构(获取数字签名时间)
  • c#分支与循环结构的实例解析
  • 解析结构体的定义及使用详解
  • vm_operations_struct 结构体解析?
  • 数据结构课程设计- 解析最少换车次数的问题详解
  • 解析SQL 表结构信息查询 含主外键、自增长
  • 解析从源码分析常见的基于Array的数据结构动态扩容机制的详解
  • 基于mysql体系结构的深入解析
  • C# IFF图形结构解析代码
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 想建立一个指向结构体的指针数组,但编译不过,望高手指点!
  • python数据结构之二叉树的建立实例
  • <<大话数据结构>>中冒泡排序算法改进
  • 请问:在用proc方式往数据库插入数据时,我能不能定义一个结构体,它与表的每一项对应,将结构体赋好值后,再只将这个结构体插入表中,这行不行啊?
  • 基于Key-Value的NOSQL数据库Redis的数据结构及常用相关命令介绍
  • 全局结构体变量和全局结构体指针变量
  • Oracle数据库(Oracle Database)体系结构及基本组成介绍
  • 《arm体系结构结构与编程》书如何
  • 数据结构:图(有向图,无向图),在Python中的表示和实现代码示例
  • file结构和inode结构
  • mysql 命令大全及导入导出表结构或数据
  • 《莱昂氏UNIX源代码分析》中有一种结构体声明没有结构体名
  • 关于学籍管理系统B/S结构实现的结构问题
  • GCC 编译问题: 结构A中有个成员结构B??
  • 强人,linux下驱动相关数据结构和usb设备数据结构之间的功能分析
  • 谁能告诉我EJB的体系结构有哪些,这些体系结构的优缺点如何,万分感谢!
  • 协议的设计一般采用结构体进行数据打包,在协议设计的结构体中能不能使用指针 ?
  • struct __una_u16结构是什么结构.
  • GNU汇编fill填充一个数据结构使得另一个数据结构全部清零
  • 高手帮帮忙!vi中如何实现跳转到任意结构体或函数的声明处,包括系统库中声明的函数和数据结构?
  • jbuilder7里如何在project pane里显示出某个project的所有的类的结构图,就如显示source java files的结构图一样
  • 关于客户服务器结构与浏览器服务器结构编程的比较
  • 有一个win32的结构体,大伙看看能否转换成linux下的基本等价的结构体?




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3