Problem with Stack Implementation

ihatec's Avatar, Join Date: Sep 2010
Go4Expert Member
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:rint()
{
//!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:ush(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:op(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();
}
0
jimblumberg's Avatar
Ambitious contributor
And the problem is???

Please post any error/warning messages.

Jim
0
ihatec's Avatar, Join Date: Sep 2010
Go4Expert Member
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.
0
jimblumberg's Avatar
Ambitious contributor
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
0
ihatec's Avatar, Join Date: Sep 2010
Go4Expert Member
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;
0
jimblumberg's Avatar
Ambitious contributor
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, shabbir likes this
0
ihatec's Avatar, Join Date: Sep 2010
Go4Expert Member
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.