What is a stack?
A stack is a data structure that stores a collection of elements and has at least two operations associated with it:
- push 2. pop
Push and pop operation on a stack is done according to LIFO that is Last in, First Out order.
Push means to insert a new item at the end.
Pop means to remove an item from the end.
Implementation
We will implement our stack with a dynamically allocated array, you can also implement a stack with a linked list or dynamic arrays.
Stack class
The stack is a template class that has two data members:
- stack: this is a dynamically allocated array.
- top: this is the index of topmost element in our array.
Additionally, our class will have two template parameters:
- type: type of the elements to be stored in the array.
- size: maximum size of the stack
The stack will have the following member functions:
- is_empty: Return true if the stack is empty, false otherwise.
- push: insert 'element' at the top of the stack, if not overflow
- pop: remove the element at the top of the stack if not underflow
- display: print all elements in the stack to the console
- get_top_element: returns the top element
- clear: remove all elements in the stack and reset the top.
template <typename type, int size>
class Stack
{
private:
type* stack;
int top;
public:
Stack();
~Stack();
bool is_empty();
void push(type element);
type pop();
void display();
type get_top_element();
void clear();
};
Stack Member Functions Implementation
Now let's define each function one by one.
- Stack(): This is our constructor.
- It creates a stack with an array of size 'size'.
- It sets top to -1 to indicate that the stack is empty right now.
template <typename type, int size>
Stack<type, size> :: Stack()
{
stack = new type[size];
top = -1;
}
- ~Stack(): This is our destructor.
-
It will free the memory occupied by the dynamically allocated array of Stack.
Why? It's important to do this in destructor because when an object goes out of scope, the dynamically allocated array won't be released automatically.
Just remember that whatever you allocate dynamically in constructor must be freed in the destructor.
template <typename type, int size>
Stack<type, size> :: ~Stack()
{
delete[] stack;
}
- is_empty(): Return true if stack is empty, false otherwise.
-
How to check if the stack is empty?
If you think of this:
if (top == -1) return true else return falsethen it is correct but just unnecessary, because you can do it like this:
template<typename type, int size> bool Stack<type, size> :: is_empty() { return top == -1; }because the Boolean operator == will itself return either true or false.
- push(): insert 'element' at the top of the stack, if not overflow.
-
First, we need to check for overflow that is if we have more space in the stack or not for our new element, then if we do we save it otherwise we have two options -
- We can handle overflow with an
ifstatement. - We can handle overflow with exception handling. We will use this method because It's easier to ask forgiveness than it is to get permission.
- Note: out_of_range(msg) is a standard exception defined in <stdexcept> header file.
- We can handle overflow with an
template<typename type, int size>
void Stack<type, size> :: push(type element)
{
if (top == size - 1)
{
throw out_of_range("Stack Overflow!! No more space to add elements.");
}
// insert element on next position in array
stack[++top] = element;
}
- pop(): Remove element at the top of stack if not underflow.
- Just like we did with push() we will handle underflow that is no more elements to remove with exception handling.
- Note: out_of_range(msg) is a standard exception defined in <stdexcept> header file.
template<typename type, int size>
type Stack<type, size> :: pop()
{
// check for underflow
if (is_empty())
{
throw out_of_range("Stack Underflow!! No more element to pop.");
}
// pop element
type element_popped = stack[top--];
return element_popped;
}
- display(): print all elements in stack to console.
- We will print elements in the LIFO order.
template<typename type, int size>
void Stack<type, size> :: display()
{
// check for empty stack
if (is_empty())
{
cout << "Woops! stack is empty." << endl;
return;
}
// loop over stack and display all elements
for (int i = top; i >= 0; i--)
{
cout << stack[i] << " ";
}
cout << endl;
}
- get_top_element(): Returns the top element if stack is not empty.
- Note: out_of_range(msg) is a standard exception defined in <stdexcept> header file.
template <typename type, int size>
type Stack<type, size> :: get_top_element()
{
if (is_empty())
{
throw out_of_range("Stack is empty!!");
}
return stack[top];
}
- clear(): Remove all elements in the stack and reset the top to -1.
template <typename type, int size>
void Stack<type, size> :: clear()
{
// free current memory occupied by the stack
delete[] stack;
// reset top
top = -1;
// assign new memory
stack = new type[size];
}
main Function to test our code:
We created a menu-driven main function to perform each operation on our stack.
Note
- Remember to create a stack object with template syntax providing both parameters - type and size.
- Remember to handle the possible exceptions thrown by push, pop, and get_top_element with a try-catch block.
- The what function used while handling exceptions is a predefined function in all exception classes that will return the message we send while throwing the exceptions.
int main()
{
cout << "Stack implemented as Array";
const int stack_size = 5;
Stack<int, stack_size> my_stack;
int choice;
while(true)
{
cout << "\nChoose an operation:\n";
cout << "1. Push\n" << "2. Pop\n" << "3. Display\n"
<< "4. Display top\n" << "5. Stack empty?\n" << "6. Clear stack\n"
<< "7. Exit" << endl;
cout << "Enter a choice(1-6): ";
cin >> choice;
switch(choice)
{
case 1:
int element;
cout << "Enter element to push: ";
cin >> element;
try
{
my_stack.push(element);
cout << "Pushed to stack\n";
}
catch(const std::exception& e)
{
std::cerr << e.what() << '\n';
}
break;
case 2:
try
{
int popped_element = my_stack.pop();
cout << "Top most element popped: " << popped_element << endl; }
catch(const std::exception& e)
{
std::cerr << e.what() << '\n';
}
break;
case 3:
cout << "Stack right now:\n";
my_stack.display();
break;
case 4:
try
{
cout << "Top most element: " << my_stack.get_top_element() << endl;
}
catch(const std::exception& e)
{
std::cerr << e.what() << '\n';
}
break;
case 5:
my_stack.is_empty() ? cout << "Stack is empty right now.\n" : cout << "Stack is not empty right now.\n";
break;
case 6:
my_stack.clear();
cout << "Stack cleared.\n";
break;
case 7:
exit(0);
break;
default:
cout << "Invalid Input!! Please Try Again.\n" << endl;
break;
}
}
return 0;
}
Read more on Scaler Topics
Abstract Classes in C++
Virtual Base Class in C++
Difference Between C and C++
Constructor and Destructor in C++
If you want to learn C++ from basic to advanced, do check out the C++ course from Scaler Topics.
Top comments (3)
Are you considering entering the field of data science but are hesitant because you lack the necessary experience or training?
There is no doubt that Skillslash is reliable and will guide you in the right direction. It would be an understatement to say Skillslash is one of the top data science institutes in pune. Its innovative approach to online education has made it a world leader.
Visit Our Website:- skillslash.com/data-science-course...
For any questions or comments, please contact us at info@skillslash.com.
Phone: 8391-911-911
DataScienceCourse #DataScienceTraining #DataScienceCertification #DataScience #Skillslash #Pune #DataScienceCoursePune
Hi,
This is the great article .It has given me complete knowledge about the arrays and array methods. I enjoyed and learnt very much from your article.
learnbay.co/data-science-course/
Some comments may only be visible to logged-in visitors. Sign in to view all comments.