C++

Forum

 
my stack class

MRKSalman0349 (51)
hey guys i was trying to make this vector class

this works fine but i have a few questions ...if you plz help me .....
i used linked list to make my class.... is it proper??

1-Am i deallocating memory properly?
2-what should i do to make my code even better and exception safe?
3-where my code will fail?

plz explain so that i could do much better .... looking for your help...plzz

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
 
#include <iostream>
#include <cstdlib>

using namespace std;

template <class T>
class Stack 
{ 

private:
	int size;
	
public:
// Struct to hold vector elements	
struct Vector{
	T elem;
	Vector *next;
};

Vector *head;
Vector *last;

//---------------------------------------Constructor----------------------------------------
Stack(){
head = NULL;
last = NULL;
size = 0;

}


//---------------------------------------public member functions----------------------------------------
void push(T const &);
T top();
bool remove(T const );
bool isEmpty();
void print_Stack();

int Size(){
return size;
}

//---------------------------------------Destructor----------------------------------------

~Stack(){
	delete head;
	delete last;
}


};


template <class T>
bool Stack<T>::remove(T const rem){
	Vector *tr = head;
	Vector *previous = head;
	bool removing = false;

	while (tr !=NULL)
	{
		previous = tr;
		tr = tr->next;
		if (tr->next == NULL && tr->elem != rem)
		{
			last = tr;
			removing = false;
			break;
		}
		else if (tr->elem == rem){

			tr = tr->next;
			previous->next = tr;
			size--;
			removing = true;
			break;
		}
		
	}
	//delete tr;
	//delete previous;
	return removing;
	
}


template <class T>
bool Stack<T>::isEmpty(){
	bool empt;
	if ( head ==NULL )
	empt = true;
	else empt = false;
	return empt;
}


template <class T>
void Stack<T>::push (T const& elem) {
	
	Vector *newelem = new Vector;
	newelem->elem = elem;
	newelem->next = NULL;
	
	if ( head == NULL )
	{
		head = newelem;
		last = newelem;
		size++;
	}
	else
	{
		last->next = newelem;
		last = newelem;
		size++;
	}
	//delete newelem;
}

template <class T>
void Stack<T>::print_Stack(){
	Vector *tr = head;
	
	while (tr != NULL)
	{
		cout << tr->elem << endl;
		tr = tr->next;
	}
	delete tr;
}


template<class T>
T Stack<T>::top(){
	T topElem;
	topElem = head->elem;
	return topElem;
}



main(){
	//cout << "not implemented yet: " << endl;
	
	Stack <int>stack;
	stack.push(5);
	stack.push(6);
	stack.push(7);
	stack.push(8);
	stack.push(9);
	
	stack.print_Stack();
	cout << endl;
	cout << "Size of stack before removing :" << stack.Size() << endl;
	if ( stack.isEmpty() )
	{
		cout << "stack is empty : " << endl;
	}
	else
	{
		cout << "The stack is not empty : " << endl;
	}
	
	if (stack.remove(7))
	{
		cout << "The number is removed : " << endl;
		stack.print_Stack();
		cout << "Size of stack after removing :"  << stack.Size() << endl;
		
	}
	
	cout << "Top element in the stack : " << stack.top() << endl;
	
	system("pause");
}
helios (17575)
1. No.
3. Stack::~Stack() is incorrect. In some cases it leaks memory, in other cases it deletes the same pointer twice. It only behaves correctly if Stack::size == 0.
MRKSalman0349 (51)
then what sholud i do to make it do better helious?? plz help me
I'll be very thankfull to you .......
giblit (3750)
1
2
3
4
 
~Stack(){
	delete head;
	delete last;
}
you are going to need to delete each pointer that was allocated. You should start from the top of the stack and work towards the bottom deleting everything.

