by Stack is a data structure used for storing collection of data where order in which data is arriving is important. In Stack, insertion and deletion both happened from the same end which is known as “Top”.
The data which is arrived last will be deleted first in Stack. This data ordering is called as Last in First out or LIFO. Before going ahead have a look into Stack basics.
Generic Stack implementation using simple array
Our aim here is to provide a generic implementation of Stacks which can be used for all primitive data types. Here we are going to talk about a Generic implementation of Stack data structures in C++ using arrays along with some basic Stack operations implementation such as Push/Pop etc.
Let’s have a look on basic C++ class definition for Generic Stack.
template <typename T>
class StackGeneric
{
private:
int size;
int top;
T* elements;
public:
StackGeneric (int sz);
~StackGeneric ();
bool push (T value);
int pop ();
bool isEmpty ();
int maxSize ();
int entries ();
};
Generic Stack Class Function Implementation
Let’s have a look into all the functions/operations definition of Generic Stack Class.
Constructor/Destructor implementation
template <typename T>
StackGeneric<T>::StackGeneric(int sz): size(sz), top (0)
{
elements = new T[size]();
if (!elements)
{
cout << "Stack initialization failed" << endl;
}
}
template <typename T>
StackGeneric<T>::~StackGeneric()
{
if (elements)
{
delete [] elements;
}
}
PUSH Operation Implementation
This operation will add an entry in Stack. In case Stack is full then error is returned. This condition is called Stack Overflow.
Let’s look into the sample code.
template <typename T>
bool StackGeneric<T>::push (T value)
{
if (!elements)
{
cout << "StackGeneric initialization failed" << endl;
return false;
}
if (top == size)
{
cout << "StackGeneric full, unable to PUSH !!!" << endl;
return false;
}
elements [top++] = value;
return true;
}
POP Operation Implementation
Removes the top item from the Stack. This ensures that LIFO is being maintained. In case Stack is empty then this condition is called Stack Underflow.
Let’s look into the sample code.
template <typename T>
int StackGeneric<T>::pop ()
{
if (!elements)
{
cout << "StackGeneric initialization failed" << endl;
return -1;
}
if (!top)
{
cout << "StackGeneric empty, unable to POP !!!" << endl;
return -1;
}
return elements[--top];
}
IsEmpty Operation Implementation
This function will check whether Stack is empty or not and return accordingly.
Let’s look into the sample code.
template <typename T>
bool StackGeneric<T>::isEmpty ()
{
return !top;
}
MaxSize Operation Implementation
This function will return the maximum size of Stack.
Let’s look into the sample code.
template <typename T>
int StackGeneric<T>::maxSize ()
{
return size;
}
Entries/Size Operation Implementation
This function will return the current number of entries present in the Stack.
Let’s look into the sample code.
template <typename T>
int StackGeneric<T>::entries ()
{
return top;
}
Let’s look into the sample main function which utilizes Stack class definition and functions defined above.
int main ()
{
StackGeneric<int> s(5);
cout << "Stack size: " << s.maxSize () << " entries present: " << s.entries () << endl;
cout << "Stack Pop: " << s.pop () << endl;
cout << "Stack Push 1 Status: " << s.push (1) << endl;
cout << "Stack Push 2 Status: " << s.push (2) << endl;
cout << "Stack size: " << s.maxSize () << " entries present: " << s.entries () << endl;
cout << "Stack Push 3 Status: " << s.push (3) << endl;
cout << "Stack Push 4 Status: " << s.push (4) << endl;
cout << "Stack Pop: " << s.pop () << endl;
cout << "Stack Push 5 Status: " << s.push (5) << endl;
cout << "Stack Push 6 Status: " << s.push (6) << endl;
cout << "Stack Push 7 Status: " << s.push (7) << endl;
cout << "Stack size: " << s.maxSize () << " entries present: " << s.entries () << endl;
cout << "Stack Push 8 Status: " << s.push (8) << endl;
cout << "Stack Push 9 Status: " << s.push (9) << endl;
cout << "Stack Pop: " << s.pop () << endl;
cout << "Stack Push 10 Status: " << s.push (10) << endl;
cout << "Stack Pop: " << s.pop () << endl;
cout << "Stack Pop: " << s.pop () << endl;
cout << "Stack Pop: " << s.pop () << endl;
cout << "Stack size: " << s.maxSize () << " entries present: " << s.entries () << endl;
cout << "Stack Pop: " << s.pop () << endl;
cout << "Stack Pop: " << s.pop () << endl;
}
Let’s analyze the output of this main function.
Stack size: 5 entries present: 0
Stack Pop: StackGeneric empty, unable to POP !!!
-1
Stack Push 1 Status: 1
Stack Push 2 Status: 1
Stack size: 5 entries present: 2
Stack Push 3 Status: 1
Stack Push 4 Status: 1
Stack Pop: 4
Stack Push 5 Status: 1
Stack Push 6 Status: 1
Stack Push 7 Status: StackGeneric full, unable to PUSH !!!
0
Stack size: 5 entries present: 5
Stack Push 8 Status: StackGeneric full, unable to PUSH !!!
0
Stack Push 9 Status: StackGeneric full, unable to PUSH !!!
0
Stack Pop: 6
Stack Push 10 Status: 1
Stack Pop: 10
Stack Pop: 5
Stack Pop: 3
Stack size: 5 entries present: 2
Stack Pop: 2
Stack Pop: 1
