Presentation on Data Structure : Presentation on Data Structure Presented by: Pardeep Sharma M Tech(CSE) pardeepsharma727@gmail.com
What is Data Structure : Data structure is representation of the logical relationship existing between individual elements of data We can also define it as a mathematical or logical model of particular organization of data item. Data Structure mainly specifies the following four things : Organization of data. Accessing Method. Degree of associativity . Processing Alternatives. What is Data Structure
CLASSIFICATION OF DATA STRUCTURE : 1-PRIMITIVE DATA STRUCTURE:- INTEGER, FLOAT, CHARACTER, POINTER 2-NON-PRIMITIVE DATA STRUCTURE:- ARRAYS, FILES, LISTS CLASSIFICATION OF DATA STRUCTURE
PowerPoint Presentation : A stack is a non – primitive linear data structure. It is an ordered list in which addition of new data type and deletion of already existing data item is done only one end, known as top of the stack (TOS). As all the deletion and insertion in stack is done from top of the stack, last item added will be first removed from the stack. This the reason why stack is called as LAST-IN-FIRST-OUT. Stack
Implementation on Stack : Implementation on Stack Static Implementation : Using array Dynamic implementation : Using pointer also called link-list. Operation On Stack : Push Pop Peek
: Operations C B B B A A A A A
Dynamic Implementation : Dynamic Implementation In the Dynamic Allocation, the memory is not pre-allocated. Memory is allocated whenever it is required. And it is de-allocated (removed) when it is no longer needed. We allocate and de-allocate the memory by using the functions : malloc( ); malloc(sizeof(datatype)); free( ); free(datatype);
Application On Stack : Application On Stack Stack Frame : When a procedure of function called a number of word stack frame is push on to a stack. When procedure of function returns, this frame of data is pop off from stack. Reversing a String : This stack can be used to reverse a string. Calculation of Postfix : Infix, Prefix, Postfix.
INFIX NOTATION : The infix notation is what we come across in our general mathemtiics,where the operator is written in-between the operands. FOR EXAMPLE:- A+B*C INFIX NOTATION
PREFIX NOTATION : In prefix notation the operator is written before the operands,it is also called polish notation. FOR EXAMPLE:- +*ABC PREFIX NOTATION
POSTFIX NOTATION : In postfix notation the operators are written after the operands. It is also known as suffix notation or reverse polish notation. FOR EXAMPLE:- ABC*+ POSTFIX NOTATION
PowerPoint Presentation : Postfix Evaluation Operand: push Operator: pop 2 operands, do the math, pop result back onto stack 1 2 3 + * Postfix Stack 1 2 3 + * 2 3 + * 1 3 + * 1 2 + * 1 2 3 * 1 5 // 5 from 2 + 3 5 // 5 from 1 * 5
Queue : Queue A queue is a non-primitive linear data structure. It is an homogeneous collection of elements in which new elements are added at one end (rear), and existing elements are deleted from other end called Front end. The queue is logically a First-in-First-out (FIFO) type of list Insert (queue) Remove (queue) rear front
Priority Queue : Priority Queue A Priority queue is a kind of queue in which each element is assigned a priority and the order in which elements are processed depend upon their priority. An element with higher priority is processed first before any element of lower priority. If queue is sorted as per the priority then insertion will be slow and service will be fast. If the queue is not sorted as per priority then insertion is faster and service is slower.
PowerPoint Presentation : Application of Queues In a multitasking operating system, the CPU time is shared between multiple processes. At a given time, only one process is running, all the others are ‘ sleeping ’ . The CPU time is administered by the scheduler. The scheduler keeps all current processes in a queue with the active process at the front of the queue. Next process Process D C B A Queue Running process
PowerPoint Presentation : Round-Robin Scheduling Every process is granted a specific amount of CPU time, its ‘ quantum ’ . If the process is still running after its quantum run out, it is suspended and put towards the end of the queue. next process Next Process D C B A Process Running Queue Process A D C B
Singly Linked Lists : Singly Linked Lists A singly linked list is a concrete data structure consisting of a sequence of nodes Each node stores element link to the next node next elem node A B C D
Inserting at the Head : Inserting at the Head Allocate a new node Insert new element Make new node point to old head Update head to point to new node
Removing at the Head : Removing at the Head Update head to point to next node in the list Free the first node.
Inserting at the Tail : Inserting at the Tail Allocate a new node Insert new element Have new node point to null Have old last node point to new node Update tail to point to new node
Removing at the Tail : Removing at the Tail Removing at the tail of a singly linked list cannot be efficient ! There is no constant-time way to update the tail to point to the previous node We have to an another pointer and travel it from the head.
Doubly Linked List : Doubly Linked List A doubly linked list is often more convenient! Nodes store: element link to the previous node link to the next node Special trailer and header nodes prev next elem trailer header nodes/positions elements node
Insertion : Insertion We visualize operation insertAfter(p, X), which returns position q A B X C A B C p A B C p X q p q
Deletion : Deletion We visualize remove(p), where p == last A B C D p A B C D p A B C
PowerPoint Presentation : THANKYOU