Competitive coding is the new desire amongst Computer-Sci. Engineering aspirants, so that they may get placed in big companies. The main focused topic amongst is Data Structures and Algorithms, which is very much useful in solving problems with ease. In this tutorial we are going to discuss about Stacks(but in C programming language), which is one of the key sub-topics of D.S(Data Structures).
Stack is an Abstract Data-type used in every programming language like C, C++, Java etc. It is a Linear Data-Structure in which a particular order is used to implement operations, this order be may LIFO(Last In First Out) or FILO(First In Last Out). As the name suggests, it actually works as a stack, like a pile of books, one on the top of the other, we can create a greater pile by putting more books on the top and decrease the pile size by removing the books from the top.
This is FILO(First In Last Out) approach, that means the first book placed in pile would be the last one to go out(to be removed). And similarly LIFO means the last item would be the first item that would be removed from the whole deck/pile.
Basic Operations That can be performed on Stacks !
- Push : This means adding an element to the stack or pushing an element in the stack. If the stack gets completely filled, and still we try to add more elements, then this condition is known as Stack OverFlow.
- Pop : Removing or deleting an element from the stack. If the stack gets completely empty and we still try to remove elements, then this condition is known as Stack UnderFlow.
- Peek : It gives us the top element of the stack, without removing it from the stack.
- IsEmpty : Checks whether the stack is Empty or not.
- IsFull : Checks whether the stack is Full or not.
* ALL THESE OPERATIONS HAVE A TIME COMPLEXITY AND SPACE COMPLEXITY OF O(1).
Implementation through a Program
#include<stdio.h>
#define SIZE 10
int Stack[SIZE], top=-1;
int isFull()
{
return top==(SIZE-1);
}
int peek() {
return Stack[top];
}
int isEmpty()
{
return top==-1;
}
int push(int item)
{
if (isFull())
{
printf("OVERFLOW");
return -1;
}
printf("%d is pushed to the stack\n",item);
Stack[++top] = item;
printf("Top is now at %d\n", top);
}
int pop()
{
int temp;
if (isEmpty())
{
printf("UNDERFLOW \n");
return -1;
}
temp=Stack[top--];
printf("%d is popped out from the stack\n", temp);
printf("Top is now at %d\n", top);
return temp;
}
int main()
{
int temp;
push(1);
push(2);
peek();
temp=pop();
push(5);
temp=pop();
temp=pop();
temp=pop();
return 0;
}
OUTPUT
1 is pushed to the stack
Top is now at 0
2 is pushed to the stack
Top is now at 1
2
2 is popped out from the stack
Top is now at 0
5 is pushed to the stack
Top is now at 1
5 is popped out from the stack
Top is now at 0
1 is popped from the stack
Top is now at -1
UNDERFLOW
* Here in this program we have implemented stacks with the help of arrays, we can also implement it through Linked Lists. Learn more about this, by clicking here.
Applications of Stacks
- Most used in problems of reversing, like reversing a word.
- For calculating values of expressions by various compilers.
- Even the browsers we use stores all the pages we visited in form of stacks, notice the history page of the browser - the last visited page is at the top always.
- In operations like Undo or Redo in Editing softwares.
- Implemented in many Algorithms like Tower of Hanoi, Topological Sorting, Histogram problem and much more.
Advantages
- Easy to use.
- Cross-platform.
- Time-efficient.
- Very fast method.
Disadvantages
- Lack of scalability.
- Non-flexible meaning random access is not possible.
- Stack memory is very limited.
- Increase risk of stack overflow.
If you have more information about the topic or any correction, do share with us in the comment box,
LETS HELP EACH-OTHER, GROW AND DEVELOP.