关于##利用链表实现栈类##的问题，如何解决？（C++）

补全代码，利用链表实现栈类，并验证栈的存储和操作。

#include <iostream>
using namespace std;
//----------链表工具类的普适形式，它可以处理以链表为基本支撑结构的数据结构问题，如栈，队列，图等。----------------- 
//结点结构
struct Node {
    int data; //这个整型变量代表结点携带的数据
    Node *next; //指向下一个结点的链表指针（保存着下一个结点的地址）
};
//定义一个处理链表的类
//该类像一个工具包，里面放着各种处理链表的工具，以及链表的数据。
class LinkList {
    public:
        //构造函数对链表的结构进行初始化，利用new，构建第一个结点。
        LinkList() {
            //补全代码，完成对头结点的初始化工作。 
            //新建一个结点（在堆内存中申请一个结点的空间，并将地址返回给first指针，该结点本身是空结点，仅做头结点用）

            //将该结点的next指针清空（可以理解为封口，堵头儿，将来遍历的时候，有个到此为止的标记）

            //------------------------------------------------        
        }
        //析构函数。 
        ~LinkList();
        //插入一个新结点，该结点携带数据x，插入后成为该链表的第i个结点。 
        void Insert(int i,int x);
        //插入一个新结点，该结点携带数据x，插入后成为该链表的第i+1个结点。
        void Insert_behind(int i, int x);
        //头插法，插入一个新结点，插入后，在头部。也就是第一个结点。
        void Insert_head(int x);
         
        //搜索结点，搜索携带数据为x的结点，返回该结点所在的索引号（该结点是第几个结点），未找到则返回0 
        int Search(int x);
        //获取第i个结点的数据，如果未找到，则返回0。 
        int Get(int i);
        //删除第i个结点。 
        void Delete(int i);
        //求链表的长度，也就是链表结点的个数。 
        int Length();
        //打印链表的数据。 
        void PrintList();
    private:
        //链表头结点指针，也就是第一个结点的地址。 
        Node *first;
};

//插入一个新结点，该结点携带数据x，插入后成为该链表的第i个结点。
void LinkList::Insert(int i, int x) {
    //结点指针p作为游标指针，从头开始遍历链表，找到要插入的位置。 
    Node *p;
    //结点指针s为新结点指针，通过new构建新结点，插入到链表的正确位置。 
    Node *s;
    //用来计算遍历的位置，直至i的前一个位置为止。 
    int j;
    //插入算法开始：
    //首先，讲游标指针p指向头结点。（first为本类唯一的一个属性，就是头结点的地址） 
    p = first;
    //遍历位置游标j从0开始。 
    j = 0;
    //当游标p有意义（也就是指向了一个存在的结点，不为空），
    //并且位置游标j没到第i个 
    while(p && j < i - 1) {
        //就继续向后寻找，遍历。 
        p = p->next;
        //位置游标j也向后增加 
        j++;
        //直到p为空（也就是到了链表末尾）或者j已挪动到预定位置i的前一个位置为止。 
    }
    //此时，退出上述while循环，有两种可能：
    //（1）p到末尾；
    //（2）j到达预定位置，即i的前一个位置。
    //如果此时p到末尾，或者i位置是个不合理位置。那报错。 
    if(!p || i < 1)
    { 
        cout << "位置不正确" << endl;
    }
    //如果此时p没到末尾，则必定到达了预定位置(i-1)。
    //所以，可以生成新结点s，并将结点连接到原来i的位置，也就是现在的p->next的位置
    //并将p的next指针指向s，完成插入操作。
    //注意，一定是先将新结点尾部挂接在原链表上，再拆开原链表，将前一部分挂接在
    //新结点上，组成一个新链表。 
    else
    {
        //补全代码，完成新结点的产生和插入操作。 
        //产生新结点，并填上数据x 
        
        
        
        //新结点尾部指向当前位置的后方，完成挂接。 
        
        
        //以当前位置为分界，原链表拆开，前一部分尾部挂接在新结点上，组成新链表。 
        
        //------------------------------------------------------------
    }
}
void LinkList::Insert_behind(int i, int x){
    //结点指针p作为游标指针，从头开始遍历链表，找到要插入的位置。 
    Node *p;
    //结点指针s为新结点指针，通过new构建新结点，插入到链表的正确位置。 
    Node *s;
    //用来计算遍历的位置，直至i的前一个位置为止。 
    int j;
    //插入算法开始：
    //首先，讲游标指针p指向头结点。（first为本类唯一的一个属性，就是头结点的地址） 
    p = first;
    //遍历位置游标j从0开始。 
    j = 0;
    //当游标p有意义（也就是指向了一个存在的结点，不为空），
    //并且位置游标j没到第i个 
    while(p && j < i) {
        //就继续向后寻找，遍历。 
        p = p->next;
        //位置游标j也向后增加 
        j++;
        //直到p为空（也就是到了链表末尾）或者j已挪动到预定位置i的前一个位置为止。 
    }
    //此时，退出上述while循环，有两种可能：
    //（1）p到末尾；
    //（2）j到达预定位置，即i的前一个位置。
    //如果此时p到末尾，或者i位置是个不合理位置。那报错。 
    if(!p || i < 0)
    { 
        cout << "位置不正确" << endl;
    }
    //如果此时p没到末尾，则必定到达了预定位置(i-1)。
    //所以，可以生成新结点s，并将结点连接到原来i的位置，也就是现在的p->next的位置
    //并将p的next指针指向s，完成插入操作。
    //注意，一定是先将新结点尾部挂接在原链表上，再拆开原链表，将前一部分挂接在
    //新结点上，组成一个新链表。 
    else
    {
        //补全代码，完成新结点的产生和插入操作。 
        //产生新结点，并填上数据x 
        
        
        
        //新结点尾部指向当前位置的后方，完成挂接。 
        
        
        //以当前位置为分界，原链表拆开，前一部分尾部挂接在新结点上，组成新链表。 
        
        //------------------------------------------------------------
    }
}

