C++

Forum

 
Stacks

Pages: 12
CodingIsHard17 (106)
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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
 
#ifndef DYNINTSTACK_H
#define DYNINTSTACK_H

template <class T>
class DynIntStack
{
	private:
		// Structure for stack nodes
		struct StackNode
		{
			T value;		//Value in the node
			StackNode *next;	//Pointer to the next node
		};
		
		StackNode *top;		//Pointer to the stack top
		
		
	public:
		//Constructor 
		DynIntStack()
		{
			top = NULL;
		}
		
		//Destructor
		~DynIntStack();
		
		//Stack Operations
		void push(T);
		void pop(T &);
		bool isEmpty();
};
#endif

#include <iostream>
#include "DynIntStack.h"
using namespace std;

// **************************
//Destructor 
//This function deletes every node in the list
// **************************

template <class T>
DynIntStack<T>::~DynIntStack()
{
	StackNode *nodePtr;
	StackNode *nextNode;
	
	//Position nodePtr at the top of the stack
	nodePtr = top;
	
	//Traverse the list deleting each node
	while(nodePtr != NULL)
	{
		nextNode = nodePtr->next;
		delete nodePtr;
		nodePtr = nextNode;
	}
}

// ***************************
// Member function push pushes the argument onto the stack
// ***************************

template <class T>
void DynIntStack<T>::push(T num)
{
	StackNode *newNode;	//Pointer to a new node
	
	// Allocate a new node and store num there
	newNode = new StackNode;
	newNode->value = num;
	
	// If there are no nodes in the list make newNode the 
	// first node
	if(isEmpty())
	{
		top =newNode;
		newNode->next = NULL;
	}
	
	else //otherwise insert NewNode before the top
	{
		newNode->next = top;
		top = newNode;
	}
}

// ******************************
// Member function pop, pops the value at the top of the stack 
// off, and copies it into the variable passed as an argument
// *******************************

template <class T>
void DynIntStack<T>::pop(T &num)
{
	StackNode *temp;  //Temporary pointer
	
	//First make sure the stack isn't empty
	if(isEmpty())
	{
		
		std::cout << "The stack is empty. \n";
		
	}
	
	else	//pop value off top of stack
	{
		num = top->value;
		temp = top->next;
		delete top;
		top = temp;
		
	}
}


// Member function is and Empty returns true 
// if the stack is empty, or false otherwise
template <class T>
bool DynIntStack<T>::isEmpty()
{
	bool status;
	
	if(!top)
		status = true;
	else
		status = false;
	
	return status;
}

void DynIntStack::topOfStack()
{
		//If there are no nodes in the list
	if(isEmpty())
	{
		std::cout<<"The Stack is empty\n";
	}
	else
	{
		std::cout<<"The value at the top of the stack is: "<< top->value <<"\n";
	}
	return;
}

void DynIntStack::bottomOfStack()
{
	StackNode *currentNode;	//Pointer for current value in the stack



	
	//If there are no nodes in the list
	if(isEmpty())
	{
		std::cout<<"The Stack is empty \n";
	}
	
	else //otherwise find the last node in the stack
	{
		currentNode = top;
		while(currentNode->next != NULL)
		{
		
			currentNode = currentNode->next;
		}
		
		std::cout<<"The value at the bottom of the stack is: "<<currentNode->value<<"\n";
		return;
	}

}

void DynIntStack::size()
{
	StackNode *currentNode;	//Pointer for current value in the stack
	StackNode *nextNode;	// Pointer for the next value in the stack
	int stackSize =0;
	
	
	currentNode = top;
	while(currentNode!= NULL)
	{
		currentNode = currentNode->next;
		stackSize++;
	
	}
	
	std::cout<<"The Stack size is: "<< stackSize<<"\n";


}

void DynIntStack::sumOfStack()
{
	StackNode *currentNode;	//Pointer for current value in the stack
	StackNode *nextNode;	// Pointer for the next value in the stack
	int stackSum =0;		//variable to store the sum of the stack
	
	//If there are no nodes in the list. To distinguish between an empty stack 
       // and a stack which may have a sum of zero
	if(isEmpty())
	{
		std::cout<<"The Stack is empty \n";
	}
	else
	{
	
		currentNode = top;
		while(currentNode!= NULL)
		{
			
			stackSum = stackSum + currentNode->value;
			currentNode = currentNode->next;
		
		}
		
		std::cout<<"The sum of the numbers in the Stack  is: "<< stackSum<<"\n";
	}
}


