I am trying to mimic std::stack in my implementation (just the basic interface - no iterators / allocators). Since I was having trouble handling all the memory allocation/deallocation, I read this.
Although my implementation seems to work flawlessly, I'm still not confident about these things:
- There is no memory-leak
- All the routines are fully performance and space-optimized
- My usage of Copy-and-Swap idiom is correct
- There isn't any better way of displaying the contents of a stack (see the overloaded
operator<<).
Could you please review it to see if it could be improved?
using namespace std;
template<typename T> struct mystack_node // The data structure for representing the "nodes" of the stack
{
T data;
mystack_node *next;
};
template<typename T> class mystack;
template<typename T>ostream& operator <<(ostream& out,const mystack<T> &a);
template<typename T> class mystack
{
unsigned int stack_size; // A variable keeping the record of number of nodes present in the stack
mystack_node<T> *stack_top; // A pointer pointing to the top of the stack
void mystack_swap(mystack &a,mystack &b) // Swap function used in the assignment operator ( Copy-and-Swap Idiom )
{
swap(a.stack_size,b.stack_size);
swap(a.stack_top,b.stack_top);
}
public:
mystack():stack_size(0),stack_top(NULL) {} // Default Constructor
mystack(const mystack& other):stack_size(0),stack_top(NULL) // Copy constructor
{
int i=0;
vector<T> vec(other.stack_size); // A vector for storing a backup of all the nodes in the "other" stack
mystack_node<T> *temp=other.stack_top;
while(temp!=NULL)
{
vec[i++]=temp->data;
temp=temp->next;
}
for(i=(int)vec.size()-1; i>=0; i--)
{
push(vec[i]);
}
}
~mystack() // Destructor
{
mystack_node<T> *temp=stack_top;
while(temp!=NULL)
{
temp=temp->next;
delete stack_top;
stack_top=temp;
}
}
mystack& operator = (mystack other) // Assignment operator
{
mystack_swap(*this,other);
return *this;
}
void push(const T &val) // Add a new node to the stack
{
mystack_node<T> *temp=new mystack_node<T>;
temp->data=val;
temp->next=stack_top;
stack_top=temp;
stack_size++;
}
void pop() // Remove the "top" node from the stack
{
if(stack_top!=NULL) // Don't do anything if the stack is already empty
{
mystack_node<T> *temp=stack_top->next;
delete stack_top;
stack_top=temp;
stack_size--;
}
}
unsigned int size() // Returns the number of nodes in the stack
{
return stack_size;
}
bool empty() // Returns whether if the stack is empty or not
{
return stack_size==0;
}
T top() // Returns the "top" node from the stack
{
return (*stack_top).data; // Deliberately left Out-of-Bound exception checking...
}
friend ostream& operator << <T> (ostream&,const mystack&);
};
template<typename T>ostream& operator <<(ostream& out,const mystack<T> &a) // Output operator to show the contents of the stack
{
mystack_node<T> *temp=a.stack_top;
while(temp!=NULL)
{
out<<temp->data<<" ";
temp=temp->next;
}
return out;
}
EDIT:
- Made
size(),empty()andtop()asconstfunctions. - Changed the type of
stack_sizefromunsigned inttosize_t. - Defined
struct mystack_nodein the private section ofclass mystackso that it is inaccessible to any other part of the code.
using namespace std;
template<typename T> class mystack;
template<typename T>ostream& operator <<(ostream& out,const mystack<T> &a);
template<typename T> class mystack
{
struct mystack_node // The data structure for representing the "nodes" of the stack
{
T data;
mystack_node *next;
};
size_t stack_size; // A variable keeping the record of number of nodes present in the stack
mystack_node *stack_top; // A pointer pointing to the top of the stack
void mystack_swap(mystack &a,mystack &b) // Swap function used in the assignment operator ( Copy-and-Swap Idiom )
{
swap(a.stack_size,b.stack_size);
swap(a.stack_top,b.stack_top);
}
public:
mystack():stack_size(0),stack_top(NULL) {} // Default Constructor
mystack(const mystack& other):stack_size(0),stack_top(NULL) // Copy constructor
{
int i=0;
vector<T> vec(other.stack_size); // A vector for storing a backup of all the nodes in the "other" stack
mystack_node *temp=other.stack_top;
while(temp!=NULL)
{
vec[i++]=temp->data;
temp=temp->next;
}
for(i=(int)vec.size()-1; i>=0; i--)
{
push(vec[i]);
}
}
~mystack() // Destructor
{
mystack_node *temp=stack_top;
while(temp!=NULL)
{
temp=temp->next;
delete stack_top;
stack_top=temp;
}
}
mystack& operator = (mystack other) // Assignment operator
{
mystack_swap(*this,other);
return *this;
}
void push(const T &val) // Add a new node to the stack
{
mystack_node *temp=new mystack_node;
temp->data=val;
temp->next=stack_top;
stack_top=temp;
stack_size++;
}
void pop() // Remove the "top" node from the stack
{
if(stack_top!=NULL) // Don't do anything if the stack is already empty
{
mystack_node *temp=stack_top->next;
delete stack_top;
stack_top=temp;
stack_size--;
}
}
size_t size() const // Returns the number of nodes in the stack
{
return stack_size;
}
bool empty() const // Returns whether if the stack is empty or not
{
return stack_size==0;
}
T top() const // Returns the "top" node from the stack
{
return (*stack_top).data; // Deliberately left Out-of-Bound exception checking...
}
friend ostream& operator << <T> (ostream&,const mystack&);
};
template<typename T>ostream& operator <<(ostream& out,const mystack<T> &a) // Output operator to show the contents of the stack
{
typename mystack<T>::mystack_node *temp=a.stack_top;
while(temp!=NULL)
{
out<<temp->data<<" ";
temp=temp->next;
}
return out;
}