//头插法，插入一个新结点，插入后，在头部。也就是第一个结点。
void LinkList::Insert_head(int x){
    //补全代码，利用Insert_behind方法或Insert方法，实现在头部插入新结点的功能



    //-------------------------------------------------------------------
}

//搜索结点，搜索携带数据为x的结点，返回该结点所在的索引号（该结点是第几个结点）
//未找到则返回0  
int LinkList::Search(int x) {
    //结点指针p作为游标指针，从头开始遍历链表
    Node *p;
    //j记录结点的索引位置 
    int j;
    //算法开始：
    //首先，将p指向有意义的第一个结点（也就是索引为1的结点，也是实际的第二个结点） 
    p = first->next;
    //j记录为1（从0开始的） 
    j = 1;
    //只要p未到末尾 
    while(p)
    {
        //补全代码，完成值为x的结点的查找 
        //考查游标p指向的结点，如果该结点恰好携带数据x，则退出循环，找到了。 
        
        
        
        //如果该结点数据并不是x，则p继续向后遍历下一个结点继续考查 
        
        
        
        //------------------------------------------------------
        //索引值也随之后移。 
        j++;

    }
    //如果上述循环正常退出，则p到末尾，也就是没找到 
    if(!p)
        //则返回0，表示未找到。有效的索引值从1开始。 
        return 0;
    //如果上述循环没正常退出，也就是break被激活，那定然是找到了x结点。 
    else
        //则将当时记录的索引j返回。交差成功。 
        return j;
}

//获取第i个结点的数据，如果未找到，则返回0。
int LinkList::Get(int i) {
//首先，将游标p指向有意义的第一个结点（也就是索引为1的结点，也是实际的第二个结点）
    Node *p = first->next;
    //j记录为1（从0开始的）
    int j = 1;
    
    //补全代码，实现结点的获取。 
    //向后移动游标，直至i结点（也就是j==i时，退出，如果此时的p仍然有意义的话）  
    //提示，游标p后移同时，索引j也应后移。 
    
    
    
    
    
    
    //-------------------------------------------------------------
    
    //如果p到末尾退出的，那证明没有找到i结点，或者说链表就没有i那么多个结点。 
    if(!p)
        throw 0;
    //如果p没到末尾，此时的j正好是i。直接把p这个结点的内容返回交差。 
    else
        return p->data;
}