void DynIntStack::displayList() const
{
	StackNode *nodePtr;	//To move through the list
	
	//Position nodePtr at the head of the list
	nodePtr = top;
	
	//while nodePtr points to a node, traverse the list
	while (nodePtr)
	{
		//Display the value in this node
		std::cout<< nodePtr->value<< " ";
		
		//Move to the next node
		nodePtr = nodePtr -> next;
	}
	std::cout<<std::endl;
}


I am receiving an error:
main.cpp:36:25: fatal error: DynIntStack.h: No such file or directory
#include "DynIntStack.h"
^
compilation terminated.
Last edited on
deleted account xyzzy (5768)
Is all of that contained in the cpp file? Or do you have a header file and a source file?
CodingIsHard17 (106)
I actually haven't started writing a function. This is supposed to be my header file but I am trying to fix all of the kinks before. Or would you suggest writing it with the function, getting all of the errors and then trying to correct it?
deleted account xyzzy (5768)
IF that is what you want in your header file, named DynIntStack.h, remove line 36. You are trying to include the file itself.

As improper as using namespace std; is in source code, having that in a header file is even worse.

Just don't do it!

Any #includes you want/need should be up at the top of the file, after your header guard definition.
CodingIsHard17 (106)
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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
 
#ifndef DYNINTSTACK_H
#define DYNINTSTACK_H
#include <iostream>
using namespace std;

template <class T>
class DynIntStack
{
	private:
		//Structure for stack nodes
		struct StackNode
		{
			T value;		//Value in the node
			StackNode *next;	//Pointer to the next node
		};
		
		StackNode *top;		//Pointer to the stack top
		
		
	public:
		//Constructor 
		DynIntStack()
		{
			top = NULL;
		}
		
		//Destructor
		~DynIntStack();
		
		//Stack Operations
		void push(int);
		void pop(int &);
		bool isEmpty();
		void reversePrint();		//Implement this function
};


//Destuctor 
//This function deletes every node in the list
template <class T>
DynIntStack<T>::~DynIntStack()
{
	StackNode *nodePtr;
	StackNode *nextNode;
	
	//Position nodePtr at the top of the stack
	nodePtr = top;
	
	//Traverse the list deleting each node
	while(nodePtr != NULL)
	{
		nextNode = nodePtr->next;
		delete nodePtr;
		nodePtr = nextNode;
	}
}

//Member function push pushes the argument onto the stack
template <class T>
void DynIntStack<T>::push(T num)
{
	StackNode *newNode;	//Pointer to a new node
	
	//Allocate a new node and store num there
	newNode = new StackNode;
	newNode->value = num;
	
	//If there are no nodes in the list
	//make newNode the first node
	if(isEmpty())
	{
		top =newNode;
		newNode->next = NULL;
	}
	
	else //otherwise insert NewNode before the top
	{
		newNode->next = top;
		top = newNode;
	}
}


// Member function pop, pops the value at the top of the stack 
// off, and copies it into the variable passed as an argument
template <class T>
void DynIntStack<T>::pop(T &num)
{
	StackNode *temp;  //Temporary pointer
	
	//First make sure the stack isn't empty
	if(isEmpty())
	{
		
		std:cout << "The stack is empty. \n";
		
	}
	
	else	//pop value off top of stack
	{
		num = top->value;
		temp = top->next;
		delete top;
		top = temp;
		
	}
}


// Member function is empty and returns true if the stack is 
// empty, or false otherwise
template <class T>
bool DynIntStack<T>::isEmpty()
{
	bool status;
	
	if(!top)
	{
		status = true;
	}
	else
	{
	    status = false;
	}
	return status;
}
#endif

void DynIntStack::topOfStack()
{
		//If there are no nodes in the list
	if(isEmpty())
	{
		std::cout<<"The Stack is empty\n";
	}
	else
	{
		std::cout<<"The value at the top of the stack is: "<< top->value <<"\n";
	}
	return;
}

