?
Solved

Stack, Linked List - help on code :(

Posted on 2003-03-28
17
Medium Priority
?
347 Views
Last Modified: 2013-12-14
Ok I posted a question a day or so ago asking about a stack implemented as an array... I got that code working and now I am looking at a linked list implementation, and basically I am very confused and am not totally aware of how a linked list works but I have some code written up.  Maybe someone could take a look at it and let me know how to improve it or provide an example??  Because I know what I have it wrong, and Im not sure where to go from here... be ready, here is my ugly code :)

1. Is my general code correct?
2. Any way to shorten or improve the pop/push methods?
3. I am very unsure how isFull would work?
4. Any other tips appreciated.

stack.h
----------
#ifndef LOTTERY_H
#define LOTTERY_H

struct Node
{
  Node* next;
  Node* previous;
  int Data;
}

class Stack
{
 public:
  Stack();
  void push(int);
  int pop();
  bool isFull();
  bool isEmpty();

 private:
  node top;
  node *current;
};

#endif

--------------
stack.cpp
--------------
#include "stack.h"

Stack::Stack()
{
  top=NULL;
}

void Stack::push(int item)
{
  node *temp=current;
  current->next=new node;
  current=current->next;
  current->data=item;
  current->previous=temp;
}

int Stack::pop()
{
  int temp;
  temp=current->data;
  if(current->previous==NULL)
    {return temp;}
  current=current->previous;
  delete current->next;
  return temp;
}

bool Stack::isFull();
{
  // ??
}

bool Stack::isEmpty();
{
  return(top==NULL;)
}



0
Comment
Question by:killer455
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 10
  • 6
17 Comments
 
LVL 16

Expert Comment

by:imladris
ID: 8228254
1. Yup. I don't see any obvious problems.
2. Nope. That's the level of effort that has to go in. You have to take care of all those pointers.
3. The joy of a linked list implementation of a stack is that it doesn't really get full until you run out of memory. The only other option would be to arbitrarily limit it to some reasonable size. In that case you would need a function that runs through the list and counts how many elements are in it. Then isFull would return true if there are that many elements in the "stack".

0
 
LVL 15

Expert Comment

by:efn
ID: 8228452
1.  It's sort of on a potentially working track, but it has bugs.

2.  You could simplify the design by using a singly linked list instead of a doubly linked list.  You don't really need a doubly linked list to implement a stack.  I don't know if you have some other externally imposed requirement to use a doubly linked list.  For a doubly linked list, you have roughly the right amount of code.

3.  See imladris's comment.  With a dynamically allocated linked list, isFull isn't very meaningful.  The stack's capacity depends on the push function's ability to allocate memory for a new node, which could be changing all the time.  That is, even if you coded isFull to try to allocate a Node as a test to see whether a following call to push would work, conditions could change between the isFull and push calls, so the test might not be reliable.

4.  If you try to compile this code, the compiler should tell you about some of the errors.

A few other hints:

The push function won't work with an empty stack.

You don't need both the top and current variables.  top is initialized, but used only in isEmpty.  current is used, but not initialized.

Consider what you want to happen if somebody calls pop on an empty stack.  As it is, this will probably blow up the program.

As it's coded, a stack with only one node will return that same node's data forever.  That is, the pop function does not empty the stack in this case.

--efn
0
 

Author Comment

by:killer455
ID: 8228473
I think there are a lot of problems, when I try to compile with a easy test program I get a ton of errors.

