Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   Problem with Stack Implementation (http://www.go4expert.com/forums/stack-implementation-t23603/)

ihatec 18Oct2010 10:15

Problem with Stack Implementation
 
At school as a task I had to implement a stack as a list in Visual Studio 2010 and there is a problem but I don't know how to use debugger yet and I have only 12 hours to improve my solution and after that lectutrer will make some auto testing. PLEASE HELP ME
File with Stack class and description of each method

#include <stdio.h>
#include <iostream>

using namespace std;

class Stack
{
public:
/*
Puts given item on the top of a stack.
Returns 0 if no error occured and 1 otherwise (e.g. lack of memory).
*/
virtual int push(int) abstract;

/*
Gets top element of the stack and removes it from the stack.
Element is stored using a pointer argument. If argument is null,
the element is removed without storing its value.
Returns 0 if no error occured and 1 otherwise (e.g. stack is empty).
*/
virtual int pop(int* item = NULL) abstract;

/*
Gets the top element of the stack (without removing it) using pointer argument.
Returns 0 if no error occured and 1 otherwise (e.g. stack is empty).
*/
virtual int top(int*) abstract;

/*
Removes all the elements from the stack.
*/
virtual void clear() abstract;

/*
Returns the number of items in the stack.
*/
virtual int getCount() abstract;

/*
Returns true if the stack is empty and false otherwise.
*/
virtual bool isEmpty() abstract;

/*
Prints current items in the stack starting from the top.
*/
virtual void print() abstract;
};

FILE WITH LISTSTACK CLASS AND GIVEN TIME COMPLEXITY

#include "Stack.h"

class ListStack :
public Stack
{
public:
ListStack();
~ListStack();
int push(int) override ; //O(1)
int pop(int*) override ; //O(1)
int getCount() override; //O(1)
int top(int*) override; //O(1)
void clear() override; //O(n)
bool isEmpty() override; //O(1)
void print() override; //O(n)

private:
struct node
{
public:
int value;
node* next;
};

node* head;
int count;
};

FILE WITH LISTSTACK METHODS IMPLEMENTATION

#include "ListStack.h"

ListStack::ListStack()
{
head=NULL;
count=0;
}
ListStack::~ListStack()
{
clear();
}
bool ListStack::isEmpty()
{
if(count<=0)
return true;
else
return false;
}
void ListStack::print()
{
//!isEmpty()? cout << "Stack content: " <<endl : cout <<"Stack is Empty!!!" << endl;
node *tmp;
for(tmp=head;tmp!=NULL;tmp=tmp->next)
cout << tmp->value <<endl;
}
int ListStack::push(int x)
{
int tempcount=getCount()+1;
if(tempcount<getCount())
return 1;
node *ptr=head;
head = new node;
if(!head)
return 1;
head->value=x;
head->next=ptr;
count++;
return 0;
}
int ListStack::top(int *ptr)
{
if(!head && count<=0)
return 1;

if(ptr)
*ptr=head->value;
return 0;
}
int ListStack::getCount()
{
return count;
}
void ListStack::clear()
{
for(int i=0;i<count;++i)
{
node *temp=head;
head=head->next;
delete temp;
}
count=0;
head=NULL;
}


int ListStack::pop(int *item)
{
if(head && count<=0)
return 1;
if(item)
*item=head->value;
node *ptr=head;
head=head->next;
delete ptr;
count--;
return 0;
}


FILE WITH MAIN FUNCTION

#include "ListStack.h"

using namespace std;

int main()
{
int item = 0;
cout << "\nStack\n";
Stack* s = new ListStack;
s->print();
s->pop();
s->print();
s->push(2);
s->print();
s->push(1);
s->print();
s->push(3);
s->print();
s->pop(&item);
cout<<endl<<item<<endl;
s->print();
s->pop(&item);
cout<<endl<<item<<endl;
s->print();
s->pop(&item);
cout<<endl<<item<<endl;
s->print();
s->pop(&item);
s->print();
}

jimblumberg 18Oct2010 20:03

Re: Problem with Stack Implementation
 
And the problem is???

Please post any error/warning messages.

Jim

ihatec 18Oct2010 21:38

Re: Problem with Stack Implementation
 
Ok when I compile it, there is no error/warning messages there is only something like this.

'labs_ads.exe': Loaded 'C:\Documents and Settings\Trusiek\Moje dokumenty\Visual Studio 2008\Projects\Project1\labs_ads\Debug\labs_ads.exe ', Symbols loaded.
'labs_ads.exe': Loaded 'C:\WINDOWS\system32\ntdll.dll'
'labs_ads.exe': Loaded 'C:\WINDOWS\system32\kernel32.dll'
'labs_ads.exe': Loaded 'C:\WINDOWS\WinSxS\x86_Microsoft.VC90.DebugCRT_1fc 8b3b9a1e18e3b_9.0.21022.8_x-ww_597c3456\msvcp90d.dll', Symbols loaded.
'labs_ads.exe': Loaded 'C:\WINDOWS\WinSxS\x86_Microsoft.VC90.DebugCRT_1fc 8b3b9a1e18e3b_9.0.21022.8_x-ww_597c3456\msvcr90d.dll', Symbols loaded.
First-chance exception at 0x00411a91 in labs_ads.exe: 0xC0000005: Access violation reading location 0x00000004.
Unhandled exception at 0x00411a91 in labs_ads.exe: 0xC0000005: Access violation reading location 0x00000004.
The program '[13484] labs_ads.exe: Native' has exited with code 0 (0x0).

and debugger opens, and points to the line head=head->next in pop fuction but I don't know how to use debugger.

jimblumberg 18Oct2010 23:49

Re: Problem with Stack Implementation
 
The first error happens when
Code:

int main()
{
int item = 0;
cout << "\nStack\n";
Stack* s = new ListStack;
s->print();
s->pop();  /////// Error here.

If you comment out that line the program will run until the last
Code:

s->pop(&item);
call. If you comment out that line then the program runs to the end.

NOTE: PLEASE USE CODE TAGS
Jim

ihatec 19Oct2010 03:28

Re: Problem with Stack Implementation
 
Ok I comment out every call of pop function and it works but how to make it works this function, because the only thing I could do in this program is to implement the methods and make them compatible with other files(stack.h, ListStack.h, main.cpp) and ofter implementation it would be auto tested by the lecturer if it works ok I get points, if not I get 0 points. Please help me with this function if this is the reason and assume every call of this function looks like:
Code:

s->pop(&item);

/*
        Gets top element of the stack and removes it from the stack.       
        Element is stored using a pointer argument. If argument is null,
        the element is removed without storing its value.
        Returns 0 if no error occured and 1 otherwise (e.g. stack is empty).
        */
        virtual int pop(int* item = NULL) abstract;


jimblumberg 19Oct2010 03:36

Re: Problem with Stack Implementation
 
I think the pop function works for all cases except when you try to pop an empty stack. You may need to check for an empty condition and take action based on that.

I am not too familiar with stacks so I can not tell you what to do for an empty stack.

Jim

ihatec 19Oct2010 04:35

Re: Problem with Stack Implementation
 
Thanks for all, I finally found what was wrong when you said about empty stack condition. I made a mistake in conditions of pop function. Now everything works ok.


All times are GMT +5.5. The time now is 17:30.