void DynIntStack::bottomOfStack()
{
	StackNode *currentNode;	//Pointer for current value in the stack



	
	//If there are no nodes in the list
	if(isEmpty())
	{
		std::cout<<"The Stack is empty \n";
	}
	
	else //otherwise find the last node in the stack
	{
		currentNode = top;
		while(currentNode->next != NULL)
		{
		
			currentNode = currentNode->next;
		}
		
		std::cout<<"The value at the bottom of the stack is: "<<currentNode->value<<"\n";
		return;
	}

}

void DynIntStack::size()
{
	StackNode *currentNode;	//Pointer for current value in the stack
	StackNode *nextNode;	// Pointer for the next value in the stack
	int stackSize =0;
	
	
	currentNode = top;
	while(currentNode!= NULL)
	{
		currentNode = currentNode->next;
		stackSize++;
	
	}
	
	std::cout<<"The Stack size is: "<< stackSize<<"\n";


}

void DynIntStack::sumOfStack()
{
	StackNode *currentNode;	//Pointer for current value in the stack
	StackNode *nextNode;	// Pointer for the next value in the stack
	int stackSum =0;		//variable to store the sum of the stack
	
	// If there are no nodes in the list, distinguish between
	// an empty stack and a stack which may have a sum of zero
	if(isEmpty())
	{
		std::cout<<"The Stack is empty \n";
	}
	else
	{
	
		currentNode = top;
		while(currentNode!= NULL)
		{
			
			stackSum = stackSum + currentNode->value;
			currentNode = currentNode->next;
		
		}
		
		std::cout<<"The sum of the numbers in the Stack  is: "<< stackSum<<"\n";
	}
}


void DynIntStack::displayList() const
{
	StackNode *nodePtr;	//To move through the list
	
	//Position nodePtr at the head of the list
	nodePtr = top;
	
	//while nodePtr points to a node, traverse the list
	while (nodePtr)
	{
		//Display the value in this node
		std::cout<< nodePtr->value<< " ";
		
		//Move to the next node
		nodePtr = nodePtr -> next;
	}
	std::cout<<std::endl;
}

#include <iostream>
#include <string>
using namespace std;

int main()
{

   //stack for integers
   DynIntStack<int> stack;
   stack.push(2);
   stack.push(3);
   stack.push(4);

   int top=0;
  
   cout<<"--->integer stack<---"<<endl;
   cout<<"Integer stack"<<endl;
   cout<<"---------------"<<endl;
   stack.print();
   cout<<"Popping integers"<<endl;
   cout<<"---------------"<<endl;
   stack.pop(top);
   cout<<top<<endl;
   stack.pop(top);
   cout<<top<<endl;
   stack.pop(top);
   cout<<top<<endl;

   //stack for characters
   DynIntStack<char> charstack;
   charstack.push('a');
   charstack.push('b');
   charstack.push('c');

   char ch;
  
   cout<<"--->Character stack<---"<<endl;
   cout<<"Character stack"<<endl;
   cout<<"---------------"<<endl;
   charstack.print();
   cout<<"Popping characters elements"<<endl;
   cout<<"---------------"<<endl;
   charstack.pop(ch);
   cout<<ch<<endl;
   charstack.pop(ch);
   cout<<ch<<endl;
   charstack.pop(ch);
   cout<<ch<<endl;

   //stack for string
   DynIntStack<string> stringStack;
   stringStack.push("windows");
   stringStack.push("apple");
   stringStack.push("unix");

   string os;
  
   cout<<"--->String stack<---"<<endl;
   cout<<"String stack"<<endl;
   cout<<"---------------"<<endl;
   stringStack.print();
   cout<<"Popping strings elements"<<endl;
   cout<<"---------------"<<endl;
   stringStack.pop(os);
   cout<<os<<endl;
   stringStack.pop(os);
   cout<<os<<endl;
   stringStack.pop(os);
   cout<<os<<endl;

  

   system("pause");
   return 0;
}


I've removed the line you told me to. I am now getting this output:


main.cpp:60:6: error: prototype for ‘void DynIntStack::push(T)’ does not match any in class ‘DynIntStack’
 void DynIntStack<T>::push(T num)
      ^~~~~~~~~~~~~~
main.cpp:31:8: error: candidate is: void DynIntStack::push(int)
   void push(int);
        ^~~~
        ^~~