In file included from stack_test.cpp:1:
stack.h:17: semicolon missing after declaration of `Node'
stack.h:26: syntax error before `;'
stack.h:27: syntax error before `*'
stack.h:28: multiple types in one declaration
In file included from stack.cpp:6:
stack.h:17: semicolon missing after declaration of `Node'
stack.h:26: syntax error before `;'
stack.h:27: syntax error before `*'
stack.h:28: multiple types in one declaration
stack.cpp: In method `Stack::Stack ()':
stack.cpp:10: `top' undeclared (first use this function)
stack.cpp:10: (Each undeclared identifier is reported only once for
each function it appears in.)
stack.cpp:10: `NULL' undeclared (first use this function)
stack.cpp: In method `void Stack::push (int)':
stack.cpp:15: `node' undeclared (first use this function)
stack.cpp:15: `temp' undeclared (first use this function)
stack.cpp:15: `current' undeclared (first use this function)
stack.cpp:16: parse error before `;'
stack.cpp: At top level:
stack.cpp:34: declaration of `bool Stack::isFull ()' outside of class
is not definition
stack.cpp:35: parse error before `{'
stack.cpp:39: declaration of `bool Stack::isEmpty ()' outside of class
is not definition
stack.cpp:40: parse error before `{'
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:killer455
ID: 8228489
I guess I do only need a single linked list.
I dunno I am just not very familiar with linked list and this makes it very confusing at this point.
0
 

Author Comment

by:killer455
ID: 8228566
Well i've tried rewriting the code and now am getting even more errors, if anyone can help me get these 4 methods down, as a stack/linked list implementation down let me know.

0
 

Author Comment

by:killer455
ID: 8228788
Ok here is my new code.

1. Is there anything else I need under the private:
2. Do I need to check for isEmpty for the pop method??
3. I need isFull to check whether it can create another node based on memory, is there any easy way to do this?


---------
stack.h
---------
#ifndef LOTTERY_H
#define LOTTERY_H

struct Node
{
  int value;
  Node *next;
}

class Stack
{
 public:
  Stack();
  void push(int);
  int pop();
  bool isFull();
  bool isEmpty();

 private:
  Node *top;
};

#endif

----------
stack.cpp
----------
#include "stack.h"

Stack::Stack()
{
  top=NULL;
}

void Stack::push(int item)
{
  Node*temp=new Node;
  temp->value=item;
  temp->next=top;
  top=temp;
}

int Stack::pop()
{
  Node*temp=top;
  int x=temp->value;
  top=top->next;
  delete temp;
  return x;
}

bool Stack::isFull();
{
  return 0; // not sure what i want to do here
}

bool Stack::isEmpty();
{
  return(top==NULL;)
}



0
 
LVL 15

Expert Comment

by:efn
ID: 8228897
Hey, you've made a lot of progress.  Congratulations.

1.  I don't think you need anything more.

2.  If somebody tries to pop an empty stack, the program will probably blow up when it tries to dereference the null pointer temp.  If you can somehow guarantee that nobody will ever try to pop an empty stack, you don't need to worry about it.  Otherwise, it would be a good idea to check for an empty stack in the pop function.  If you do that, you have to decide what you want the function to do in that case--such as throw an exception, return zero, or return -1.

3.  I don't think there is any portable way to find out whether you could hypothetically allocate some memory if you wanted to.  The straightforward approach would be just to try to allocate a node.  If allocation fails, isFull returns true; otherwise, it deallocates the test node and returns false.

--efn
0
 

Author Comment

by:killer455
ID: 8229081
Thanks efn.

Just a few more quick questions.

For #2. (above) what do you mean by throw an exception?  Also why would you want it to return -1?  Wouldnt you just want it to return 0 if it could not pop? I dunno, lemme know what you think.

For #3. (above) ok your explanation is what i needed, that what I was trying to get across :)  How would I allocate a node... like...

if(allocation = new Node)
   return 1;
else
   delete allocation;

or do i need a pointer or something... or something totally different?

Also one other quick question, do I need a destructor?

Thanks a lot for the help, sorry if I am dragging this out, I will raise the answer points before I accept an answer.

Thanks to efn, for the generous help.

Ben
0
 

Author Comment

by:killer455
ID: 8229086
for code in last comment...
it should be

if(!allocation=new Node)
   return 1
else
   delete allocation
   return 0;

I dont know if this is right, but its the correction to my attempt in the above comment.
0
 
LVL 15

Accepted Solution

by:
efn earned 420 total points
ID: 8229384
Hi Ben,

Exceptions are a feature of C++ that lets you bomb out of the middle of some code, "throwing" a hopefully informative object that can be "caught" by some other calling code.  It's kind of a big subject to explain here (there are one-day courses on just C++ exceptions); you can look it up in whatever you use as a C++ reference source or on the Web, for example, here:

http://www.freshsources.com/Except1/ALLISON.HTM

If you are not going to have the function throw an exception, ideally it should return some special magical value it would never otherwise return.  If the stack were intended to be used only with positive numbers, zero or a negative number could indicate an error.  Similarly, if the stack were intended to be used only for non-negative numbers, a negative value could indicate an error--that's why I suggested -1.  But if the stack is to be used for any int at all, you're stuck--there is no way to distinguish the error code from the same number previously pushed on the stack.  This is not good.

For a test allocation, you can use the new operator, just as you are already doing.  In fact, you can practice exception handling, because if the new operator can't allocate memory, by default, it throws an exception.

That might look something like this:

Node* tester = 0;

try
{
  tester = new Node;
}
catch (std::bad_alloc)
{
  // If allocation fails, control comes here,
  // else this block is skipped.
  return true;
}

// Allocation succeeded.
delete tester;  // Avoid memory leak.
return false;

If you don't want to mess with the wizardly complexities of exceptions, there is a simpler way.  You can tell the new operator not to throw an exception like this:

Node* tester = new (nothrow) Node;

If you do this, you will get a null pointer returned instead of an exception thrown if the new operator cannot allocate the memory, and code like what you posted should work.

If you are working with an old compiler, it might return a null pointer by default rather than throwing a bad_alloc exception.

Finally, you don't need a destructor to make it work, but you do need one to avoid memory leakage.  Nothing but your own destructor will deallocate all the dynamically allocated Nodes in the linked list.

You're welcome.  I'm glad my advice was useful.

--efn
0
 

Author Comment

by:killer455
ID: 8231884
Ok sounds good.  Just out of interest, is there a simple way of explaining what try { } does?  and do I need an include for the std? You also mentioned if I dont want to mess with your new code, my code posted above will work?  Just wanting to confirm that it will work... here is the code so you know for sure what i am talking about.

 if(!allocation=new Node)
  return 1
else
  delete allocation
  return 0;

I'm familiar with a destructor for an array implementation but when deleting a linked list do you simply set top=NULL ?

BTW, i raised the points some :)  Thanks for your continued help.

Thanks,
Ben
0
 
LVL 15

Expert Comment

by:efn
ID: 8232070
A "try" statement goes with one or more "catch" statements to specify what to do with exceptions.

try x;
catch (exceptiontype1) y;
catch (exceptiontype2) z;

I used simple pseudostatements here instead of blocks so you can see what is going on.  If the execution of x throws an exceptiontype1 exception, y gets executed.  Similarly, if the execution of x throws an exceptiontype2 exception, z gets executed.  If x doesn't throw any exception, neither y nor z gets executed.

You will need to #include <new> to get std::bad_alloc declared.

I don't think your code will work.  First, the prefix ! has higher precedence than the assignment operator =, so

!allocation = new Node

is equivalent to

(!allocation) = new Node

but what you want is

!(allocation = new Node)

Second, for this code to work, you need "new Node" to return a null pointer if allocation fails.  It may do this if you have an old compiler, but if your compiler works according to the standard, it won't, unless you add the (nothrow) specification I mentioned above.

As a style note, it would be better to return true and false rather than 1 and 0.

To avoid memory leaks, the rule is to use "delete" on everything for which you ever used "new".  In your case, every Node on the Stack is created with "new", so the destructor should traverse the list and delete each Node.  Since the pop function already does this, the destructor could just call pop until the list is empty.

--efn
0
 

Author Comment

by:killer455
ID: 8232504
You mentioned that in my code every Node is created with "new", is there a better way this or something? or do you think it is sufficient for the small size of my program and that a loop in the descructor would work fine?

Here is my updated code, looking good?  The next thing I wanted to experiment with was using a template.  I might post a new question on that but if i get the code done which I think is pretty easy to do, I will post it here and up the points.

Ben


#include "stack.h"

Stack::Stack()
{
  top=NULL;
}

Stack::~Stack();
{
  // destructor, no code yet
}

void Stack::push(int item)
{
  if(!isFull())
    {
      Node*temp=new Node;
      temp->value=item;
      temp->next=top;
      top=temp;
    }
  else
    {
      return -1;
    }
}

int Stack::pop()
{
  if(!isEmpty())
    {
      Node*temp=top;
      int x=temp->value;
      top=top->next;
      delete temp;
      return x;
    }
  else
    {
      return -1;
    }
}

bool Stack::isFull()
{
  Node*tester=new(nothrow) Node;
  if(!(tester=new Node))
    {
      return true;
    }
  else
    {
      delete tester;
      return false;
    }
}

bool Stack::isEmpty()
{
  return(top==NULL;)
}






0
 
LVL 15

Expert Comment

by:efn
ID: 8232639
Creating Nodes with "new" is just fine, and a delete (or pop) loop in the destructor is also just fine.

There's a bug in isFull.  It allocates two Nodes.  One would be enough.

The push function can't very well return -1 since its return type is void.  As in the case of popping from an empty stack, you have to decide what you want a Stack to do when somebody tries to push an element on it and it can't allocate memory for the Node.  A typical implementation would not have an isFull function and would just let push throw a bad_alloc exception and let the client deal with it.

I don't see anything else to carp about at the moment.

--efn
0
 

Author Comment

by:killer455
ID: 8232722
So would i simply write

 Node*tester=new(nothrow) Node;
 if(!(tester))

??

0
 
LVL 15

Expert Comment

by:efn
ID: 8232797
Yes, that would work.

If you wanted to make it a little more explicit, you could write something like

if (tester == 0)

But that's just style.
0
 

Author Comment

by:killer455
ID: 8233189
Ok thanks for your help efn, you got me through this :)  Like I mentioned before I might post another question concerning templates, so just in case you are interested in answering it, it will be up there.

Ok thanks again, and thanks to everyone else you posted tips/help.

Ben
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Here is a helpful source code for C++ Builder programmers that allows you to manage and manipulate HTML content from C++ code, while also handling HTML events like onclick, onmouseover, ... Some objects defined and used in this source include: …
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
THe viewer will learn how to use NetBeans IDE 8.0 for Windows to perform CRUD operations on a MySql database.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
Suggested Courses

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question