将栈模板改用链表的方式实现?

Question

题目描述

将栈模板改用链表的方式实现

题目来源及自己的思路

题目来源：https://blog.csdn.net/weixin_...
思路：以链表为底层数据结构

相关代码

粘贴代码文本（请勿用截图）

//Stack.h
#ifndef STACK_H
#define STACK_H
#include "ListNode.h"

template <class Type>
class Stack
{
public:
    //构造函数
    Stack()
    {
        top=NULL;
    }
    //析构函数
    ~Stack()
    {

        while(top!=NULL)
        {
            ListNode<Type> *tempNode=top;
            top=top->GetNext();
            delete tempNode;
        }
    }
    //新元素进栈
    void Push(const &x)
    {
        ListNode<Type>  *newNode=new ListNode<Type>(x);
        if(top==NULL)
        {
            top=newNode;
        }
        else
        {
            newNode->SetNext(top);
            top=newNode;
        }
    }
    //栈顶元素出栈
    Type Pop()
    {
        if(top==NULL)
        {
            return NULL;
        }
        Type data=top->GetData();
        ListNode<Type> *tempNode=top;
        delete tempNode;
        top=top->GetNext();
        return data;
    }
    //判断当前栈是否为空
    bool IsEmpty()
    {
        if(top==NULL)
            //为空的时候返回false
            return false;
        else
            //非空的时候返回true
            return true;
    }
    //获取当前栈有多少个元素
    int Size()
    {
        int num=0;
        ListNode<Type> *current=top;
        while(current!=NULL)
        {
            current=current->GetNext();
            num++;
        }
        return num;
    }
    //获取栈顶元素
    Type Top()
    {
        if(top!=NULL)
            return top->GetData();
        return NULL;
    }
private:
    ListNode<Type> *top;
};
#endif // STACK_H

//ListNode.h
#ifndef LISTNODE_H
#define LISTNODE_H
#include<iostream>

using namespace std;
template<class Type>
class ListNode
{
public:

    //链表结点构造函数
    ListNode ( ):link(NULL) {}
    ListNode ( const Type& item ):data(item),link(NULL) {}
    ~ListNode()
    {
    }
    Type GetData()
    {

        return  data;
    }
    ListNode<Type> *GetNext()
    {
        return link;

    }
    void SetNext(ListNode<Type> *node)
    {
        link=node;
    }
private:
    Type data;
    ListNode<Type> *link;
};
#endif // LISTNODE_H

//3_main.cpp
#include <iostream>
#include "Stack.h"
using namespace std;

int main()
{
    Stack<int> *mstack=new Stack<int>();
    for(int i=10; i<20; i++)
        mstack->Push(i);
    mstack->Pop();
    mstack->Push(99);
    cout<<"当前栈中元素个数:"<<mstack->Size()<<endl;
    cout<<"栈顶元素是："<<mstack->Top()<<endl;

    cout<<"当前栈中的所有的元素(栈顶--->栈底)："<<endl;
    while(mstack->IsEmpty())
    {
        cout<<mstack->Top()<<"  ";
        mstack->Pop();
    }
    cout<<endl;
    //释放内存
    delete mstack;
    return 0;
}

你期待的结果是什么？实际看到的错误信息又是什么？

我把Stack.h中的#include<Stack.h>改为#include "Stack.h"
运行时就卡在这不动了!

C:\software\Edu\VSCode\C++\Exp8\9-3\Stack.h: In instantiation of 'Type Stack<Type>::Pop() [with Type = int]':
C:\software\Edu\VSCode\C++\Exp8\9-3\test3.cpp:11:17: required from here
C:\software\Edu\VSCode\C++\Exp8\9-3\Stack.h:46:20: warning: converting to non-pointer type 'int' from NULL [-Wconversion-null]

         return NULL;

image.png

Answer 1

除了 fefe 所指出的问题外，你的错误信息是一些警告，主要是说:

//栈顶元素出栈
Type Pop()
{
    if(top==NULL)
    {
        return NULL;
    }
    ...
}

如果 top 是 NULL 你返回 NULL，但 NULL 通常是用于指针类型，当 Type 是 int 的时候，反回 NULL 只是警告你。如果 Type 是一个 class，你返回 NULL 就有问题了。这里需要改为：

    return Type{};

Answer 2

        ListNode<Type> *tempNode=top;
        delete tempNode;
        top=top->GetNext(); // top 已经被 delete 了，调用结果未定义。
                            // 这句应该在 delete 之前。