Stack ADT – Implementation in C++
1. Introducing C++
The stack is a kind of linear data structure used in many applications. The computer
applications are designed with the help of programming languages. So we need to know
how to implement the stack ADT in programming languages so that the different
applications may use the stack for solving problems. The stack has to be designed as an
ADT, i.e., the implementation details have to be abstracted from the user of the stack.
To create any kind of ADT, we need a programming language which support Object
Oriented Programming. C++ is Object Oriented Programming language which supports
object oriented way of solving problems. In this session, we are going to discuss the
implementation of stack in C++ language.
2. Identifying Properties and Functionalities
Any ADT (Abstract Data Type) can be constructed with the help of “Class” concept in
C++. The class is nothing but a template for creating a group of similar objects. A class
may have constructors, properties and functions. To create a stack ADT, we need to
create a class in the name of “Stack”. Inside the class, we need to specify the properties,
usually the storage and special properties of the ADT to be designed and the
functionalities to be done with the ADT. There are two important sections in C++ class,
private and public. The properties or functions which are given in private section of the
class cannot be accessed outside of the class scope through its object. But the functions
or properties which are declared in public section can be accessed outside of the class
through its object. Since the stack is an ADT, we need to decide, what are things to be
restricted from the access and what are things to be allowed for the user access. Usually,
for any ADT, the storage and the implementation details of the functionalities are hidden
from the user. But the user should know what are the operations he can do with the ADT.
So the properties of the stack will be added in private section of the class and the
functions declarations, i.e., the operations to be done with the stack will be added in
public section of the stack. The following are the properties with its type of the stack to
be added in private section.
stData - An array with fixed size to store the stack elements of type integer.
Assume that we are going to create a stack for storing integer elements.
Size – Integer type variable used to maintain the size of the stack. The size
of the stack needs to be fixed during the creation of stack.
Top – Integer type variable used to maintain the index of the recently
inserted element.
The memory for the array stData can be created during the construction of stack.
Let us assume the “Size” of the stack is the input and it will be received from the user
during the creation of stack. The properties “Size” and “Top” will be initialized during
creation of stack. The initial value of the “Top” is -1.
The stack is having the following functionalities. The following is the possible
operations on stack.
isStackEmpty – to check stack emptiness.
isStackFull – to check the stack overflow.
Push – to add a new element into the stack.
Pop – to delete an element from the stack.
Peek – to obtain the value of next element to be deleted.
makeStackEmpty – to clear the content of the stack.
The class is defined as follows which include the properties declarations and the
member functions declaration. The class contains only the prototype of the functions and
the definition of the functions are defined outside of the class. The array stData is also
declared as only pointer, so that the memory for the array elements will be created in the
constructor.
3. C++ Code for Stack ADT
int main()
{
int data;
Stack myStack(4);
int ch;
bool result;
do
{
cout<<"\n1. Push\n2. Pop\n3. Peek\n0. Exit";
cout<<"\nEnter Choice: ";
cin>>ch;
switch(ch)
{
case 1:
cout<<"\nEnter the element to be inserted: ";
cin>>data;
result = [Link](data);
if(result)
cout<<"\nSuccess...\n";
else
cout<<"\nFailed. Stack Overflow...\n";
break;
case 2:
result = [Link](data);
if(result)
cout<<"\nSuccess. Popped Element: "<<data<<"\n";
else
cout<<"\nFailed. Stack Empty\n";
break;
case 3:
result = [Link](data);
if(result)
cout<<"\nSuccess. Next Element: "<<data<<"\n";
else
cout<<"\nFailed. Stack Empty\n";
break;
default:
cout<<"\nInvalid Option...\n";
break;
}
}while(ch!=0);
}