main.cpp:129:6: error: ‘template class DynIntStack’ used without template parameters
 void DynIntStack::topOfStack()
      ^~~~~~~~~~~
main.cpp: In function ‘void topOfStack()’:
main.cpp:132:13: error: ‘isEmpty’ was not declared in this scope
  if(isEmpty())
             ^
main.cpp:32:8: note:   no known conversion for argument 1 from ‘std::string {aka std::basic_string}’ to ‘int&’


Please note: the output contained many more errors. However, it exceeded the max length.
deleted account xyzzy (5768)
Do not jam all your source from headers and separate source files into one set of code tags! It makes it IMPOSSIBLE to decipher your code.

Each file, header and source, should be between their own code tags.

DynIntStack.hpp:
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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
 
#ifndef __DYNINTSTACK_HPP__
#define __DYNINTSTACK_HPP__

#include <iostream>

template <class T>
class DynIntStack
{
private:
   //Structure for stack nodes
   struct StackNode
   {
      T value;		//Value in the node
      StackNode* next;	//Pointer to the next node
   };

   StackNode* top;		//Pointer to the stack top

public:
   //Constructor
   DynIntStack()
   {
      top = NULL;
   }

   //Destructor
   ~DynIntStack();

   //Stack Operations
   void push(T);
   void pop(T&);
   bool isEmpty();
   // void reversePrint();		//Implement this function
   void topOfStack();
   void bottomOfStack();
   void size();
   void sumOfStack();
   void displayList() const;
};

//Destuctor
//This function deletes every node in the list
template <class T>
DynIntStack<T>::~DynIntStack()
{
   StackNode* nodePtr;
   StackNode* nextNode;

   //Position nodePtr at the top of the stack
   nodePtr = top;

   //Traverse the list deleting each node
   while (nodePtr != NULL)
   {
      nextNode = nodePtr->next;
      delete nodePtr;
      nodePtr = nextNode;
   }
}

//Member function push pushes the argument onto the stack
template <class T>
void DynIntStack<T>::push(T num)
{
   StackNode* newNode;	//Pointer to a new node

   //Allocate a new node and store num there
   newNode = new StackNode;
   newNode->value = num;

   //If there are no nodes in the list
   //make newNode the first node
   if (isEmpty())
   {
      top = newNode;
      newNode->next = NULL;
   }
   else //otherwise insert NewNode before the top
   {
      newNode->next = top;
      top = newNode;
   }
}

// Member function pop, pops the value at the top of the stack
// off, and copies it into the variable passed as an argument
template <class T>
void DynIntStack<T>::pop(T& num)
{
   StackNode* temp;  //Temporary pointer

   //First make sure the stack isn't empty
   if (isEmpty())
   {
      std::cout << "The stack is empty. \n";
   }
   else	//pop value off top of stack
   {
      num = top->value;
      temp = top->next;
      delete top;
      top = temp;
   }
}

// Member function is empty and returns true if the stack is
// empty, or false otherwise
template <class T>
bool DynIntStack<T>::isEmpty()
{
   bool status;

   if (!top)
   {
      status = true;
   }
   else
   {
      status = false;
   }
   return status;
}

template <class T>
void DynIntStack<T>::topOfStack()
{
   //If there are no nodes in the list
   if (isEmpty())
   {
      std::cout << "The Stack is empty\n";
   }
   else
   {
      std::cout << "The value at the top of the stack is: " << top->value << "\n";
   }
   return;
}

template <class T>
void DynIntStack<T>::bottomOfStack()
{
   StackNode* currentNode;	//Pointer for current value in the stack

   //If there are no nodes in the list
   if (isEmpty())
   {
      std::cout << "The Stack is empty \n";
   }
   else //otherwise find the last node in the stack
   {
      currentNode = top;
      while (currentNode->next != NULL)
      {

         currentNode = currentNode->next;
      }

      std::cout << "The value at the bottom of the stack is: " << currentNode->value << "\n";
      return;
   }
}

template <class T>
void DynIntStack<T>::size()
{
   StackNode* currentNode;	//Pointer for current value in the stack
   StackNode* nextNode;	// Pointer for the next value in the stack
   int stackSize = 0;

   currentNode = top;
   while (currentNode != NULL)
   {
      currentNode = currentNode->next;
      stackSize++;
   }

   std::cout << "The Stack size is: " << stackSize << "\n";
}

