JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

SQP1 Stack Implementation Using Array

What is Stack?

A stack is a non-primitive linear data structure. it is an ordered list in which the addition of a new data item and deletion of the already existing data item is done from only one end known as the top of the stack (TOS). The element which is added in last will be first to be removed and the element which is inserted first will be removed in last. As all the deletion and insertion in a stack is done from the top of the stack, the last added element will be the first to be removed from the stack. That is the reason why stack is also called Last-in-First-out (LIFO).

Stack Implementation

The stack can be implemented in two ways :

Static implementation

Dynamic implementation

Static Implementation: – Here array is used to create a stack. it is a simple technique but is not a flexible way of creation, as the size of the stack has to be declared during program design, after that size implementation is not efficient with respect to memory utilization.

Dynamic implementation: – It is also called linked list representation and uses a pointer to implement the stack type of data structure.

Some Basics operations on the Stack

push()

pop()

top() or peek()

size()

empty()

Notes

Note: Zoom for Better Understanding

Push(): Push Function used for the put the element to the Stack if the stack limit is Not Overflow under the Limit or The process of adding new elements to the top of the stack is called push operation.
Conditions:

Check if the stack is full or not.

If the stack is full, then print error of overflow and exit the program.

If the stack is not full, then increment the top and add the element.

                    push (Stack, Size, Limit, x) 
                        { 
                        if (Limit=Size) 
                        Print stack overflow and exit
                        Limit = Limit + 1
                        Stack[Limit] = x
                        EXIT
                        }
                 

Pop(): Pop Function The process of deleting an element. from the top of the stack is called POP operation
Conditions:

Check if the stack is full or not.

If the stack is empty, then print error of underflow and exit the program.

If the stack is not empty, then print the element at the top and decrement the top.

                    pop (Stack, Size, Limit) 
                        { 
                        if (Limit==-1) 
                        Print Underflow 
                        X = Stack[Limit] 
                        Limit=Limit-1 
                        Return X and Exit 
                        }
                 

Top() or Peeks(): Means Prnt the Top Element from the Stack.
Conditions:

Check if the stack is not Empty.

If the stack is empty, then print error of underflow and exit the program.

If the stack is not empty, then print the element at the top of the Stack

                    top (Stack, Size, Limit) 
                        { 
                        if (Limit==-1) 
                        Print Underflow error
                        X = Stack[Limit] 
                        Return X and Exit 
                        }
                 

Size(): Size function used for find the Size of the Stack.
Conditions:

Check if the stack is not Empty.

If the stack is empty, then print -1

If the stack is not empty, then print Limit is our Size of the Stack

                    size (Stack, Size, Limit) 
                        { 
                        if (Limit==-1) 
                        Print Underflow error
                        
                        Return Limit and Exit 
                        }
                 

Empty(): Empty function is Used for check Stack Stck is Empty or Not.
Conditions:

Check if the stack is not Empty.

If the stack is Not empty, then print -1 or False

If the stack is empty, then print 1 or True

                  empty (Stack, Size, Limit) 
                      { 
                      if (Limit==-1) 
                      Print(1)
                      
                      Return -1
                      }
               

Code Zone!

Time Complexity:Push Operation : O(1)
Pop Operation : O(1)
Top Operation : O(1)
Empty Operation: O(1)
Size Operation: O(1)
Search Operation : O(n)
Space Complexity:O(N) O(N) Size of the Stack