在 C++ 中使用链表堆栈

Stack Using Linked List in C++

提问by Ishaan Sharma

I'm trying to create a stack using linked lists in c++. But the display function i have written prints only the top of the stack. I can't really understand why this is happening. Any help or clarification is much appreciated. Thanks

我正在尝试使用 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='
#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;

};
';length=0;}

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

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

void displaystack()
{
    while(top->next!='
int pop() 
{
    Node* oldTop = top;
    top = top->next;
    int oldTopData = oldTop->data;
    delete(oldTop);
    --length;
    return oldTopData;
}
')
    {
        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();
}

It only prints the following: 3 the length of stack is 6

它只打印以下内容： 3 堆栈的长度为 6

--------xxxxxxx-------xxxxxxxx--------xxxxxxx-----------xxxxxxxxxxxxx--------------

--------xxxxxxx-------xxxxxxxx--------xxxxxxx-----------xxxxxxxxxxxxx------------ ——

After editing the code looks like this: and works too! (thanks to @Kaathe) :P

编辑后的代码看起来像这样：并且也可以工作！（感谢@Kaathe）：P

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

回答by Kaathe

When you push, you want to create an entirely new Node, set its data to the value d, and point it at the old top of the stack. You can then set the top of the stack to this new node. You actually don't need to modify the old top node at all.

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

So push could read:

所以推可以读：

Stack(){top->next=NULL;length=0;}

I just noticed that popalso won't behave as expected, as you throw away the top node, and return the data in the node below it. Maybe you could write:

我只是注意到pop，当您丢弃顶部节点并返回其下方节点中的数据时，它也不会按预期运行。也许你可以写：

##代码##

It would probably also be a good idea to stop people from popping empty stacks (for example by checking that length >= 1at the start of pop().

阻止人们弹出空堆栈可能也是一个好主意（例如通过length >= 1在pop().

Finally, displaystackwill kind of destroy the Stackobject if called, by losing the pointer to the top node. Maybe this would be better:

最后，如果被调用，将通过丢失指向顶部节点的指针来displaystack销毁Stack对象。也许这样会更好：

##代码##

It makes more sense to me to end the linked list with a nullptrtoo.

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

Also, the stack should have a destructor which deletes all its Nodes - I'll let you write that one ;)

此外，堆栈应该有一个析构函数，delete它Node是它的所有s - 我会让你写那个 ;)

回答by jev

When you print (in displaystack) you should use a temporary variable instead of destructively updating the top variable.

当您打印 (in displaystack) 时，您应该使用临时变量而不是破坏性地更新顶部变量。

To avoid a memory leak in pop()you should also deletethe node previously allocated using new.

为了避免内存泄漏，pop()您还应该delete使用先前分配的节点new。

回答by youdontneedtothankme

I would be surprised if your program works if you still have this in your code:

如果您的代码中仍然有这个，如果您的程序有效，我会感到惊讶：

##代码##

Solution is left as exercise for the reader ;-)

解决方案留给读者作为练习;-)

回答by Abhinav jain

You can replace while(top->next!='\0')to while(top!='\0')It should work then...

您可以替换while(top->next!='\0')为while(top!='\0')它应该可以工作然后...