I just coded this implementation of a stack using a singly linked list. Its written in C++ using the STL. I believe I am complete with it but there may be functions I am forgetting or ways to improve/ optimize my code. I tried using exceptions to learn how to use them so the code may not be best practice. Anyhow anyone who may want to use this use it, anyone looking to suggest ways to optimize my code type away :)

/*
 * Stack.h
 */

#ifndef STACK_H_
#define STACK_H_

template <typename T>
class Stack {

	public:
		// default constructor
		Stack(): front(NULL) , stackSize(0) {}

		// destructor
		virtual ~Stack();

		// add node to the top of the stack
		void push(const T& item);

		// delete a node from the top of the stack
		void pop();

		// references the item at the top of the stack
		T& top();

		// get the size of the stack
		int size() {return stackSize;}

		// returns true if the stack is empty, false otherwise
		bool empty() {return ((front == NULL) ? true: false);}

		// returns true if you can't allocate new memory, false otherwise
		bool full();

		// write out the stack
		void writeStack();

		// clear the stack
		void clear();

	private:
		struct node {
			T nodeValue;
			node *next;

			// default constructor
			node(): next(NULL) {}

			// constructor. Initialize nodeValue and next.
			node(const T& item, node *nextNode = NULL):
			nodeValue(item), next(nextNode) {}
		};

		node *front, *newNode;
		int stackSize;
};

template <typename T>
void Stack<T>::push(const T& item){

	try {

		newNode = new node(item,front);
		if (!full()){
			front = newNode;
			stackSize++;
		}
		else
			throw "Allocation error";
	}
	catch(char* e) {
		std::cout<<"Error: "<<e<<std::endl;
	}

}

template <typename T>
void Stack<T>::pop(){

	if (!empty()) {
		clear();

		stackSize--;
	}
	else
		std::cout<<"pop(): Stack is Empty"<<std::endl;

}

template <typename T>
T& Stack<T>::top(){
	if (!empty())
		return front->nodeValue;
	else
		std::cout<<"top(): Stack is empty"<<std::endl;
		std::exit(1);
}

template <typename T>
bool Stack<T>::full(){
	node *temp = new node;
	if (temp == NULL)
		return true;
	else
		return false;
}

template <typename T>
void Stack<T>::writeStack(){

	node* curr = front;
	while (curr != NULL){
		std::cout<<curr->nodeValue<<" ";
		curr = curr->next;
	}
}

template <typename T>
void Stack<T>::clear(){

	node* curr = front;
	front = front->next;
	delete curr;
}

template <typename T>
Stack<T>::~Stack(){
	try {
		if (!empty())
			clear();
		else
			throw "Destructor: Stack is empty";
	}
	catch (char* e){
		std::cout<<e<<std::endl;
	}

}

#endif /* STACK_H_ */

Here is an example of main()

/*
 * main.cpp
 */

#include <iostream>
#include "Stack.h"

using namespace std;

int main(){

	Stack<int> myStack;

	if (myStack.empty())
		cout<<"Stack is empty"<<endl;
	else
		cout<<"Stack is not empty"<<endl;

	for (int i = 0; i < 10; i++)
		myStack.push(i);

	cout<<"The top of the Stack is: "<<myStack.top()<<endl;

	if (myStack.empty())
		cout<<"Stack is empty"<<endl;
	else
		cout<<"Stack is not empty"<<endl;

	myStack.writeStack();
	cout<<endl<<"My Stack size is: "<<myStack.size()<<endl;
	cout<<endl;

	while (!myStack.empty())
		myStack.pop();

	if (myStack.empty())
		cout<<"Stack is empty"<<endl;
	else
		cout<<"Stack is not empty"<<endl;

	cout<<"The top of the Stack is: "<<myStack.top()<<endl;


	return 0;
}

heres the output

Stack is empty
The top of the Stack is: 9
Stack is not empty
9 8 7 6 5 4 3 2 1 0
My Stack size is: 10

Stack is empty
top(): Stack is empty

Looks okay at first glance, except for a few issues:
1. No const-correctness. Member functions that do not change the object (size, empty) should be const.
2. new does not return a null pointer when there is no more memory - it throws an exception of type std::bad_alloc.
3. What's the deal with the full function? You're leaking memory all over the place for every call to it.
4. Same in pop() - there are several "new"s in the program, but not a single "delete".
5. top() should throw an exception if the stack is empty instead of rudely exiting the program.
6. Missing braces in top() - the function will always cause the program to exit.

