Concept

Definition

• A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) manner.

• A stack is typically implemented using an array or a linked list.

• The basic operations that can be performed on a stack are:

  • Push: Adds an item to the top of the stack

  • Pop: Removes an item from the top of the stack

  • Peek: Returns the item at the top of the stack without removing it

• Time Complexity:

  • Access -> at O(n).

  • Deletion at O(1).

  • Searching -> O(n)

  • Insertion -> O(1)

Where is Stack Useful?

• Push back, pop front i.e process the last element again

  eg: https://www.interviewbit.com/problems/simplify-directory-path/

  https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

• Next smaller / larger element

  eg: https://www.interviewbit.com/problems/nearest-smaller-element/

• Valid parentheses as a use case

  eg: https://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression/

  • By maintaining scores:
    eg: https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/

• Direct operations over stack

  eg: https://www.interviewbit.com/problems/min-stack/

• For recursion

  eg: DFS https://leetcode.com/problems/binary-tree-preorder-traversal/

Applications of Stacks

Stacks are widely used in many applications. Some of the common examples are:

• The undo/redo functionality in text editors

• Balancing symbols in programming languages

• Backtracking in algorithms such as depth-first search

• Function calls in programming languages

So this is it for this article. I hope it helped you somewhere. Don't forget to support us and share with other geekians.

Thank you, Have a nice day !!