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.
Stack implementation using simple array
Here we are going to talk about a simple 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 Stack.
class Stack
{
private:
int size;
int top;
int* elements;
public:
Stack (int sz);
~Stack ();
bool push (int value);
int pop ();
bool isEmpty ();
int maxSize ();
int entries ();
};
Stack Class Function Implementation
Let’s have a look into all the functions/operations definition of Stack Class.
Constructor/Destructor implementation
Stack::Stack (int sz): size (sz),
top (0)
{
elements = new int[size]();
if (!elements)
{
cout << "Stack initialization failed" << endl;
}
}
Stack::~Stack ()
{
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.
bool Stack::push (int value)
{
if (!elements)
{
cout << "Stack initialization failed" << endl;
return false;
}
if (top == size)
{
cout << "Stack 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.
int Stack::pop ()
{
if (!elements)
{
cout << "Stack initialization failed" << endl;
return -1;
}
if (!top)
{
cout << "Stack 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.
bool Stack::isEmpty ()
{
return !top;
}
MaxSize Operation Implementation
This function will return the maximum size of Stack.
Let’s look into the sample code.
int Stack::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.
int Stack::entries ()
{
return top;
}
Let’s look into the sample main function which utilizes Stack class definition and functions defined above.
int main ()
{
Stack 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: Stack 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: Stack full, unable to PUSH !!!
0
Stack size: 5 entries present: 5
Stack Push 8 Status: Stack full, unable to PUSH !!!
0
Stack Push 9 Status: Stack 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
