85840

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; };

Answer1:

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 ;)

Answer2:

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.

Answer3:

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 ;-)

Answer4:

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

Recommend

  • Unexpected behavior of floating point numbers in C [duplicate]
  • Finding nth power of integer m through C program without pow()
  • Illegal Initialization In C Program
  • Using inp() on 16Bit Dos 5with Turbo C++ 3.0
  • Writing a backspace in a file
  • how can I strcat one character to array character in c++
  • How do I limit the amount of characters in JTextPane as the user types (Java)
  • c++ Linked List losing data between functions
  • Android Xml parsing error on new android versions
  • linked list program
  • hashmap in android xml parsing
  • Python: “Print” and “Input” in one line [duplicate]
  • What is wrong with this emulation of CMPXCHG16B instruction?
  • Iterating over a container bidirectionally
  • std::system Exception when instantiating a singleton object
  • How can I count unique terms in a plaintext file case-insensitively?
  • Programmatically Update Linked Named Range of excel object in MS Word (2007)
  • OpenMP and File I/O
  • How do I translate LR(1) Parse into a Abstract syntax tree?
  • Is there any way to call saveCurrentTurnWithMatchData without sending a push notification?
  • Angular Bootstrap Carousel Slide Transition not working correctly
  • Silverlight DependencyProperty.SetCurrentValue Equivalent
  • Remove final comma from string in vb.net
  • copying resource to sdcard gives a damaged file in android
  • why overloaded new operator is calling constructor even I am using malloc inside overloading functio
  • Alert pop up with LWUIT
  • output of program is not same as passed argument
  • Javascript + PHP Encryption with pidCrypt
  • Akka Routing: Reply's send to router ends up as dead letters
  • How can I get HTML syntax highlighting in my editor for CakePHP?
  • Suggestions to manage Login/Logout transitions
  • Getting Messege Twice Using IMvxMessenger
  • Exception on Android 4.0 `android.os.StrictMode$AndroidBlockGuardPolicy.onNetwork(StrictMode)`
  • unknown Exception android
  • EntityFramework adding new object to nested object collection
  • Checking variable from a different class in C#
  • How can i traverse a binary tree from right to left in java?
  • failed to connect to specific WiFi in android programmatically
  • How to push additional view controllers onto NavigationController but keep the TabBar?
  • How can I use threading to 'tick' a timer to be accessed by other threads?