C++栈和典型迷宫问题 _生活百科

1. 前言栈是一种受限的数据结构，要求在存储数据时遵循先进后出（Last In First Out）的原则。可以把栈看成只有一个口子的桶子，进和出都是走的这个口子（也称为栈顶），封闭的另一端称为栈底。

文章插图
什么时候会用到栈？
现实世界里，类似于栈的存储现象很普通。
当我们需要同时存储经常和不经常使用的物品时，我们总是把不经常使用的物品先放到箱子的最里层，把经常使用的物品放到箱子的最外层。这是典型的栈存储思想。
在编程的世界里，可把稍后要用的数据存储在栈底，把当前需要用的数据存储在栈顶。或者说，如果数据A依赖数据B ，也就是必须先处理完B后才能处理A 。可以把数据B存储在栈顶，数据A存储在栈底。
栈的抽象数据类型：
栈最基本的操作是入栈、出栈，除此之外，还有查看栈顶、检查栈是为空、检查栈已满……操作。
栈有 2 种实现方案：

顺序存储。
链式存储。

2. 顺序存储顺序存储指使用数组模拟栈实现。
2.1 初始化栈数组是开放式的数据存储结构，为了保证向数组中存储数据时，遵循栈的存储理念，栈类需要做 2 点准备：

对外隐藏数组(私有化) 。
栈内部确定存储位置。入口（栈顶）位置可以从数组的首地址开始，也可以从数组的尾地址开始。

文章插图
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;}