//删除第i个结点。
void LinkList::Delete(int i) {
    //游标p从头开始 
    Node *p = first;
    //结点指针s用来指向待删除的结点。 
    Node *s;
    //索引j从0开始 
    int j = 0;
    //将游标p后移，直至待删除的结点的前一个结点。 
    while(p && j < i - 1)
    {
        p = p->next;
        j++;
    }
    //如果循环结束时，p已经到了末尾，或者p的下一个结点到了末尾（也就是p指向了最后一个有意义的结点）。
    //这里解释一下。
    //（1）出现p到末尾的情况是：待删除结点的索引i - length（链表） > 1
    //此时，p到了末尾，仍然无法达到待删除结点的前一个结点的位置。
    //（2）出现p到了最后一个有意义结点的情况是：i - length(链表) == 1
    //此时，p到了最后一个有意义的结点，但是后面再没有可删除的i结点了。悲剧。
    //这两种情况都是无法删除的，位置不正确。 
    if(!p || !p->next)
    {
        cout << "位置不正确" << endl;
    }
    //如果找到了待删除结点i的前一个位置。 
    else
    {
        //补全代码，完成结点i删除的操作。
        //那就用s记录下要删除的结点 
        
        
        //然后将i前一个结点直接越过s，连接到s的下一个结点。 
        
        
        //输出该删除结点的数据 
        
        
        //注销该结点。 
        
        //----------------------------------------------------
    }
}
//求链表的长度，也就是链表结点的个数。 
int LinkList::Length() {
    //首先，将游标p指向有意义的第一个结点
    Node *p = first->next;
    //len记录长度 
    int len = 0;
    //只要p没到链表末尾 
    while(p)
    {
        //补全代码，完成长度的计算。 
        //就将p后移 
        
        
        //长度加一 
        
        //------------------------------------------- 
    }
    //返回长度 
    return len;
}
//打印链表的数据。
void LinkList::PrintList() {
    //首先，将游标p指向有意义的第一个结点
    Node *p = first->next;
    if(!p){
    //    cout << "链表无结点" << endl; 
    }
    else{
        //只要p没到链表末尾
        while(p)
        {
            //就输出该结点数据 
            cout << p->data << endl;
            //将p后移
            p = p->next;
        }
    }
    
}
//析构函数。 
LinkList::~LinkList() {
    //游标p从头开始
    Node *p = first;
    //结点指针s用来指向待删除的结点。
    Node *s;
    //只要p没到链表末尾 
    while(p)
    {
        //补全代码，完成结点的删除操作 
        //s标记好待删除结点 
        
        
        //p后移到下一个待删除结点 
        
        
        //注销s结点 
        
        //------------------------------------------------
    }
}
//--------------------------------------------------------------------------------------------- 
//--------------------------------------------------------------------------------------------- 
 

//----------------------------------------------------------------------------- 
int main(){
    
    //-------------链表形式的栈操作验证--------------------------
    //利用基础链表类进行栈操作验证
    //建立栈 
    LinkList l;
    int i;
    //压栈的次数
    int num;
    //压栈的数据 
    int x;
    //输入压栈次数
    cin >> num;
    //依次压栈x 
    for(int i = 0; i < num; i++){
        cin >> x;
        l.Insert_head(x);
    }
    
    //查看数据 
    l.PrintList();
    //查看栈长度 
    cout << l.Length() << endl;
    //出栈操作 
    for(i = 0; i < 2; i++){
        //出栈操作 
        try{
            //补全代码
            int data;
            //利用Get方法弹出栈顶结点,保存至data，并输出
            

            //再利用Delete方法注销被弹出的栈顶结点
            
            
            //------------------------------------------------------------
        }    
        catch(int){
            cout << "栈空" << endl; 
        }
    }
    
    //查看数据 
    l.PrintList();
    //查看栈长度 
    cout << l.Length() << endl;
    return 0;
}




``测试输入：
3
1
2
3
预期输出：
3
2
1
3
出栈弹出数据：3
出栈弹出数据：2
1
1

测试输入：
1
1
预期输出：
1
1
出栈弹出数据：1
栈空
0