Code in the form if (foo)return true; else return false; can be shortened to return foo; So in the case of empty() this is sufficient:

bool empty() const {return !front;}

By the way, I don't see any use of the STL here.
The STL has a stack class already (std::stack).

Edited 6 Years Ago by Aranarth: n/a

I'd like to echo Aranarth's comments. In addition:

1) The clear() function appears to delete one element, despite the comment that suggests that it deletes all of them.

2) Therefore, the destructor deletes one element and leaves the rest of them sitting around.

3) You have no copy constructor or copy-assignment operator. If you try to copy a Stack, the effect is likely to be that you will have two objects that share a common data structure. Destroying one of them will cause mayhem with the other.

Wasup Aranarth, thanks for the reply, here are my replies..

Looks okay at first glance, except for a few issues:
1. No const-correctness. Member functions that do not change the object (size, empty) should be const.

Thanks for that, I forgot to do that. So question...size, empty I changed but should I also changed full? Another question what is the rules to follow for const member function (i.e. read only) functions? I would think that clear and writeList may qualify to be const but not sure, it looks like they shouldn't be

2. new does not return a null pointer when there is no more memory - it throws an exception of type std::bad_alloc.
I m still learning about exceptions so my exception code is my first try at it. I ll get better at it, thanks

3. What's the deal with the full function? You're leaking memory all over the place for every call to it.
I ll delete the new node, thanks

4. Same in pop() - there are several "new"s in the program, but not a single "delete".
I ll delete here too, thanks. Can you give me a rule of thumb for when to delete a pointer, i.e. did you miss the new keyword in writeStack() or in that case you don't delete it? I just read an article by the writer of C++ which said to use auto_ptr because sometimes its hard to know if your supossed to delete the ptr.

5. top() should throw an exception if the stack is empty instead of rudely exiting the program.
Thanks, still learning exceptions

6. Missing braces in top() - the function will always cause the program to exit.
got it, forgot that one, any conditional if statement's body with more than 1 line of code should include braces {}

Edited 6 Years Ago by figuer25: n/a

Arkoenig,

I'd like to echo Aranarth's comments. In addition:

1) The clear() function appears to delete one element, despite the comment that suggests that it deletes all of them.
good catch, I need a while loop

2) Therefore, the destructor deletes one element and leaves the rest of them sitting around.
got it

3) You have no copy constructor or copy-assignment operator. If you try to copy a Stack, the effect is likely to be that you will have two objects that share a common data structure. Destroying one of them will cause mayhem with the other.
I am not using a copy or assignment operator for this right now, this was a start. when I make more complicated code I ll start doing that. Then again I should try doing them for practice, but I do understand that if I wanted to copy on object to another I would need a copy consturctor and if I want to assign the value from one object to the other I would need an assignment operator function.

Edited 6 Years Ago by figuer25: n/a

3) You have no copy constructor or copy-assignment operator. If you try to copy a Stack, the effect is likely to be that you will have two objects that share a common data structure. Destroying one of them will cause mayhem with the other.
I am not using a copy or assignment operator for this right now, this was a start. when I make more complicated code I ll start doing that. Then again I should try doing them for practice, but I do understand that if I wanted to copy on object to another I would need a copy consturctor and if I want to assign the value from one object to the other I would need an assignment operator function.

If you don't want to define the copy or assignment operators, make them private (without defining them otherwise) so that no one tries to use them by mistake.

If you don't want to define the copy or assignment operators, make them private (without defining them otherwise) so that no one tries to use them by mistake.

make the functions private? not sure I understand what you mean, if you can give me a code example, thanks

Here are the changes...

#ifndef STACK_H_
#define STACK_H_

template <typename T>
class Stack {

	public:
		// default constructor
		Stack(): front(NULL) , stackSize(0) {}

		// destructor
		virtual ~Stack();

		// add node to the top of the stack
		void push(const T& item);

		// delete a node from the top of the stack
		void pop();

		// references the item at the top of the stack
		T& top();

		// get the size of the stack
		int size() const {return stackSize;}

		// returns true if the stack is empty, false otherwise
		bool empty() const {return !front;}

		// returns true if you can't allocate new memory, false otherwise
		bool full();

		// write out the stack
		void writeStack();

