Stack Using Linked List in C++

Question

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

#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();
}

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

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

After editing the code looks like this: and works too! (thanks to @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;

};

I cannot see how you initialize top of stack. "n->next='\0'; top->next=n;" should be "n->next= top->next; top->next=n;" — JackyZhu
– JackyZhu, Commented Aug 25, 2013 at 14:38
I'm trying to copy the data of "top" into n and make "top" point to "n" like this : top(points to n)->n(points to null) — Ishaan Sharma
– Ishaan Sharma, Commented Aug 25, 2013 at 14:40

Kaathe · Accepted Answer · 2013-08-25 15:05:51Z

2

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.

So push could read:

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

I just noticed that pop also 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:

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

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

Finally, displaystack will kind of destroy the Stack object if called, by losing the pointer to the top node. Maybe this would be better:

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

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

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

edited Aug 25, 2013 at 15:05

answered Aug 25, 2013 at 14:46

Kaathe

3353 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Ishaan Sharma Over a year ago

Question: Is putting a"nullptr" in *next not the same as putting '\0' ? Thank you so much @Kaathe for your patience! I know the mistakes are so naive!

Kaathe Over a year ago

'\0' is an end-of-string character - it's of type char. I would guess that it must automatically convert to 0 when you assign it to a pointer type, but writing nullptr makes it clearer what you are trying to do - finish the linked list with a pointer that points to null, rather than a Node.

Ishaan Sharma Over a year ago

~Stack() { while(top!=NULL) { Node* toDelete=top; top=top->next; delete toDelete; } }

jev · Accepted Answer · 2013-08-25 15:05:05Z

0

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

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

edited Aug 25, 2013 at 15:05

answered Aug 25, 2013 at 14:53

jev

2,0031 gold badge17 silver badges26 bronze badges

Comments

youdontneedtothankme · Accepted Answer · 2013-08-25 16:46:42Z

0

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

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

Solution is left as exercise for the reader ;-)

answered Aug 25, 2013 at 16:46

youdontneedtothankme

6724 silver badges6 bronze badges

2 Comments

Ishaan Sharma Over a year ago

could you please elaborate ? because the program is running! please give me a condition under which it won't ?

Ishaan Sharma Over a year ago

its working both, when i use top->next=NULL AND top=NULL. please help me understand!

jogo · Accepted Answer · 2016-01-28 15:05:36Z

0

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

edited Jan 28, 2016 at 15:05

jogo

12.6k11 gold badges41 silver badges43 bronze badges

answered Jan 28, 2016 at 14:44

Abhinav jain

1

Collectives™ on Stack Overflow

Stack Using Linked List in C++

4 Answers 4

3 Comments

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related