How to create a stack in C++
A stack is a data structure, which is of linear type. A specific order has to be followed while inserting and deleting the elements from the stack. Generally, stack follows LIFO (Last In First Out) or FILO (First In Last Out).
LIFO: The element inserted at the end will be deleted first.
FILO: The element inserted at the first position will be deleted last.
Both LIFO and FILO mean the same here.
Applications of Stack Data Structure
1. Expression conversion
Postfix, prefix, and infix expression conversions are implemented using a stack. With the help of stack operations, those conversions will be performed.
2. Backtracking
Stack helps backtrack from the current position to the previous position.
3. String Reversal
Stack helps us in reversing a string. First, we store all the characters of a string into the stack, and then we pop those characters from the stack. This operation will result in reversing a string.
4. Algorithms
Many algorithms are implemented using stack.
5. Recursion
Recursion uses the stack for its base case and the multiple function calls that are made.
6. Memory Management
Stack plays a vital role in Memory management, where all essential operations by an operating system are performed through memory management.
Implementation/Creation
In C++, a stack can be implemented or created without STL and STL. Here STL is known as Standard Template Library. The only difference is that STL contains all inbuilt libraries and methods which help implement a stack.
Before creating a stack, some terminology is essential for us to understand stack operations.
Some points to be noted:
- Push: With this operation, a new element is added to the stack's top, replacing the existing or previous top element. Followed by increasing the size of the stack by one.
- Pop: This operation helps in deleting the top element from the stack and reduces the size of the stack by one each time.
- Peek: The top element from the stack is returned by this operation.
- Size: Size is used to determine how many elements are present in the stack overall.
- Display: Display is used to print the elements in the stack in order, starting from the top to bottom.
- top = SIZE-1 means stack is full and top = -1 means stack is empty.
Let's first see the creation of a stack without STL
Program to create a stack in C++ by using an array without STL
#include<iostream>
using namespace std;
#define SIZE 40
int stack [ SIZE ], top = -1;
void push ( int ele )
{
if (top == SIZE-1)
{
cout<<"Stack Over Flow"<<endl;
}
else
{
top++;
stack [ top ] = ele;
}
}
void pop ( )
{
if (top==-1)
{
cout<<"Stack under-Flow"<<endl;
}
else
{
int element=stack[top];
cout<<"Element "<<element<<" popped/deleted Successfully."<<endl;
top--;
}
}
void peek()
{
if(top==-1)
cout<<"Sorry!there are no elements present in the stack"<<endl;
else
cout<<"The top most element in the stack is: "<<stack[top]<<endl;
}
void size()
{
cout<<"The size of the stack is: "<<top+1<<endl;
}
void displayStack()
{
int i;
if ( top == -1 )
{
cout<<"Stack is empty, there are no elements present!"<<endl;
}
else
{
cout<<"The element(s) in the stack are :"<<endl;
for (int i=top; i>= 0; i--)
cout<<stack[i]<<endl;
}
}
int main()
{
int choice, element;
while(1)
{
cout<<"Stack Operations are:"<<endl;
cout<<"Choice-[1]:Push"<<endl;
cout<<"Choice-[2]:Pop"<<endl;
cout<<"Choice-[3]:Peek"<<endl;
cout<<"Choice-[4]:Size"<<endl;
cout<<"Choice-[5]:Display Stack"<<endl;
cout<<"Enter your choice from the above : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the element to insert into the stack :";
cin>>element;
push(element);
cout<<"Element "<<element<<" Pushed/Inserted Successfully."<<endl;
break;
case 2 :
pop();
break;
case 3 :
peek();
break;
case 4 :
size();
break;
case 5 :
displayStack();
break;
default:
return 0;
}
}
}
Output
Now, Let's see the creation using STL.
STL is a powerful template library which makes our life easier. It contains almost all inbuilt libraries, methods, functions etc.
Considering the current data structure stack, all the operations we have implemented above, like push, pop, and peek, can be used here directly without any specific implementation.
The only that has to be done is to include this: " #include<bits/stdc++.h " or you can also include " #include<stack> " which is stack specific.
Some points to be noted :
- push(): : With this operation, a new element is added to the stack's top, replacing the existing or previous top element. Followed by increasing the size of the stack by one.
- pop(): This operation helps in deleting the top element from the stack and reduces the size of the stack by one each time.
- top() : The top element from the stack is returned by this operation.
- size() : Size is used to determine how many elements are present in the stack overall.
- empty() : It is used to check whether the stack is empty or not.
All the above operations are included in '#include<stack>'. Hence, no specific implementation would be required for them, as we did in the previous program.
Syntax of Stack In STL
stack <type> stackName;
stack is a pre-defined template keyword used to create a stack's object.
type indicates the data type that has to be passed. It denotes a particular data type of the elements stored in the stack, like int, which keep only integers, char that store only characters etc.
stackName indicates the name of the stack object that has been created. We can perform all the stack operations with that particular name.
Program to create a stack in C++ with STL
#include <iostream>
#include <stack>
using namespace std;
// Stack implementation in C++ using ‘std::stack’
int main()
{
stack<int> st; //Intializing a stack which can store integers.
st.push(10); // Inserting 10 into the stack
st.push(20); // Inserting 20 into the stack
st.push(30);
st.push(40);
st.push(50);
st.push(60);
// prints the total number of elements present in the stack
cout << "The size of the stack is " << st.size() << endl;
// prints the top element of the stack
cout << "The top element is " << st.top() << endl;
st.pop(); // top elemet 60 will be removed.
cout<<"Top element Deleted successfully"<<endl;
st.pop(); // next top element 50 will be removed.
cout<<"Next Top element Deleted successfully"<<endl;
cout << "The size of the stack is " << st.size() << endl;
while(1)
{
if (st.empty())
{
cout <<"The stack is empty\n";
break;
}
else
{
int ele=st.top();
cout<<"The element is :"<<ele<<endl;
}
st.pop();
}
return 0;
}
Output