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

仅查询栈顶数据，不从栈中删除数据。
//查看栈顶数据T getTop() {    if(this->isEmpty()) {        return NULL;    }    return *(this->index-1);}2.3.4 测试入栈出栈栈存储会导致存入的顺序和输出的顺序是相反的。
int main(int argc, char** argv) {    Stack<int> myStack(10);    //向栈中压入数据    for(int i=0; i<15; i++) {        myStack.push(i);    }    int top=myStack.getTop();    cout<<"栈顶数据："<<top<<endl;    int size=myStack.getSize();    cout<<"栈中数据的大小:"<<size<<endl;    cout<<"输出栈中所有数据："<<endl;    for(int i=0; i<15; i++) {        cout<<myStack.pop()<<endl;    }    return 0;}输出结果：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MEHtsaDR-1665378597891)(D:\红泥巴\我的课程体系\（信息奥赛）课程体系\第一阶段：入门级（CSP-J）\第三部分：数据结构\1_第一章节：线性表\教学教案\栈的图片\3.png)]
向栈中添加了 15 次数据，因栈的容量只有 10 ，最终输出只有 10 个有效数据。最后的 5 个 0 表示出栈失败。
2.4 小结因顺序栈基于数组，实现过程相对而言较简单，但受限于数组的物理特性，在压入的数据多于栈内部大小时，会出现数据溢出问题。虽然可以采用扩容算法，但同时增加了代码的维护量。
3. 链式存储链式存储是基于结点的存储方式，数据在物理结构上是不连续的。链表存储的优点是可以自行动态扩容，不需要算法层面的支持。
链式存储的流程：
3.1 结点类型结点类型和单链表相同，只需要数据域和存储下一个结点的指针域。
template <typename T>class Node { public:T data;Node *next;Node(T data) {this->data=https://www.huyubaike.com/biancheng/data;this->next=NULL;}};3.2 初始化创建链表时，通常会增加一个空白头结点作为标志结点，在构建链表栈时是不需要的。
template <typename T>class Stack { private://头结点指针Node *head;//栈中实际数据的大小int size; public://构造函数Stack() {            //不需要空白头结点this->head=NULL;             this->size=0;}//入栈bool push(T data)  ;//出栈T pop() ;//查看栈顶数据T getTop() ;//得到栈中的实际数据大小int getSize(){            return this->size;        }};3.3 入栈、出栈链表的数据插入方案有头部插入和尾部插入两种方案。在模拟栈时须保证数据的维护只能在一端进行，可以有 2 种方案：

数据的插入和删除在头部进行。
数据的插入和删除在尾部进行。

本文以头部插入实现入栈和出栈算法。
3.3.1 入栈链式栈不需要考虑栈是已经满的问题。入栈实现流程：

创建一个新结点对象。
原来的头结点成为新结点的后驱结点。
新结点成为头结点。

//入栈bool push(T data) { //创建新结点 Node<T> *newNode=new Node<T>(data); if(newNode){ //原来的头结点成为新结点的后驱 newNode->next=this->head; //新结点成为头结点 this->head=newNode; this->size++; return 1; }else{ return 0; }}3.3.2 出栈链式栈的出栈操作需要判断栈是否为空。如果不为空刚取出头结点数据，并把结点从链表中删除。实现流程：