`

代码补全如下：

#include <iostream>
using namespace std;
//----------链表工具类的普适形式，它可以处理以链表为基本支撑结构的数据结构问题，如栈，队列，图等。----------------- 
//结点结构
struct Node {
    int data; //这个整型变量代表结点携带的数据
    Node* next; //指向下一个结点的链表指针（保存着下一个结点的地址）
};
//定义一个处理链表的类
//该类像一个工具包，里面放着各种处理链表的工具，以及链表的数据。
class LinkList {
public:
    //构造函数对链表的结构进行初始化，利用new，构建第一个结点。
    LinkList() {
        //补全代码，完成对头结点的初始化工作。 
        //新建一个结点（在堆内存中申请一个结点的空间，并将地址返回给first指针，该结点本身是空结点，仅做头结点用）
        first = new Node;
        
        //将该结点的next指针清空（可以理解为封口，堵头儿，将来遍历的时候，有个到此为止的标记）
        first->next = 0;
        //------------------------------------------------        
    }
    //析构函数。 
    ~LinkList();
    //插入一个新结点，该结点携带数据x，插入后成为该链表的第i个结点。 
    void Insert(int i, int x);
    //插入一个新结点，该结点携带数据x，插入后成为该链表的第i+1个结点。
    void Insert_behind(int i, int x);
    //头插法，插入一个新结点，插入后，在头部。也就是第一个结点。
    void Insert_head(int x);

    //搜索结点，搜索携带数据为x的结点，返回该结点所在的索引号（该结点是第几个结点），未找到则返回0 
    int Search(int x);
    //获取第i个结点的数据，如果未找到，则返回0。 
    int Get(int i);
    //删除第i个结点。 
    void Delete(int i);
    //求链表的长度，也就是链表结点的个数。 
    int Length();
    //打印链表的数据。 
    void PrintList();
private:
    //链表头结点指针，也就是第一个结点的地址。 
    Node* first;
};

//插入一个新结点，该结点携带数据x，插入后成为该链表的第i个结点。
void LinkList::Insert(int i, int x) {
    //结点指针p作为游标指针，从头开始遍历链表，找到要插入的位置。 
    Node* p;
    //结点指针s为新结点指针，通过new构建新结点，插入到链表的正确位置。 
    Node* s;
    //用来计算遍历的位置，直至i的前一个位置为止。 
    int j;
    //插入算法开始：
    //首先，讲游标指针p指向头结点。（first为本类唯一的一个属性，就是头结点的地址） 
    p = first;
    //遍历位置游标j从0开始。 
    j = 0;
    //当游标p有意义（也就是指向了一个存在的结点，不为空），
    //并且位置游标j没到第i个 
    while (p && j < i - 1) {
        //就继续向后寻找，遍历。 
        p = p->next;
        //位置游标j也向后增加 
        j++;
        //直到p为空（也就是到了链表末尾）或者j已挪动到预定位置i的前一个位置为止。 
    }
    //此时，退出上述while循环，有两种可能：
    //（1）p到末尾；
    //（2）j到达预定位置，即i的前一个位置。
    //如果此时p到末尾，或者i位置是个不合理位置。那报错。 
    if (!p || i < 1)
    {
        cout << "位置不正确" << endl;
    }
    //如果此时p没到末尾，则必定到达了预定位置(i-1)。
    //所以，可以生成新结点s，并将结点连接到原来i的位置，也就是现在的p->next的位置
    //并将p的next指针指向s，完成插入操作。
    //注意，一定是先将新结点尾部挂接在原链表上，再拆开原链表，将前一部分挂接在
    //新结点上，组成一个新链表。 
    else
    {
        //补全代码，完成新结点的产生和插入操作。 
        //产生新结点，并填上数据x 
        s = new Node;
        s->data = x;
        
        //新结点尾部指向当前位置的后方，完成挂接。 
        s->next = p->next;
        
        //以当前位置为分界，原链表拆开，前一部分尾部挂接在新结点上，组成新链表。 
        p->next = s;
        //------------------------------------------------------------
    }
}
void LinkList::Insert_behind(int i, int x) {
    //结点指针p作为游标指针，从头开始遍历链表，找到要插入的位置。 
    Node* p;
    //结点指针s为新结点指针，通过new构建新结点，插入到链表的正确位置。 
    Node* s;
    //用来计算遍历的位置，直至i的前一个位置为止。 
    int j;
    //插入算法开始：
    //首先，讲游标指针p指向头结点。（first为本类唯一的一个属性，就是头结点的地址） 
    p = first;
    //遍历位置游标j从0开始。 
    j = 0;
    //当游标p有意义（也就是指向了一个存在的结点，不为空），
    //并且位置游标j没到第i个 
    while (p && j < i) {
        //就继续向后寻找，遍历。 
        p = p->next;
        //位置游标j也向后增加 
        j++;
        //直到p为空（也就是到了链表末尾）或者j已挪动到预定位置i的前一个位置为止。 
    }
    //此时，退出上述while循环，有两种可能：
    //（1）p到末尾；
    //（2）j到达预定位置，即i的前一个位置。
    //如果此时p到末尾，或者i位置是个不合理位置。那报错。 
    if (!p || i < 0)
    {
        cout << "位置不正确" << endl;
    }
    //如果此时p没到末尾，则必定到达了预定位置(i-1)。
    //所以，可以生成新结点s，并将结点连接到原来i的位置，也就是现在的p->next的位置
    //并将p的next指针指向s，完成插入操作。
    //注意，一定是先将新结点尾部挂接在原链表上，再拆开原链表，将前一部分挂接在
    //新结点上，组成一个新链表。 
    else
    {
        //补全代码，完成新结点的产生和插入操作。 
        //产生新结点，并填上数据x 
        s = new Node;
        s->data = x;


        //新结点尾部指向当前位置的后方，完成挂接。 
        s->next = p->next;

        //以当前位置为分界，原链表拆开，前一部分尾部挂接在新结点上，组成新链表。 
        p->next = s;
        //------------------------------------------------------------
    }
}

//头插法，插入一个新结点，插入后，在头部。也就是第一个结点。
void LinkList::Insert_head(int x) {
    //补全代码，利用Insert_behind方法或Insert方法，实现在头部插入新结点的功能
    Insert_behind(0, x);

    //-------------------------------------------------------------------
}

//搜索结点，搜索携带数据为x的结点，返回该结点所在的索引号（该结点是第几个结点）
//未找到则返回0  
int LinkList::Search(int x) {
    //结点指针p作为游标指针，从头开始遍历链表
    Node* p;
    //j记录结点的索引位置 
    int j;
    //算法开始：
    //首先，将p指向有意义的第一个结点（也就是索引为1的结点，也是实际的第二个结点） 
    p = first->next;
    //j记录为1（从0开始的） 
    j = 1;
    //只要p未到末尾 
    while (p)
    {
        //补全代码，完成值为x的结点的查找 
        //考查游标p指向的结点，如果该结点恰好携带数据x，则退出循环，找到了。 
        if (p->data == x)
            break;

        //如果该结点数据并不是x，则p继续向后遍历下一个结点继续考查 
        p = p->next;
        //------------------------------------------------------
        //索引值也随之后移。 
        j++;

    }
    //如果上述循环正常退出，则p到末尾，也就是没找到 
    if (!p)
        //则返回0，表示未找到。有效的索引值从1开始。 
        return 0;
    //如果上述循环没正常退出，也就是break被激活，那定然是找到了x结点。 
    else
        //则将当时记录的索引j返回。交差成功。 
        return j;
}

//获取第i个结点的数据，如果未找到，则返回0。
int LinkList::Get(int i) {
    //首先，将游标p指向有意义的第一个结点（也就是索引为1的结点，也是实际的第二个结点）
    Node* p = first->next;
    //j记录为1（从0开始的）
    int j = 1;

    //补全代码，实现结点的获取。 
    //向后移动游标，直至i结点（也就是j==i时，退出，如果此时的p仍然有意义的话）  
    //提示，游标p后移同时，索引j也应后移。 
    while (p && j < i)
    {
        p = p->next;
        j++;
    }

    //-------------------------------------------------------------

    //如果p到末尾退出的，那证明没有找到i结点，或者说链表就没有i那么多个结点。 
    if (!p)
        throw 0;
    //如果p没到末尾，此时的j正好是i。直接把p这个结点的内容返回交差。 
    else
        return p->data;
}

//删除第i个结点。
void LinkList::Delete(int i) {
    //游标p从头开始 
    Node* p = first;
    //结点指针s用来指向待删除的结点。 
    Node* s;
    //索引j从0开始 
    int j = 0;
    //将游标p后移，直至待删除的结点的前一个结点。 
    while (p && j < i - 1)
    {
        p = p->next;
        j++;
    }
    //如果循环结束时，p已经到了末尾，或者p的下一个结点到了末尾（也就是p指向了最后一个有意义的结点）。
    //这里解释一下。
    //（1）出现p到末尾的情况是：待删除结点的索引i - length（链表） > 1
    //此时，p到了末尾，仍然无法达到待删除结点的前一个结点的位置。
    //（2）出现p到了最后一个有意义结点的情况是：i - length(链表) == 1
    //此时，p到了最后一个有意义的结点，但是后面再没有可删除的i结点了。悲剧。
    //这两种情况都是无法删除的，位置不正确。 
    if ( !p || !p->next )
    {
        cout << "位置不正确" << endl;
    }
    //如果找到了待删除结点i的前一个位置。 
    else
    {
        //补全代码，完成结点i删除的操作。
        //那就用s记录下要删除的结点 
        s = p->next;

        //然后将i前一个结点直接越过s，连接到s的下一个结点。 
        p->next = s->next;

        //输出该删除结点的数据 
        cout << s->data << endl;

        //注销该结点。 
        delete s;
        s = 0;
        //----------------------------------------------------
    }
}
//求链表的长度，也就是链表结点的个数。 
int LinkList::Length() {
    //首先，将游标p指向有意义的第一个结点
    Node* p = first->next;
    //len记录长度 
    int len = 0;
    //只要p没到链表末尾 
    while (p)
    {
        //补全代码，完成长度的计算。 
        //就将p后移 
        p = p->next;

        //长度加一 
        len++;
        //------------------------------------------- 
    }
    //返回长度 
    return len;
}
//打印链表的数据。
void LinkList::PrintList() {
    //首先，将游标p指向有意义的第一个结点
    Node* p = first->next;
    if (!p) {
        //    cout << "链表无结点" << endl; 
    }
    else {
        //只要p没到链表末尾
        while (p)
        {
            //就输出该结点数据 
            cout << p->data << endl;
            //将p后移
            p = p->next;
        }
    }

}
//析构函数。 
LinkList::~LinkList() {
    //游标p从头开始
    Node* p = first;
    //结点指针s用来指向待删除的结点。
    Node* s;
    //只要p没到链表末尾 
    while (p)
    {
        //补全代码，完成结点的删除操作 
        //s标记好待删除结点 
        s = p;

        //p后移到下一个待删除结点 
        p = p->next;

        //注销s结点 
        delete s;
        s = 0;
        //------------------------------------------------
    }
}
//--------------------------------------------------------------------------------------------- 
//--------------------------------------------------------------------------------------------- 


//----------------------------------------------------------------------------- 
int main() {

    //-------------链表形式的栈操作验证--------------------------
    //利用基础链表类进行栈操作验证
    //建立栈 
    LinkList l;
    int i;
    //压栈的次数
    int num;
    //压栈的数据 
    int x;
    //输入压栈次数
    cin >> num;
    //依次压栈x 
    for (int i = 0; i < num; i++) {
        cin >> x;
        l.Insert_head(x);
    }

    //查看数据 
    l.PrintList();
    //查看栈长度 
    cout << l.Length() << endl;
    //出栈操作 
    for (i = 0; i < 2; i++) {
        //出栈操作 
        try {
            //补全代码
            int data;
            //利用Get方法弹出栈顶结点,保存至data，并输出
            data = l.Get(1);
            cout <<"出栈弹出数据:";

            //再利用Delete方法注销被弹出的栈顶结点
            l.Delete(1);

            //------------------------------------------------------------
        }
        catch (int) {
            cout << "栈空" << endl;
        }
    }

    //查看数据 
    l.PrintList();
    //查看栈长度 
    cout << l.Length() << endl;
    return 0;
}

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7647183
• 你也可以参考下这篇文章：【C++数据结构实验】基于双端队列的头插、头删操作，完成栈的应用：逆波兰表达式求值，测试和调试程序。
• 除此之外, 这篇博客: C++线性表的链式存储结构中的 为了更好的操作，测试相关函数的功能，写了这样一个函数来从文件得到链表长度的函数 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• template <class T>
  inline int LinkList<T>::readlen()
  {
  	ifstream readfile("data.txt");
  	int length;
  	readfile>>length;
  	return length;
  }
  

• 您还可以看一下 王健伟老师的C++语言基础到进阶课程中的 重载运算符、拷贝赋值运算符、析构函数小节, 巩固相关知识点
  
• 以下回答由chatgpt基于相关博客总结生成:

  答案：

  实现一个栈，需要实现压栈、弹栈、判断栈空、获取栈顶元素等基本操作。使用链表来实现栈类，需要创建一个链表类，并在其中实现压栈、弹栈、判断栈空、获取栈顶元素等基本操作。

  一个简单的链表类代码如下：

  template <class T>
  class LinkedList {
  public:
      /* 链表节点结构体 */
      struct Node {
          T data; // 数据域
          Node *next; // 指向下一个节点的指针
          Node(T data) : data(data), next(nullptr) {}
      };
  
      LinkedList() : head(nullptr), tail(nullptr) {}
      ~LinkedList() {
          // 析构函数
          Node *tmp = head;
          while (tmp != nullptr) {
              Node *next = tmp->next;
              delete tmp;
              tmp = next;
          }
          head = nullptr;
          tail = nullptr;
      }
      /* 在链表尾部添加一个节点 */
      void push_back(T data){
          Node *node = new Node(data);
          if (head == nullptr) {
              head = node;
              tail = node;
          } else {
              tail->next = node;
              tail = node;
          }
      }
      /* 在链表尾部插入一个节点 */
      void insert(T data){
          Node *node = new Node(data);
          if (head == nullptr) {
              head = node;
              tail = node;
          } else {
              node->next = head;
              head = node;
          }
      }
      /* 在链表头部弹出一个节点 */
      bool pop_front(T &data) {
          if (head == nullptr) {
              return false;
          }
          Node *tmp = head;
          data = tmp->data;
          head = head->next;
          delete tmp;
          return true;
      }
      /* 获取链表头部节点的数据 */
      bool front(T &data){
          if (head == nullptr) {
              return false;
          }
          data = head->data;
          return true;
      }
      /* 判断链表是否为空 */
      bool empty(){
          return head == nullptr;
      }
  private:
      Node *head; // 链表头指针
      Node *tail; // 链表尾指针
  };
  

  利用链表类实现栈类的代码如下：

  template <class T>
  class Stack {
  public:
      Stack() : size(0) {}
      ~Stack() {}
      /* 添加一个元素 */
      void push(T data) {
          linkedList.push_back(data);
          size++;
      }
      /* 删除一个元素 */
      bool pop(T &data) {
          if (linkedList.empty()) {
              return false;
          }
          linkedList.pop_front(data);
          size--;
          return true;
      }
      /* 获取栈顶元素 */
      bool top(T &data) {
          return linkedList.front(data);
      }
      /* 获取栈的大小 */
      int getSize() {
          return size;
      }
      /* 判断栈是否为空 */
      bool empty() {
          return linkedList.empty();
      }
  private:
      LinkedList<T> linkedList;
      int size;
  };
  

  栈的特性是先进后出，所以利用链表的头部作为栈的栈顶。push时在链表尾部添加一个节点，pop时从链表头弹出一个节点即可。由于链表的删除节点操作需要返回节点数据，使用一个bool类型的返回值代表操作是否成功，并使用一个传出参数data返回节点数据。top方法获取链表头部节点的数据，等价于栈的栈顶元素。getSize获取栈的大小，判断栈是否为空使用的也是链表的empty()方法，只不过封装成了Stack类的empty()方法，使得代码更易读。

  带有一些测试用例的完整代码请参考以下GitHub链接：

  https://github.com/zhouteng11/cpp-data-structure/blob/main/stack/stack_linkedlist.cpp

  参考文章：

  [1] 算法课1.3 快速排序[EB/OL].https://www.acwing.com/video/120/ (2019-08-14). [2] C++函数参数的传递方式[EB/OL].https://www.cnblogs.com/duanweishi/p/5253283.html (2015-08-20). [3] sizeof无法测量指针指向的数组大小？[EB/OL].https://duckduckgo.com/?q=sizeof%E6%97%A0%E6%B3%95%E6%B5%8B%E9%87%8F%E6%8C%87%E9%92%88%E6%8C%87%E5%90%91%E7%9A%84%E6%95%B0%E7%BB%84%E5%A4%A7%E5%B0%8F%EF%BC%9F&t=h_&ia=web (2021-09-16). [4] C++中如何获取数组长度 - 想生产数据科学家[EB/OL].https://www.jianshu.com/p/d21e8445f8aa (2019-03-13). [5] C++ 模板函数[EB/OL].https://www.runoob.com/cplusplus/cpp-function-template.html (无日期). [6] 漫画算法：小灰的算法之旅[EB/OL].https://github.com/greyireland/algorithm-pattern (2021-09-16).

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632