Hot Topics
Data Structure
What is Stack and Its Operations:
Stack
As we have discussed in our previous section stack is basically an array which follows LIFO (Last In First Out) principle which is the element inserted first in the stack will be the last element we can take out from stack. We can perform the following operations on stack:
1. push(): It is used to push an element in a stack at the top.
To push elements in a stack we must be sure that the stack has atleast one empty place to push the element.If the stack is full i.e the top reached to last place in stack then we cannot push element.
Here is the Code for Push operation:
void push(int element)
{
/* declaring the top variable in a stack and making
it point to -1 at first when the stack is empty.*/
int top = -1;
int stack[10], size = 10;
// taking the element to insert in stack from user
cin>>>> element >>>>endl;
/*checking if the stack is full the we are printing stack is full in
console that will happen when the top has reached to one
less than size of stack.*/
if (top >= size - 1)
{
cout<<<<”Stack is full” <<<< endl;
} // end of if
/* we are pushing element in stack when atleast there is an
empty place in stack.*/
else
{
/* indexing of stack starts from 0 but at first the stack is
empty and top points to -1.To insert element in stack we
have to bring the index to 0 and everytime after
inserting we have to point top to the new index to insert
element in blank space in stack.*/
stack[++top] = element;
} // end of else
} // end of push
2.pop(): It is used to take out the top most or the last element inserted in stack.
To take out element from stack we must make sure the stack is not empty then only we can pop out elements from stack. If the stack is empty then we can’t take out element.
Here is the Code for Pop operation:
void pop()
{
/* declaring the top variable in a stack and making
it point to -1 at first when the stack is empty.*/
int top = -1;
int stack[10];
// taking the element to insert in stack from user
cin >> element >> endl;
/* when the top is less than equal to -1 means stack is empty as
-1 location is not a part of the stack.*/
if (top <= -1)
{
cout <<”stack is empty” << endl;
} // end of if
else
{
cout <<”The element popped is “<< stack[top] << endl;
top - -;
} // end of else
} // end of pop function
3.peak(): To get the top most element in stack or the last inserted element in stack we use this operation. We cannot get the top element if the stack is empty.
Here is the Code for Peak operation:
int peak()
{
/* declaring the top variable in a stack and making
it point to -1 at first when the stack is empty.*/
int top = -1;
int stack[10];
// taking the element to insert in stack from user
cin >> element >> endl;
// top pointing to -1 means the stack is empty
if (top <= -1)
{
cout <<”stack is empty” << endl;
}
// entering the else block when stack is not empty
else
{
/* storing the element present at the top of stack in an
element variable*/
int element = stack[top];
return element;
} // end of else
} // end of peak
4.Display(): It is used to display all the elements present in the stack.The elements can be displayed only when the stack is not empty.
Here is the code for Display():
void display()
{
// declaring the top variable in a stack and making it point to -1
at first when the stack is empty.int top = -1;
int stack[10];
// taking the element to insert in stack from user
cin >> element >> endl;
// if the stack is not empty we are displaying all the element in
stack if (top >= 0)
{
for (int i = top; i >= 0; i--)
{
cout << stack[i] <<” “;
} // end of for
} // end of if
else
{
cout <<”stack is empty” << endl;
} // end of else
} // end of display
Applications of stack:
1.Evaluating arithmetic expressions such as turning infix expression to postfix expression or vic-e-versa,etc.
2.Reversing a group of data such as string or an array.
3.To store function calls in a sequential manner.
4.It is widely used for backtracking.
Advantages and disadvantages of stack:
Advantages
1. Stack helps to manage data in last in first out order
2. Stack can be used to manage memory efficiently
3. Stack can manage function calls efficiently
4. Stack helps in memory allocation and deallocation
Disadvantages
1. Stack has limited size and the total size must be defined before
2. Stack can overflow if too many objects are inserted in it.
3.You can’t randomly access elements in a stack.
Recursion using Stack
We know recursion is a self calling function but to understand it in depth we need to use stack.
Let us take an example of factorial program using recursion:
int fact(int n)
{
if (n == 1)
return 1;
return n * fact(n - 1);
}
int main()
{
int n = 5;
cout << fact(n) << endl;
return 0;
}Explanation
Step 1:
The main function goes into the stack first and calls fact(n) function.
Step 2:
The fact(n) or fact(5) function goes into the stack.
Step 3:
Then the fact(5) function recursively calls fact(4) function and this fact(4) function goes into the stack.
Step 4:
Then the fact(4) function recursively calls fact(3) function and this fact(3) function goes into the stack.
Step 5:
Then the fact(3) function recursively calls fact(2) function and this fact(2) function goes into the stack.
Step 6:
Then the fact(2) function recursively calls fact(1) function and this fact(1) function goes into the stack.
Step 7:
The fact(1) function returns 1 as here the value of n becomes 1.
After this we will pop out every function call from the stack to get our desired result.
Automata Fixing