		// clear the stack
		void clear();

	private:
		struct node {
			T nodeValue;
			node* next;

			// default constructor
			node(): next(NULL) {}

			// constructor. Initialize nodeValue and next.
			node(const T& item, node* nextNode = NULL):
			nodeValue(item), next(nextNode) {}
		};

		node *front, *newNode;
		int stackSize;

                // copy constructor
                Stack(const Stack&);

                // copy assignment
                Stack& operator=(const Stack&);
};

template <typename T>
void Stack<T>::push(const T& item){

	try {

		newNode = new node(item,front);
		if (!full()){
			front = newNode;
			stackSize++;
		}
		else
			throw "Allocation error";
	}
	catch(char* e) {
		std::cout<<"Error: "<<e<<std::endl;
	}

}

template <typename T>
void Stack<T>::pop(){

	if (!empty()) {
		clear();

		stackSize--;
	}
	else
		std::cout<<"pop(): Stack is Empty"<<std::endl;

}

template <typename T>
T& Stack<T>::top(){
	if (!empty())
		return front->nodeValue;
	else
		std::cout<<"top(): Stack is empty"<<std::endl;
		std::exit(1);
}

template <typename T>
bool Stack<T>::full(){
	node* temp = new node;
	if (temp == NULL)
		return true;
	else
		return false;
}

template <typename T>
void Stack<T>::writeStack(){

	node* curr = front;
	while (curr != NULL){
		std::cout<<curr->nodeValue<<" ";
		curr = curr->next;
	}

	delete curr;
}

template <typename T>
void Stack<T>::clear(){

	node* curr;
	while (front != NULL){
		curr = front;
		front = front->next;
		delete curr;
	}

}

template <typename T>
Stack<T>::~Stack(){
	try {
		if (!empty())
			clear();
		else
			throw "Destructor: Stack is empty";
	}
	catch (char* e){
		std::cout<<e<<std::endl;
	}

}

#endif /* STACK_H_ */

heres what I changed...
1. made size() and empty() const functions AND shortened empty to return "!front" - Thanks Aranarth

int size() const {return stackSize;}

		bool empty() const {return !front;}

2. deleted curr in writeStack() after I display the stack

template <typename T>
void Stack<T>::writeStack(){

	node* curr = front;
	while (curr != NULL){
		std::cout<<curr->nodeValue<<" ";
		curr = curr->next;
	}

	delete curr;
}

3. Changed clear to use a loop to delete ALL nodes

template <typename T>
void Stack<T>::clear(){

	node* curr;
	while (front != NULL){
		curr = front;
		front = front->next;
		delete curr;
	}

}

4. Added private copy consturctor and assignment (copy) operator function

// copy constructor
                Stack(const Stack&);

                // copy assignment
                Stack& operator=(const Stack&);

questions...
1. In full, how can I delete the pointer with out affecting my return value?

full(){
   if (temp == NULL){
      delete temp;
      return true;
   }
   else{
      delete temp;
      return false;
   }

Will this work? I believe this works because the if check already does what it needs to do with temp so I can erase the pointer before my return statement.

Comments...
1. I will read more about exceptions in the next few days and change the exception code once I know more about them

2. About the 'using STL' question, arent templates part of the STL? that is why I said using STL, if not correct me and I ll change my terminology to something like 'Stack (template/ generic) implementation code' - thanks

Edited 6 Years Ago by figuer25: n/a

make the functions private? not sure I understand what you mean, if you can give me a code example, thanks

template<typename T> class Stack {

    // ...
private:
    Stack(const Stack&);               // copy constructor
    Stack& operator=(const Stack&);    // copy assignment

public:
    // ...
};

So you declare the copy constructor and assignment operators as private, thus ensuring a compile-time diagnostic message for anyone who tries to use them. Because no one can actually use them, you don't need to define them -- just declare them as shown here.

template<typename T> class Stack {

    // ...
private:
    Stack(const Stack&);               // copy constructor
    Stack& operator=(const Stack&);    // copy assignment

public:
    // ...
};

So you declare the copy constructor and assignment operators as private, thus ensuring a compile-time diagnostic message for anyone who tries to use them. Because no one can actually use them, you don't need to define them -- just declare them as shown here.

got it, added it, check the code above your post, thanks. when I have time in the next few days I ll work on those, thanks

This article has been dead for over six months. Start a new discussion instead.