template <class T>
void DynIntStack<T>::sumOfStack()
{
   StackNode* currentNode;	//Pointer for current value in the stack
   StackNode* nextNode;	// Pointer for the next value in the stack
   int stackSum = 0;		//variable to store the sum of the stack

   // If there are no nodes in the list, distinguish between
   // an empty stack and a stack which may have a sum of zero
   if (isEmpty())
   {
      std::cout << "The Stack is empty \n";
   }
   else
   {
      currentNode = top;
      while (currentNode != NULL)
      {
         stackSum = stackSum + currentNode->value;
         currentNode = currentNode->next;
      }

      std::cout << "The sum of the numbers in the Stack  is: " << stackSum << "\n";
   }
}


template <class T>
void DynIntStack<T>::displayList() const
{
   StackNode* nodePtr;	//To move through the list

   //Position nodePtr at the head of the list
   nodePtr = top;

   //while nodePtr points to a node, traverse the list
   while (nodePtr)
   {
      //Display the value in this node
      std::cout << nodePtr->value << " ";

      //Move to the next node
      nodePtr = nodePtr->next;
   }
   std::cout << std::endl;
}

#endif


Driver.cpp:
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
 
#include <iostream>
#include <string>
#include "DynIntStack.hpp"

int main()
{
   //stack for integers
   DynIntStack<int> stack;
   stack.push(2);
   stack.push(3);
   stack.push(4);

   int top { };

   std::cout << "--->integer stack<---\n";
   std::cout << "Integer stack\n";
   std::cout << "---------------\n";

   // stack.print(); // not implemented, can't call

   std::cout << "Popping integers\n";
   std::cout << "---------------\n";
   stack.pop(top);
   std::cout << top << '\n';
   stack.pop(top);
   std::cout << top << '\n';
   stack.pop(top);
   std::cout << top << '\n';

   //stack for characters
   DynIntStack<char> charstack;
   charstack.push('a');
   charstack.push('b');
   charstack.push('c');

   char ch { };

   std::cout << "--->Character stack<---\n";
   std::cout << "Character stack\n";
   std::cout << "---------------\n";

   // charstack.print();

   std::cout << "Popping characters elements\n";
   std::cout << "---------------\n";
   charstack.pop(ch);
   std::cout << ch << '\n';
   charstack.pop(ch);
   std::cout << ch << '\n';
   charstack.pop(ch);
   std::cout << ch << '\n';

   //stack for string
   DynIntStack<std::string> stringStack;
   stringStack.push("windows");
   stringStack.push("apple");
   stringStack.push("unix");

   std::string os { };

   std::cout << "--->String stack<---\n";
   std::cout << "String stack\n";
   std::cout << "---------------\n";

   // stringStack.print();

   std::cout << "Popping strings elements\n";
   std::cout << "---------------\n";
   stringStack.pop(os);
   std::cout << os << '\n';
   stringStack.pop(os);
   std::cout << os << '\n';
   stringStack.pop(os);
   std::cout << os << '\n';
}
CodingIsHard17 (106)
Okay I see what you mean and I apologize for not separating my header and source files .. what can I do to resolve this error? 

main.cpp:235:27: fatal error: DynIntStack.hpp: No such file or directory
 #include "DynIntStack.hpp"
                           ^
compilation terminated.
CodingIsHard17 (106)
Hey,

I removed the line
#include "DynIntStack.hpp"

And instead I added
#include <stack>

So now my output is:
--->integer stack<---
Integer stack
---------------
Popping integers
---------------
4
3
2
--->Character stack<---
Character stack
---------------
Popping characters elements
---------------
c
b
a
--->String stack<---
String stack
---------------
Popping strings elements
---------------
unix
apple
windows



How can I now ensure that the stacks are sorted from low to high / alphabetical order?
Ganado (6811)
I'm just jumping in here without having read the whole thread...
How can I now ensure that the stacks are sorted from low to high / alphabetical order?
You don't. stacks are not meant for sorting, they're meant for pushing and popping; if you push something, it should be the same thing that would get popped if you calling stack.push("foo"); stack.pop().

