What is a stack?

Stack is a linear data structure in which elements are stored in a certain order. It follows the LIFO or FILO approach which is Last In First Out or First In Last Out respectively.

The two main operations that can be performed on the stack data structure are push() and pop().

There are other options which include top(), isEmpty(), etc.

We see a stack in our day-to-day lives. For example, a stack of books, a stack of clothes, a stack of shoeboxes, etc.

Applications of stack

1. Stack can be really handy in solving problems like balanced parenthesis, reversal of a string, stock span problem, etc.
   • Balanced Parenthesis: Suppose you are given a string of parenthesis, say “({})” you need to check if for every opening parenthesis there exists a closing parenthesis. You need to make sure that the order of both closing and opening parenthesis should remain the same.
   • Reversal of a string: Suppose you are given a string, say “takeyouforward” and you need to reverse the string. The result should be “drawrofuoyekat”.
     
     This can be done using a stack by storing the characters in the stack and then popping them out of the stack and simultaneously printing the popped element.
   • Stock Span Problem: You’ll be given a daily price of a stock in the form of an array and you need to return the span of the stock’s price for the current day. 
2. Stack can also be used to implement backtracking approach.
3. Stack can be used in inter-conversion and solving of infix, prefix and postfix expressions.
   • Infix Expression: An expression where operators come in between two operands. Example: “a+b”.
   • Prefix Expression: An expression where operators come before two operands. Example: “+ab”
   • Postfix Expression: An expression where operators come after two operands. Example: “ab+”
   • Stacks can be really useful in solving these types of expressions and would also work in the inter-conversion of these expressions.
4. Calling and implementing of functions is also achieved using stacks.
   
   If a function called by a program calls another function and that function calls another function, we can assume it as a function call stack. Following code helps in understanding the concept.

func1() {
  func2();
}
func2() {
  func3();
}
main() {
  func1();
}

The following diagram represents a function call stack.

5. Stacks can also be used in DFS (Depth First Search)

These are some of the most popular stack applications that we thought of sharing with you, if you know anything else apart from these, please share with us in the comments below.

Special thanks to Yash Mishra for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article