Stacks

Contents
About Stacks
Structure of stacks
Real-world usages of stacks
Types of operations
Time Complexity of operations

Programs on Stack
Stacks - perform getmin in O(1) operation

About Stacks

• Stacks are powerful data structures.
• They help us solve complex real-world problems.

Structure of stacks

• We can consider stacks as part of arranging books one by one, once we keep adding books and complete adding, now if we want to remove it we have to traverse from the top and if we want to reach the bottom book, we need to remove all the books on the top one by one and reach the bottom.
• Thus they are called LIFO - Last In First Out data structures.

Stacks are like a wrapper around a linked list or an array that helps us perform various operations by storing and accessing the objects

Real-world usages of stacks

• It helps to implement undo mechanism
• It helps in building compilers ... Ex: syntax checking.
• Evaluating the expressions ... Ex: If we are building the calculator and say we want to evaluate an expression (1+2*3).
• Helps in building the Navigation .. Ex: pressing the back stack in android device.

Types of operations

• Push -------> Adding the element to the stack.
• Pop --------> Removing the element from the stack.
• Peek -------> Getting the element from the top of the stack without removing it.
• isEmpty() --> Tells us if the stack is empty or not You can observe there are no look up's because the stacks are not meant for like storing the products and to access it

Time Complexity of operations - All operations of stack run in constant time

• Push -------> O(1)
• Pop --------> O(1)
• Peek -------> O(1)
• isEmpty() --> O(1)