If you want to sort your data, it's no longer a stack. I suggest using a std::vector or multiset.
Last edited on
deleted account xyzzy (5768)
Do you have jammed all your code together into a single source file? Your template class implementation and main()?

If you do why have unneeded header guards?

If that is all in one source file no need to #include <stack> since you are trying to implement a custom stack.

If you have your source separated into header and source files what are the files named?

If you do have header and source files, are the two files in the same folder location?

And FYI, stack contents should not sorted. A stack is LIFO. Last In, First Out. You want to sort the contents you need to create a different custom container, or use one of the C++ standard library containers that can be sorted. Such as a std::vector or std::list.
mbozzi (3932)
How can I now ensure that the stacks are sorted from low to high / alphabetical order?

Consider a priority queue instead.
Last edited on
CodingIsHard17 (106)
So the code is here:

https://onlinegdb.com/BJjhqr7nB

I wrote it all together here on this compiler and it is running with that output I sent.

Just can't get it to run in Dev C++. Especially when separated into two separate files using the "DynIntStack.hpp" header.

When separated the names of the files are
DynIntStack
and
DynIntStack_Source
. And yes they are located in the same folder.
CodingIsHard17 (106)
To implement a sortStack function how would I go about doing that?

I have only the beginning line:
void DynIntStack::sortStack()

I also want to implement a reversePrint() function.
Ganado (6811)
One way to sort a stack would be to pop all of its elements into a sortable container, like std::vector, then sort that, and then push the elements back onto the stack.

e.g. using std::stack
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
 
// Example program
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>

void sortStack(std::stack<int>& stack)
{
    std::vector<int> vec(stack.size());
    for (size_t i = 0; i < vec.size(); i++)
    {
        vec[i] = stack.top();
        stack.pop();
    }
    
    std::sort(vec.begin(), vec.end());
    
    for (size_t i = 0; i < vec.size(); i++)
    {
        size_t rev_index = vec.size() - i - 1;
        stack.push(vec[rev_index]);
    }
}

int main()
{
    std::stack<int> my_stack;
    my_stack.push(42);
    my_stack.push(37);
    my_stack.push(52);
    my_stack.push(13);
    
    sortStack(my_stack);
    
    // print sorted by popping:
    while (my_stack.size() > 0)
    {
        int num = my_stack.top();
        std::cout << num << '\n';
        my_stack.pop();
    }
}


What does it mean to print a stack reversed?
If I pushed 5, then 3, then 6 onto the stack, the "reverse" of that is to just print then pop the top -- you'd print 6, then 3, then 5. A fairly simple while loop.
Last edited on
jonnin (11437)
vectors are effectively stacks, via the push back and pop back tools.
vectors can be sorted and rearranged to your heart's content.
deleted account xyzzy (5768)
jonnin wrote:
vectors are effectively stacks,


You already know this, jonnin, but the OP probably doesn't. :)

std::stack in the C++ standard library acts as a wrapper to an underlying container. std::vector, std::deque and std::list fit the requirements for a stack adaptation.

http://www.cplusplus.com/reference/stack/stack/
Last edited on
CodingIsHard17 (106)
How can I correct this to work efficiently and correctly? I'm new with stacks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
void DynIntStack::sortStack(stack<int> &stack)
{
    if(isEmpty()) // base case: stack is empty
    {
    return;
    }
    // remove the top element
    int top = stack.top();
    stack.pop();
    
    // continue for the remaining stack elements
    sortStack(stack);
    
    // insert the popped elements back into the sorted stack
    stack.push(top);
}
Ganado (6811)
Well the issue is you're not sorting anything there. I see no comparisons.

Forget what I said about using a vector; I doubt this is how your professor wants it.

In your first code, your stack is essential implemented as a linked list. I would look up "C++ sort linked list" and try to follow the logic there. Probably the easiest thing to implement would be an insertion sort -- take an element, remove it from the list, and then carry it back to the head of the list.
Then, traverse the list and insert it when it's greater than or equal to the current node's value.
Last edited on
CodingIsHard17 (106)
DynIntStack.h
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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
 
#ifndef DYNINTSTACK_H
#define DYNINTSTACK_H

#include<iostream>

