1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

Problem with Stack Implementation

Discussion in 'C++' started by ihatec, Oct 18, 2010.

  1. ihatec

    ihatec New Member

    Joined:
    Sep 1, 2010
    Messages:
    20
    Likes Received:
    3
    Trophy Points:
    0
    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();
    }
     
  2. jimblumberg

    jimblumberg New Member

    Joined:
    May 30, 2010
    Messages:
    120
    Likes Received:
    29
    Trophy Points:
    0
    And the problem is???

    Please post any error/warning messages.

    Jim
     
  3. ihatec

    ihatec New Member

    Joined:
    Sep 1, 2010
    Messages:
    20
    Likes Received:
    3
    Trophy Points:
    0
    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_1fc8b3b9a1e18e3b_9.0.21022.8_x-ww_597c3456\msvcp90d.dll', Symbols loaded.
    'labs_ads.exe': Loaded 'C:\WINDOWS\WinSxS\x86_Microsoft.VC90.DebugCRT_1fc8b3b9a1e18e3b_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.
     
  4. jimblumberg

    jimblumberg New Member

    Joined:
    May 30, 2010
    Messages:
    120
    Likes Received:
    29
    Trophy Points:
    0
    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
     
  5. ihatec

    ihatec New Member

    Joined:
    Sep 1, 2010
    Messages:
    20
    Likes Received:
    3
    Trophy Points:
    0
    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;
    
    
     
  6. jimblumberg

    jimblumberg New Member

    Joined:
    May 30, 2010
    Messages:
    120
    Likes Received:
    29
    Trophy Points:
    0
    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
     
    shabbir and ihatec like this.
  7. ihatec

    ihatec New Member

    Joined:
    Sep 1, 2010
    Messages:
    20
    Likes Received:
    3
    Trophy Points:
    0
    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.
     

Share This Page