C++中栈结构建立与操作详细解析
什么是栈结构
栈结构是从数据的运算来分类的，也就是说栈结构具有特殊的运算规则，即：后进先出。
我们可以把栈理解成一个大仓库，放在仓库门口（栈顶）的货物会优先被取出，然后再取出里面的货物。
而从数据的逻辑结构来看，栈结构起始就是一种线性结构。
如果从数据的存储结构来进一步划分，栈结构包括两类：
顺序栈结构：
即使用一组地址连续的内存单元依次保存栈中的数据。在程序中，可以定义一个指定大小的结构数组来作为栈，序号为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)
{
cout<<"栈溢出"<<endl;
return 0;
}
s->data[++s->top]=data; //将元素压入栈
return 1;
}
输入参数s为一个指向操作的栈的指针，输入参数data是需要入栈的数据元素。程序首先判断栈是否溢出，如果溢出就给出警告，不进行入栈操作，否则修改栈顶指针，即top先加1，然后将data放到top现在指向的数据单元。
出栈
出栈（Pop）是占据诶狗的基本操作，主要操作与入栈相反，它是从栈顶弹出一个数据元素，出栈操作的具体步骤如下：
（1）首先判断栈顶top，如果top等于0，则表示为恐慌在哪，进行出错处理。否则执行下面的操作。
（2）将栈顶指针top所指向的位置的元素返回（实际是返回的指针）
（3）将top的减1，指向栈的下一个元素，原来栈顶的元素被弹出。
DATA * PopST(StackType *s)
{
if(s->top==0)
{
cout<<"栈为空，不能再输出！"<<endl;
exit(0);
}
return &(s->data[s->top--]);
}
当栈中有数据时，该函数返回值是一个指向DATA类型数据的指针。
读取点结构
读取点结构也就是读取栈结构中结点的数据。由于栈结构只能在一端进行操作，因此这里的读操作其实就是读站点的数据。
需要注意的是，读节点数据的操作和出栈操作不同。读结点操作仅仅是显示栈顶结点数据的内容，而出栈操作则将栈顶数据弹出。
示例代码如下：
DATA *PeekST(StackType *s)
{
if(s->top==0)
{
cout<<"栈已空"<<endl;
exit(0);
}
return &(s->data[s->top]);
}
对比出栈的示例代码，不难发现读取点结构同样返回了栈顶结点的地址，但是却没有使top减1.
完整示例
下面是栈的基本操作的完整示例：
程序代码：
#include<iostream>
#include<string>
using namespace std;
#define MAXLEN 50
struct DATA
{
string name;
int age;
};
struct StackType
{
DATA data[MAXLEN+1];
int top;
};
/******************初始化栈结构****************/
StackType *STInit()
{
StackType *p;
if(p=new StackType) //申请栈空间
{
p->top=0; //设置栈顶为0
return p; //返回栈顶指针
}
return NULL;
}
/****************判断空栈**********************/
int STIsEmpty(StackType *s)
{
int t;
t=(s->top==0); //通过栈顶的值进行判断
return t;
}
/**********************判断满栈****************/
int STIsFull(StackType *s)
{
int t;
t=(s->top==MAXLEN);
return t;
}
/**********************清空栈**********************/
void STClear(StackType *s)
{
s->top=0;
}
/********************释放空间********************/
void STFree(StackType *s)
{
delete s;
}
/**********************入栈***********************/
int PushST(StackType *s,DATA data)
{
if((s->top+1)>MAXLEN)
{
cout<<"栈溢出"<<endl;
return 0;
}
s->data[++s->top]=data; //将元素压入栈
return 1;
}
/************************出栈***********************/
DATA * PopST(StackType *s)
{
if(s->top==0)
{
cout<<"栈为空，不能再输出！"<<endl;
exit(0);
}
return &(s->data[s->top--]);
}
/**********************读取点结构*******************/
DATA *PeekST(StackType *s)
{
if(s->top==0)
{
cout<<"栈已空"<<endl;
exit(0);
}
return &(s->data[s->top]);
}
/*****************进入主函数**********************/
int main()
{
StackType *stack;
DATA data,*p_data;
stack=STInit();
cout<<"===============入栈操作：============="<<endl;
cout<<"输入姓名 ，年龄进行入栈操作："<<endl;
//执行入栈操作
while(1)
{
cin>>data.name>>data.age;
if(data.name=="0")
{
break; //当姓名和年龄都是0的时候退出输入
}else
{
PushST(stack,data);
}
}
p_data=PopST(stack);
cout<<"弹出栈顶元素"<<endl;
cout<<"name:"<<p_data->name<<",age:"<<p_data->age<<endl;
p_data=PeekST(stack);
cout<<"输出栈顶元素"<<endl;
cout<<"name:"<<p_data->name<<",age:"<<p_data->age<<endl;
cout<<"================将所有的的数据出栈：============="<<endl;
while(1)
{
p_data=PopST(stack);
cout<<"name:"<<p_data->name<<",age:"<<p_data->age<<endl;
}
STFree(stack);
return 0;
}
程序运行界面：
相关文章
- vector是表示可以改变大小的数组的序列容器，本文主要介绍了C++STL标准库std::vector的使用详解，文中通过示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子，讲述了C++调用C#的DLL程序的方法，作出了以下总结，下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码，小编觉得挺不错的，现在分享给大家，也给大家做个参考。...2020-04-25
- 整数拆分，指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解，非常不错，感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析，sort函数是algorithm库下的一个函数，sort函数是不稳定的，即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文)，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法，而是讲解我个人比较好奇的问题，就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下...2021-03-29
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 虽然C++11引入了智能指针的，但是开发人员在与内存的斗争问题上并没有解放，如果我门实用不当仍然有内存泄漏问题，其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用，一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员，删除map容器中value为指定元素的问题是我们经常与遇到的一个问题，下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料，需要的朋友可以参考借鉴，下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍，需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25