class DynIntStack
{
	private:
		//Structure for stack node
		struct StackNode
		{
			int value;		//Value in the node
			StackNode *next;	//Pointer to the next node
		};
		
		StackNode *top;		//Pointer to the stack top
		
		
	public:
		//Constructor 
		DynIntStack()
		{
			top = NULL;
		}
		
		//Destructor
		~DynIntStack();
		
		//Stack Operations
		void push(int);
		void pop(int &);
		bool isEmpty();
		void topOfStack();
		void bottomOfStack();
		void size();
		void sumOfStack();
		void displayList() const;
		void sortStack();			//Implement this function
		void reversePrint();		//Implement this function
		void OddOrEvenPrint();		//Implement this function
//		void divisbleBy235Print();	//Optional only remove comment if you plan on implementing this function
		
		
		
};
#endif


// Destructor 
// This function deletes every node in the list
DynIntStack::~DynIntStack()
{
	StackNode *nodePtr;
	StackNode *nextNode;
	
	//Position nodePtr at the top of the stack
	nodePtr = top;
	
	//Traverse the list deleting each node
	while(nodePtr != NULL)
	{
		nextNode = nodePtr->next;
		delete nodePtr;
		nodePtr = nextNode;
	}
}



// Member function push pushes the argument onto the stack
void DynIntStack::push(int num)
{
	StackNode *newNode;	//Pointer to a new node
	
	//Allocate a new node and store num there
	newNode = new StackNode;
	newNode->value = num;
	
	//If there are no nodes in the list make newNode the first node
	if(isEmpty())
	{
		top =newNode;
		newNode->next = NULL;
	}
	
	else //otherwise insert NewNode before the top
	{
		newNode->next = top;
		top = newNode;
	}
}


//Member function pop, pops the value at the top of the stack off, and copies it into the variable passed as an argument

void DynIntStack::pop(int &num)
{
	StackNode *temp;		//Temporary pointer
	
	//First make sure the stack isn't empty
	if(isEmpty())
	{
		
		std::cout << "The stack is empty. \n";
		
	}
	
	else	//pop value off top of stack
	{
		num = top->value;
		temp = top->next;
		delete top;
		top = temp;
		
	}
}


//Member function isEmpty returns true if the stack is empty, or false otherwise
bool DynIntStack::isEmpty()
{
	bool status;
	
	if(!top)
		status = true;
	else
		status = false;
	
	return status;
}

void DynIntStack::topOfStack()
{
		//If there are no nodes in the list
	if(isEmpty())
	{
		std::cout<<"The Stack is empty\n";
	}
	else
	{
		std::cout<<"The value at the top of the stack is: "<< top->value <<"\n";
	}
	return;
}

void DynIntStack::bottomOfStack()
{
	StackNode *currentNode;	//Pointer for current value in the stack

	//If there are no nodes in the list
	if(isEmpty())
	{
		std::cout<<"The Stack is empty \n";
	}
	
	else //otherwise find the last node in the stack
	{
		currentNode = top;
		while(currentNode->next != NULL)
		{
		
			currentNode = currentNode->next;
		}
		
		std::cout<<"The value at the bottom of the stack is: "<<currentNode->value<<"\n";
		return;
	}

}

void DynIntStack::size()
{
	StackNode *currentNode;	//Pointer for current value in the stack
	StackNode *nextNode;	// Pointer for the next value in the stack
	int stackSize =0;
	
	
	currentNode = top;
	while(currentNode!= NULL)
	{
		currentNode = currentNode->next;
		stackSize++;
	
	}
	
	std::cout<<"The Stack size is: "<< stackSize<<"\n";


}

void DynIntStack::sumOfStack()
{
	StackNode *currentNode;	//Pointer for current value in the stack
	StackNode *nextNode;	// Pointer for the next value in the stack
	int stackSum =0;		//variable to store the sum of the stack
	
	//If there are no nodes in the list. To distinguish between an empty stack and a stack which may have a sum of zero
	if(isEmpty())
	{
		std::cout<<"The Stack is empty \n";
	}
	else
	{
	
		currentNode = top;
		while(currentNode!= NULL)
		{
			
			stackSum = stackSum + currentNode->value;
			currentNode = currentNode->next;
		
		}
		
		std::cout<<"The sum of the numbers in the Stack is: "<< stackSum<<"\n";
	}
}


