Stack using Arrays in C++
As you know all the elements of a stack are of the same data type, like, Int, Float, Char, and so on, so implementation of the stack using Arrays in C++ is very easy.
The first element of the stack can be put in the first array slot, the second element of the stack in the second array slot, and so on.
The top of the stack is the index of the last element added to the stack. In this way, stack elements are stored in an array.
However, by definition, a STACK is a data structure in which the elements are accessed (popped or pushed) at only one end i.e. a Last In First Out data structure.
Stack
Thus, a stack element is accessed only through the top, not through the bottom or middle.
This feature of a stack is extremely important and must be understood well.
Related: Stack Using Linked List C++ Program
What is a Stack?
The stack is a non-primitive linear data structure in which the addition of new data elements and deletion of already existing data elements is performed only from one end i.e, the top of the stack.
Stack uses the LIFO algorithm i.e, Last In First Out (LIFO) structure.
For beginners, it is a little bit confusing, but it is a very easy concept
Read More: Queue Using Array C++
Now take an example.
1. 10 plates placed on each other in a kitchen is a stack because when we add more plates we put them on the top. and when we take a plate from it we pick up the top plate first.
So it simply follows the LIFO (Last In First Out) data structure.
Push and Pop are the standard forms for the insertion and deletion of data elements in the stack.
1. Push is simply placing data on the top of the stack. Or when we add data to this list we call it to push into the stack.
2. Pop is simply deleting the elements but only from the top. It is called pop from the stack.
Since stack elements are only accessed from the top so we must update top in all the operations.
Whenever a stack is created, the stack base remains fixed, as new elements are added to the stack from the top.
See Also: Linked List C++ Program
Stack using Arrays C++ Program
//C++ program of stack using arrays
#include<iostream>
#include<stdio.h>
#include<conio.h>
#include<process.h>
using namespace std;
#define SIZE 5
//make a class & name it stk
class stk
{
int stack[SIZE]; //stack using arrays
int top;
public:
void push();
int pop();
void display();
stk()
{
top=-1;
}
};
void stk::push() //push function definition
{
int item;
if(top==SIZE-1)
{
cout<<"Stack is Full\n";
return(0);
}
else{
cout<<"Enter element to push: \n";
cin>>item;
top=top+1;
stack[top]=item;
}
}
int stk::pop()
{
int temp;
if(top==-1)
{
cout<<"Empty Stack:\n";
return(0);
}
else
{
temp=stack[top];
top=top-1;
}return(temp);
}
//travese and display
void stk::display()
{
if(top==-1)
cout<<"stack empty\n";
else
{
for(int i=top; i>=0; i--)
{
cout<<"Elements are:\t";
cout<<stack[i];
}
}cout<<endl;
}
int main(){
int option=0;
stk s;
int element;
while(1)
{
cout<<" ---------------------------------\n";
cout<<"enter 1 to push:\nenter 2 for pop:\n";
cout<<"enter 3 for display:\nenter 4 for exit\n";
cout<<" ---------------------------------\n";
cout<<"Enter option: \n";
cin>>option;
switch(option){
case 1:
s.push();
break;
case 2:
element=s.pop();
cout<<" ---- sucessful ----";
cout<<"popped element is= "<<element<<endl;
break;
case 3:
s.display();
break;
case 4:
exit(0);
default:
cout<<"wrong choice\n";
break;
}
}
getch();
return 0;
}Code language: PHP (php)Read Also: Stack Using Linked List C++
Suggested Read:
Applications of Stacks | Implementation of stack
Stack is the most important data structure, which has a wide range of uses both in the user programs and system programs.
Suppose that you have a program with several functions.
- Now suppose that function A calls function B, function B calls function C, and function C calls function D.
To be specific, suppose that you have the functions A, B, C, and D in your program.
When function D terminates, control goes back to function C;
when function C terminates, control goes back to function B; and when function B terminates, control goes back to function A.
2. During program execution, how do you think the computer keeps track of the function calls? What about recursive functions?
Related: What is Binary Search Tree
Recursion is the most and important result of the stack.
Since various problems are recursive in nature that must be solved recursively for better results and performances.
Recursion works completely on the stack operations.
It’s pushes are the return values and variables into the stack and after all the recursive calls are called and calculated then it pops the results from the stack to summarize the final results and returns this back to the calling function.
The computer uses stacks to implement function calls.
Stacks can also be used to convert recursive algorithms into non-recursive algorithms, especially recursive algorithms that are not tail-recursive.
Also Read: Binary Search Tree C++
Stacks have numerous other applications in computer science.
- Postfix Expression, The stack is also very helpful in the evaluation of Postfix expressions. As expressions needs to be computed correctly so by using stack we change the general expressions into the Postfix expression.
- Stack Frames, Almost programs compiled from modern high level languages make use of a stack frame for the working memory or each procedure or function invocation.
- Reversing a String, Since stack operates from top to bottom, therefore reversing a string is quite easy by using stacks.
After developing the tools necessary to implement a stack, we will examine some applications of stacks.
A stack can be implemented in two ways static so size is fixed at compile-time and cannot be changed during run time.
Also in Dynamic, we do not set any size because the stack can grow during run time and shrink during run time.
1. Implementation of stack using arrays in C/C++ is Static.
2. Implementation of stack using Linked Lists in C/C++ is Dynamic.
Related: