## Data Structure

A data structure is a special way of organizing and storing data in a computer so that it can be used efficiently. Array, LinkedList, Stack, Queue, Tree, Graph etc are all data structures that stores the data in a special way so that we can access and use the data efficiently. Each of these mentioned data structures has a different special way of organizing data so we choose the data structure based on the requirement, we will cover each of these data structures in a separate tutorials.

##### Instruction

- Watch all the videos first
- Then read this blogs which I have written here
- Don’t miss anything which I am explaining here

#### Data Structure Types :

1. Linear Data Structure

2. Non-linear Data Structure

##### 1. Linear Data Structure :

Elements of Linear data structure are accessed in a sequential manner, however the elements can be stored in these data structure in any order. Examples of linear data structure are: LinkedList, Stack, Queue and Array.

##### 1. Non-Linear Data Structure :

Elements of non-linear data structures are stores and accessed in non-linear order. Examples of non-linear data structure are: Tree and Graph

### What Is Stack ? :

It is type of linear data structure.

It follows LIFO (Last In First Out) property.

It has only one pointer TOP that points the last or top most element of Stack.

Insertion and Deletion in stack can only be done from top only.

Insertion in stack is also known as a PUSH operation.

Deletion from stack is also known as POP operation in stack.

Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.

### Applications Of Stack :

1. Conversion ofpolish notations

There are three types of notations:

> Infix notation – Operator is between the operands : x + y

> Prefix notation – Operator is before the operands : + xy

> Postfix notation – Operator is after the operands : xy +

Note : Exam will ask 2,3 objective on Prefix Postfix .

2. To reverse a string A string can be reversed by using stack. The characters of string pushed on to the stack till the end of the string. The characters are popped and displays. Since the end character of string is pushed at the last, it will be printed first.

3. Recursion

4. Parsing

5. Tree Traversals

### Algorithm for POP operation :

Now lets consider an example of a stack is the pile of dinner plates that you encounter when you eat at the local cafeteria: When you remove a plate from the pile, you take the plate on the top of the pile .

That means you did POP operation in programming sense .

Pop means retrieve data from array or list which is inserted at last . Thats why its called Last Input First Output .

For Implement Do following Steps :

1. Check if the stack is empty or not.

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

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

### Algorithm for PUSH operation :

Now same above example . After finish your dinner you will keep that plates for wash . That means you are inserting data into stack .

For example first you keep your plate for wash , After than your brother keep plate obviously he will keep plate on above of your plate .

Hope you understand how PUSH works in stack PUSH means Insert data in array or list .

For Implement Do following Steps :

1. Check if the stack is full or not.

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

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

Position of Top | Status of Stack |
---|---|

`-1` | Stack is Empty |

`0` | Only one element in Stack |

`N-1` | Stack is Full |

`N` | Overflow state of Stack |