void DynIntStack::displayList() const
{
	StackNode *nodePtr;	//To move through the list
	
	//Position nodePtr at the head of the list
	nodePtr = top;
	
	//while nodePtr points to a node, traverse the list
	while (nodePtr)
	{
		//Display the value in this node
		std::cout<< nodePtr->value<< " ";
		
		//Move to the next node
		nodePtr = nodePtr -> next;
	}
	std::cout<<std::endl;
}

// Sort stack implementation
void DynIntStack::sortedInsert(stack<int> &stack, int top)
{
    if(isEmpty() || top > stack.top()) // base case: stack is empty
    {
    stack.push(top);
    return;
    }
    // remove the top element
    int temp = stack.top();
    stack.pop();
    sortedInsert(stack, top);
    stack.push(temp);
}

void DynIntStack::sortStack()
{
    if(!isEmpty())
    {
        int top = stack.top();
        stack.pop();
        sortStack(stack);
        sortedInsert(stack, top);
    }
}

// implemented reverse print function
void DynIntStack::reversePrint()
{
    int num;
    stack<int> temp;
    
    while (stack.empty() = false)
    {
        num = stack.top();
        stack.pop();
        temp.push(item);
    }
    
    stack = temp;
    return;
}

void DynIntStack::OddOrEvenPrint()
{

	StackNode *currentNode;	//Pointer for current value in the stack
	StackNode *nextNode;	// Pointer for the next value in the stack
	int stackOdd =0;		//variable to store the sum of the stack
	int stackEven = 0;
	
	if(isEmpty())
	{
		std::cout<<"The Stack is empty \n";
	}
	
	else
	{
	
		currentNode = top;
		while(currentNode!= NULL)
		{
			if(currentNode->value%2 == true)
			{
				stackEven++;
			}
			else
			{
				stackOdd++;
			}
			currentNode = currentNode->next;
		
		}
		

	}
	std::cout<<"The number of even numbers in the Stack is: "<< stackEven <<"\n";	
	std::cout<<"The number of odd numbers in the Stack is: "<< stackOdd <<"\n";
}


driver.cpp
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
 
#include <iostream>
#include <string>
#include "DynIntStack.h"

using namespace std;

int main()
{
	
	int catchVar;	//To hold values popped off the stack
	
	//Create a DynIntStack object
	DynIntStack stack;

//Test 1
	stack.push(14);
	stack.push(3);
	stack.push(15);
	stack.displayList();
	stack.sortStack();
	stack.displayList();


	cout<<"Popping...\n";
	stack.pop(catchVar);
	stack.pop(catchVar);
	stack.pop(catchVar);

//Test 2
	stack.push(15);
	stack.push(14);
	stack.push(3);
	stack.displayList();
	stack.sortStack();
	stack.displayList();


	cout<<"Popping...\n";
	stack.pop(catchVar);
	stack.pop(catchVar);
	stack.pop(catchVar);	
	
//Test 3
	stack.push(3);
	stack.push(14);
	stack.push(15);
	stack.displayList();
	stack.sortStack();
	stack.displayList();
	
	
	cout<<"Popping...\n";
	stack.pop(catchVar);
	stack.pop(catchVar);
	stack.pop(catchVar);

//Test 4
	stack.push(3);
	stack.displayList();
	stack.sortStack();
	stack.displayList();


	cout<<"Popping...\n";
	stack.pop(catchVar);	

//Test 5
	stack.displayList();
	stack.sortStack();
	stack.displayList();

	return 0;
}


The output is getting:
main.cpp:239:32: error: variable or field ‘sortedInsert’ declared void
 void DynIntStack::sortedInsert(stack<int> &stack, int top)
                                ^~~~~
main.cpp:239:32: error: ‘stack’ was not declared in this scope
main.cpp:239:38: error: expected primary-expression before ‘int’
 void DynIntStack::sortedInsert(stack<int> &stack, int top)
                                      ^~~
main.cpp:239:51: error: expected primary-expression before ‘int’
 void DynIntStack::sortedInsert(stack<int> &stack, int top)


What is the problem with it now?
doug4 (1538)
You never declared the sortedInsert(...) function in the class declaration.

You never included any header file that defines the type 'stack'.
Last edited on
Pages: 12