c++ - 在 C++ 中使用链表进行堆栈

Question

我正在尝试使用 C++ 中的链表创建堆栈。但是我写的显示函数只打印堆栈的顶部。我真的不明白为什么会这样。非常感谢任何帮助或澄清。谢谢

#include<iostream.h>
#include<conio.h>

class Node
{
protected:

    Node* next;
    int data;

public:

    Node(int d){data=d;}
    friend class Stack;
};

class Stack
{
public:
    Stack(){top->next='\0';length=0;}

void push(int d)
{
    Node *n=new Node(top->data);
    n->next='\0';
    top->next=n;
    top->data=d;
    length++;
}

int pop()
{
    top=top->next;
    length--;
    return top->data;
}

void displaystack()
{
    while(top->next!='\0')
    {
        cout<<top->data<<endl;
    top=top->next;
    }
}

int getlength()
{
    return length;
}

private:
    Node *top;
    int length;

};

void main()
{
    clrscr();
    Stack s;
    s.push(9);
    s.push(8);
    s.push(7);
    s.push(6);
    s.push(5);
    s.push(3);
    s.displaystack();
    int len=s.getlength();
    cout<<"length of stack is "<<len<<endl;
    getch();
}

它只打印以下内容:3个栈的长度为6

--------xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx-------- -----

修改后的代码如下所示:并且也有效! (感谢@Kaathe):P

#include<iostream.h>
#include<conio.h>

class Node
{
protected:
Node* next;
int data;

public:

Node(int d){data=d;}
friend class Stack;
};

class Stack
{
public:
Stack(){top->next=NULL;length=0;}
~Stack()
{
     while(top!=NULL)
 {
   Node* toDelete=top;
   top=top->next;
   delete toDelete;
 }

}

void push(int d)
{
Node *n=new Node(d);
n->next=top;
top=n;
length++;
}

int pop()
{
 Node* oldtop=top;
 top=top->next;
 int oldtopdata=oldtop->data;
 delete(oldtop);
 --length;
 return oldtopdata;
}

void displaystack()
{
Node* current=top;
while(current->next!=NULL)
    {
    cout<<current->data<<endl;
    current=current->next;
    }
}

int getlength()
{
return length;
}

private:
Node *top;
int length;

};

Answer 1

当您push 时，您想要创建一个全新的节点，将其数据设置为值d，并将其指向旧的栈顶。然后您可以将堆栈的顶部设置为这个新节点。您实际上根本不需要修改旧的顶级节点。

因此推送可以读取:

void push(int d)
{
    Node* newTop = new Node(d);
    newTop->next = top;
    top = newTop;
    ++length;
}

我刚刚注意到 pop 也不会像预期的那样运行，因为您丢弃了顶部节点，并在其下方的节点中返回数据。也许你可以这样写:

int pop() 
{
    Node* oldTop = top;
    top = top->next;
    int oldTopData = oldTop->data;
    delete(oldTop);
    --length;
    return oldTopData;
}

阻止人们弹出空堆栈可能也是一个好主意(例如，通过在 pop() 的开头检查 length >= 1。

最后，displaystack 会在调用时破坏 Stack 对象，丢失指向顶部节点的指针。也许这样会更好:

void displayStack()
{
    Node* currNode = top;
    while(currNode->next != nullptr)
    {
        std::cout << currNode->data << std::endl;
        currNode = currNode->next;
    }
}

对我来说，以 nullptr 结束链表更有意义。

此外，堆栈应该有一个析构函数，它删除它的所有节点 - 我会让你写那个;)