Also, your main function should return int
MRKSalman0349 (51)
when i delete 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
template <class T>
bool Stack<T>::remove(T const rem){
	Vector *tr = head;
	Vector *previous = head;
	bool removing = false;

	while (tr !=NULL)
	{
		previous = tr;
		tr = tr->next;
		if (tr->next == NULL && tr->elem != rem)
		{
			last = tr;
			removing = false;
			break;
		}
		else if (tr->elem == rem){

			tr = tr->next;
			previous->next = tr;
			size--;
			removing = true;
			break;
		}
		
	}
//when i delete these pointers an infinite loop starts .... i don't know why???
	delete tr;
       delete previous;
	return removing;
	
}


please help giblit
giblit (3750)
1
2
3
4
 
//when i delete these pointers an infinite loop starts .... i don't know why???
	delete tr;
       delete previous;
	return removing;
At that point tr will be null. So deleting null is probably undefined behavior I have never tried it though.

I have never made a stack before but here is a simple version I came up with 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
#include <iostream>

template <class T>
struct Node
{
    Node *next;
    T value;
};

template <class T>
class Stack
{
    public:
        Stack() : top(new Node<T>), size(0)
        { 
            top->next = nullptr;
            //value is undefined because there is nothing on the stack
        }
        ~Stack()
        {
            while(top != nullptr)
            {
                Node<T> *next = top->next;
                delete top;
                top = next;
            }
        }

        std::size_t length(void) const {return size;}

        void push(T value) //pushes item onto stack
        {
            Node<T> *temp = new Node<T>{top, value};
            top = temp;
            ++size;
        }

        T pop(void) //removes top item and returns it
        {
            if(size < 1)
            {
                throw("Error - Can't pop an empty stack.");
            }

            T temp = top->value;

            Node<T> *next = top->next;
            delete top;
            top = next;

            --size;
            return temp;
        }

        T peek(void) //returns top item
        {
            if(size < 1)
                throw("Error - The stack is empty.");
            return top->value;
        }

    private:
        Node<T> *top;
        std::size_t size;
};

int main()
{
    Stack<int> test;

    std::cout << "Size: " << test.length() << std::endl; //0

    for(int i = 0; i < 5; ++i)
    {
        test.push(i);
        std::cout << "Added " << i << " to the stack." << std::endl;
    }

    std::cout << "Size: " << test.length() << std::endl; //5
    try
    {
        std::cout << "Removing " << test.pop() << " from the stack" << std::endl; //4
    }
    catch(char const *e)
    {
        std::cout << e << std::endl;
    }

    try
    {
        std::cout << "Top: " << test.peek() << std::endl; //3
    }
    catch(char const *e)
    {
        std::cout << e << std::endl;
    }

    int size = test.length();
    for(int i = 0; i <= size; ++i) //purposely try and delete one more than possible.
    {
        std::cout << "Size: " << test.length() << std::endl; //5
        try
        {
            std::cout << "Removing " << test.pop() << " from the stack" << std::endl; //4
        }
        catch(char const *e)
        {
            std::cout << e << std::endl;
        }
        try
        {
            std::cout << "Top: " << test.peek() << std::endl; //3
        }
        catch(char const *e)
        {
            std::cout << e << std::endl;
        }
    }

    return 0;
}

Size: 0
Added 0 to the stack.
Added 1 to the stack.
Added 2 to the stack.
Added 3 to the stack.
Added 4 to the stack.
Size: 5
Removing 4 from the stack
Top: 3
Size: 4
Removing 3 from the stack
Top: 2
Size: 3
Removing 2 from the stack
Top: 1
Size: 2
Removing 1 from the stack
Top: 0
Size: 1
Removing 0 from the stack
Error - The stack is empty.
Size: 0
Error - Can't pop an empty stack.
Error - The stack is empty.


Hopefully it will help you understand it easier.

If you have learned about smart pointers also I would suggest using a std::unique_ptr<T> to prevent any possible memory leaks.


*Slight improvement (forgot to check if the size was > 0 before popping :P) Also removed the setting value equal to 0 on the "out of bounds" value.
Last edited on
MRKSalman0349 (51)
Thanks bro i'm gratefull to you .......
Topic archived. No new replies allowed.