1. 前言栈是一种受限的数据结构,要求在存储数据时遵循先进后出(Last In First Out)的原则 。可以把栈看成只有一个口子的桶子 , 进和出都是走的这个口子(也称为栈顶),封闭的另一端称为栈底 。
![C++栈和典型迷宫问题](http://img.zhejianglong.com/231018/06445C2V-0.png)
文章插图
什么时候会用到栈?
现实世界里 , 类似于栈的存储现象很普通 。
当我们需要同时存储经常和不经常使用的物品时,我们总是把不经常使用的物品先放到箱子的最里层,把经常使用的物品放到箱子的最外层 。这是典型的栈存储思想 。
在编程的世界里 , 可把稍后要用的数据存储在栈底,把当前需要用的数据存储在栈顶 。或者说,如果数据A依赖数据B , 也就是必须先处理完B后才能处理A 。可以把数据B存储在栈顶,数据A存储在栈底 。
栈的抽象数据类型:
栈最基本的操作是入栈、出栈 , 除此之外,还有查看栈顶、检查栈是为空、检查栈已满……操作 。
栈有 2 种实现方案:
- 顺序存储 。
- 链式存储 。
2.1 初始化栈数组是开放式的数据存储结构 , 为了保证向数组中存储数据时,遵循栈的存储理念,栈类需要做 2 点准备:
- 对外隐藏数组(私有化) 。
- 栈内部确定存储位置 。入口(栈顶)位置可以从数组的首地址开始,也可以从数组的尾地址开始 。
![C++栈和典型迷宫问题](http://img.zhejianglong.com/231018/06445BS2-1.png)
文章插图
template <typename T>class Stack { private://数组地址(这里使用动态创建数组)int *items;//用来控制数组中的有效存储位置(位置控制指针)int *index;//栈的实际数据的大小int size=0; public://构造函数Stack(int stackSize) {this->items=new T[stackSize];this->size=stackSize; //从数组的首地址开始存储 this->index=this->items;}//入栈void push(T data);//出栈T pop();//查看栈顶数据T getTop();//是否为空bool isEmpty();//是否满了bool isFill();};2.2 栈的状态栈有 2 种状态:
- 可用:入栈时,栈中有空位置 , 出栈时 , 栈中有数据,此时栈为可用状态 。
- 不可用:出栈时,如果栈为空,或入栈时,栈已满,此时栈为不可用状态 。
2.2.1 是否为空这个算法很简单,只需要检查位置控制指针是不是为构建栈时的最初状态 。
//是否为空bool isEmpty() { return this->items==this->index;}2.2.2 是否已满只需要检查栈的大小是否和数组的实际存储大小相等 。或者检查位置控制指针是否已经到达数组尾部 。
//是否满了bool isFill(){ return this->index-this->items==this->size;}2.3 入栈和出栈2.3.1 入栈入栈操作需要检查栈是否有空位置 。如果有,存储在位置控制指针所指向位置,然后让位置控制指针指向下一个可用位置 。
//入栈bool push(T data) { if(this->isFill()) { //栈满了 , 不能存储 return 0; } //存储至位置控制指针所指位置 *(this->index)=data; //移动 this->index++; this->size++; return 1;}2.3.2 出栈出栈时需要检查栈是否为空,为空时,出栈失败 。不为空时,把位置控制指针向后移动到数据所在位置 , 然后得出数据 。
//出栈T pop() { if(this->isEmpty()) { //栈为空 return NULL; } this->index--; this->size--; return *(this->index);}2.3.3 其它函数返回栈中实际数据的函数 。
//得到栈中的实际数据大小int getSize(){ return this->index-this->items;}
推荐阅读
- vivoX70pro和苹果11区别对比_哪款更值得入手
- 小米10s和小米10拍照哪个好_小米10s和小米10拍照对比
- vivox70pro+和小米11Ultra那个好_详细对比
- C++ 标准文档
- MatrixOne从入门到实战04——MatrixOne的连接和建表
- MyBatis之ResultMap的association和collection标签详解
- 和平精英粉红小猪怎么获得
- 兰蔻196口红和阿玛尼405哪个好看?颜色更显白?
- airpods 3和AirPods pro的区别_哪款更值得买
- 荣耀v40和小米11哪个好_荣耀v40和小米11哪个值得买