introduction of Data strutter and algirithm.pptx

its all about data structure.in

1. (Data Structure) 7/30/2024 1

2. MUHAMMAD AYAZ MSCS University of Gujrat, Pakistan MCS (Gold Medal) The University of Lahore M.Com University of Sargodha. 7/30/2024 2

3. Data Structure A data structure is any data representation and its associated operations. A ”data structure'' is a ”container'' that holds elements. A data structure has methods for inserting an element retrieving an element deleting an element

4. A data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently. Or A data structure is a specialized format for organizing, processing, retrieving and storing data. There are several basic and advanced types of data structures, all designed to arrange data to suit a specific purpose. Data structures make it easy for users to access and work with the data they need in appropriate ways.

5. Data Structure Proper data structure can make the difference between a program running in a few seconds and one requiring many days. A solution is said to be efficient if it solves the problem within the required resource constraints. Resource Constraint Space and Time

6. A data structure is a way to store and organize data in order to facilitate access and modifications. No single data structure works well for all purposes, and so it is important to know the strengths and limitations of several of them.

7. Selection of a proper data structure Analyze your problem to determine the basic operations that must be supported. Quantify the resource constraints for each operation. Select the data structure that best meets these requirements.

8. Why so many data structure Ideal data structure Fast, elegant, memory efficient. Generates tensions Time vs space One operation’s performance vs another’s The study of data structure is the study of tradeoffs. That’s why we have so many of them.

9. Data Structure Types The four basic data structure types are  linear data structures Array, Stack, Queue, linked list , Tree data structures H ash data structures G raph data structures .

10. Linear data structure:  Data structure in which data elements are arranged sequentially or linearly, where each element is attached to its previous and next adjacent elements, is called a linear data structure.  Examples of linear data structures are array, stack, queue, linked list, etc. Static data structure:  Static data structure has a fixed memory size. It is easier to access the elements in a static data structure.  An example of this data structure is an array. Dynamic data structure:  In the dynamic data structure, the size is not fixed. It can be randomly updated during the runtime which may be considered efficient concerning the memory (space) complexity of the code.  Examples of this data structure are queue, stack, etc. Non-linear data structure:  Data structures where data elements are not placed sequentially or linearly are called non-linear data structures. In a non-linear data structure, we can’t traverse all the elements in a single run only.  Examples of non-linear data structures are trees and graphs.

11. (Array ) 7/30/2024 11

12. Array Array is a type of linear data structure that is defined as a collection of elements with same or different data types . They exist in both single dimension and multiple dimensions . These data structures come into picture when there is a necessity to store multiple elements of similar nature together at one place. Array is a set of pairs (index and value). The difference between an array index and a memory address is that the array index acts like a key value to label the elements in the array. However, a memory address is the starting address of free memory available.

13. Syntax Creating an array in C and C++ programming languages − data_type array_name [ array_size ] = {elements separated using commas} Int arr [5]={23,20,13,26,7} or, data_type array_name [ array_size ]; Int arr [5];

14. Array Representation Arrays are represented as a collection of buckets where each bucket stores one element. These buckets are indexed from ‘0’ to ‘n-1’, where n is the size of that particular array. For example, an array with size 10 will have buckets indexed from 0 to 9. This indexing will be similar for the multidimensional arrays as well. If it is a 2-dimensional array, it will have sub-buckets in each bucket. Then it will be indexed as array_name [m][n], where m and n are the sizes of each level in the array.

15.  A multi-dimensional array (2D or 3D array) can be simply considered an array of arrays. A 2D array can be picturized as a table made of rows and columns like a spreadsheet or a chessboard. And a 3D array is simply a collection of 2D arrays.

16. Why do we need arrays? It is simpler to sort and search for a value in an array Arrays are ideal for processing many values with ease Arrays are useful for storing a variety of values in a single variable. Most applications of of arrays in computer programming necessitate keeping a significant amount of data of a similar type. To hold this much data, we must define a large number of variables. While writing the programs, it would be quite tough to remember the names of all the variables. Instead of naming each variable a different name, it’s simpler to build an array and store all of the elements within it.

17. Application of Arrays : A basic application of Arrays can be storing data in tabular format. For example, if we wish to store the contacts on our phone, then the software will simply place all our contacts in an array. all the quiz scores for a test could be stored in an array with the single variable name: quiz_scores . The first students quiz score would be found in the first "bucket" of the array, the second students score in the "second" bucket, etc. Arrangement of the leaderboard of a game can be done simply through arrays to store the score and arrange them in descending order to clearly make out the rank of each player in the game. A simple question Paper is an array of numbered questions with each of them assigned some marks. 2D arrays , commonly known as, matrices, are used in image processing. It is also used in speech processing, in which each speech signal is an array .  Your viewing screen is also a multidimensional array of pixels. Book titles in a Library Management Systems. Online ticket booking. Contacts on a cell phone.  For CPU scheduling in computer .(in computer science). which the CPU decides the order and manner in which multiple tasks would be executed when it’s asked to perform multiple tasks. Arrays can be a handy data structure to contain the list of processes that need to be scheduled for CPUs that we need to keep track of. To store the possible moves of chess on a chessboard. To store images of a specific size on an android or laptop. Processing an Image

18. Basic Operations in the Arrays The basic operations in the Arrays are insertion, deletion, searching, display, traverse, and update. These operations are usually performed to either modify the data in the array or to report the status of the array. Following are the basic operations supported by an array. Traverse  − print all the array elements one by one. Insertion  − Adds an element at the given index. Deletion  − Deletes an element at the given index. Search  − Searches an element using the given index or by the value. Update  − Updates an element at the given index. Display  − Displays the contents of the array.

19. Stack Stacks in real life: stack of books, stack of plates Add new items at the top Remove an item at the top Stack data structure similar to real life: collection of elements arranged in a linear order. Can only access element at the top 07/30/2024 20

20. A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end only , called top of the stack . i.e. deletion/insertion can only be done from top of the stack. The insert operation on a stack is often called Push operation and delete operation is called Pop operation. 07/30/2024 21

21. Top of the Stack Figure showing stack….. B A D C NULL 07/30/2024 22

22. In a stack , the element deleted from the list is the one most recently inserted. Stack is also referred as Last-in First-out i.e LIFO . A stack can be implemented by means of Array, Structure, Pointer, and Linked List . Stack can either be a fixed size one or it may have a sense of dynamic resizing. , we are going to implement stack using arrays, which makes it a fixed size stack implementation. The example of stack is the stacks of plates used in cafeterias. The order in which plates are popped from the stack is the reverse of the order in which they were pushed onto the stack, since only the top plate is accessible . 07/30/2024 23

23. If an empty stack is popped, we say stack underflows , which is normally an error. and If top of the stack exceeds n , the stack overflows . 07/30/2024 24

24. Stack Operations The most fundamental operations in the stack ADT include: push(), pop(), peek(), isFull (), isEmpty (). These are all built-in operations to carry out data manipulation and to check the status of the stack. Push(X) – insert X as the top element of the stack Pop() – remove the top element of the stack and return it. Peek()/Top() – return the top element without removing it from the stack. 07/30/2024 25

25. Stack Operation The last element to go into the stack is the first to come out: LIFO – Last In First Out. What happens if we call pop() and there is no element? Have IsEmpty () boolean function that returns true if stack is empty, false otherwise. 07/30/2024 26

26. 07/30/2024 27

27. Complexity Analysis: Time Complexity Operations   Complexity push()  O(1) pop()    O(1) isEmpty()  O(1) size() O(1) 07/30/2024 28

28. Types of Stacks: Fixed Size Stack: As the name suggests, a fixed size stack has a fixed size and cannot grow or shrink dynamically. If the stack is full and an attempt is made to add an element to it, an overflow error occurs. If the stack is empty and an attempt is made to remove an element from it, an underflow error occurs. Dynamic Size Stack: A dynamic size stack can grow or shrink dynamically. When the stack is full, it automatically increases its size to accommodate the new element, and when the stack is empty, it decreases its size. This type of stack is implemented using a linked list , as it allows for easy resizing of the stack. 07/30/2024 29

29. Stack Implementation: Array Worst case for insertion and deletion from an array when insert and delete from the beginning: shift elements to the left. Best case for insert and delete is at the end of the array – no need to shift any elements. Implement push() and pop() by inserting and deleting at the end of an array 07/30/2024 30

30. Stack Implementation: Array 07/30/2024 31

31. Stack using an Array In case of an array, it is possible that the array may “fill-up” if we push enough elements. Have a boolean function IsFull() which returns true is stack (array) is full, false otherwise. We would call this function before calling push(x). 07/30/2024 32

32. Advantages of array implementation: Easy to implement. Memory is saved as pointers are not involved. Disadvantages of array implementation: It is not dynamic i.e., it doesn’t grow and shrink depending on needs at runtime. [But in case of dynamic sized arrays like vector in C++, list in Python, ArrayList in Java, stacks can grow and shrink with array implementation as well]. The total size of the stack must be defined beforehand. 07/30/2024 33

33. Stack Using Linked List We can avoid the size limitation of a stack implemented with an array by using a linked list to hold the stack elements. As with array, however, we need to decide where to insert elements in the list and where to delete them so that push and pop will run the fastest. 07/30/2024 34

34. 07/30/2024 35

35. Advantages of Linked List implementation: The linked list implementation of a stack can grow and shrink according to the needs at runtime. It is used in many virtual machines like JVM. Disadvantages of Linked List implementation: Requires extra memory due to the involvement of pointers. Random accessing is not possible in stack. 07/30/2024 36

36. Stack: Array or List Since both implementations support stack operations in constant time, any reason to choose one over the other? Allocating and deallocating memory for list nodes does take more time than preallocated array. List uses only as much memory as required by the nodes; array requires allocation ahead of time. List pointers (head, next) require extra memory. Array has an upper limit; List is limited by dynamic memory allocation. 07/30/2024 37

37. Application of Stack Data Structure: Function calls and recursion:  When a function is called, the current state of the program is pushed onto the stack. When the function returns, the state is popped from the stack to resume the previous function’s execution. Undo/Redo operations:  The undo-redo feature in various applications uses stacks to keep track of the previous actions. Each time an action is performed, it is pushed onto the stack. To undo the action, the top element of the stack is popped, and the reverse operation is performed. Expression evaluation:  Stack data structure is used to evaluate expressions in infix, postfix, and prefix notations. Operators and operands are pushed onto the stack, and operations are performed based on the stack’s top elements. Browser history:  Web browsers use stacks to keep track of the web pages you visit. Each time you visit a new page, the URL is pushed onto the stack, and when you hit the back button, the previous URL is popped from the stack. Balanced Parentheses:  Stack data structure is used to check if parentheses are balanced or not. An opening parenthesis is pushed onto the stack, and a closing parenthesis is popped from the stack. If the stack is empty at the end of the expression, the parentheses are balanced. Backtracking Algorithms:  The backtracking algorithm uses stacks to keep track of the states of the problem-solving process. The current state is pushed onto the stack, and when the algorithm backtracks, the previous state is popped from the stack. Application of Stack in real life : CD/DVD stand. Stack of books in a book shop. Call center systems. Undo and Redo mechanism in text editors. The history of a web browser is stored in the form of a stack. Call logs, E-mails, and Google photos in any gallery are also stored in form of a stack. YouTube downloads and Notifications are also shown in LIFO format(the latest appears first ). Allocation of memory by an operating system while executing a process. 07/30/2024 38

38. Uses/ Applications of Stack 07/30/2024 39

39. Balancing Symbols Compilers check your programs for syntax errors, but frequently a lack of one symbol (such as a missing brace or comment starter) can cause the compiler to spill out a hundred lines of diagnostics without identifying the real error. A useful tool in this situation is a program that checks whether everything is balanced. Thus, every right brace, bracket, and parenthesis must correspond to its left counterpart. 07/30/2024 40

40. The sequence [()] is legal, but [(]) is wrong. Obviously, it is not worthwhile writing a huge program for this, but it turns out that it is easy to check these things. For simplicity, we will just check for balancing of parentheses, brackets, and braces and ignore any other character that appears. The simple algorithm uses a stack and is as follows: Make an empty stack. Read characters until end of file. If the character is an opening symbol , push it onto the stack. If it is a closing symbol and the stack is empty, report an error. Otherwise, pop the stack. If the symbol popped is not the corresponding opening symbol, then report an error. At end of file, if the stack is not empty, report an error. 07/30/2024 41

41. Data Structure - Expression Parsing The way to write arithmetic expression is known as a notation. An arithmetic expression can be written in three different but equivalent notations, i.e., without changing the essence or output of an expression. These notations are − Infix Notation Prefix (Polish) Notation Postfix (Reverse-Polish) Notation These notations are named as how they use operator in expression. 07/30/2024 42

42. Infix Notation We write expression in infix notation, e.g . a - b + c , where operators are used in-between operands. It is easy for us humans to read, write, and speak in infix notation but the same does not go well with computing devices. An algorithm to process infix notation could be difficult and costly in terms of time and space consumption. Prefix Notation In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands. For example, +ab . This is equivalent to its infix notation a + b. Prefix notation is also known as Polish Notation. Postfix Notation This notation style is known as Reversed Polish Notation. In this notation style, the operator is postfixed to the operands i.e., the operator is written after the operands. For example, ab+. This is equivalent to its infix notation a + b. 07/30/2024 43

43. To parse any arithmetic expression, we need to take care of operator precedence and associativity also. Precedence When an operand is in between two different operators, which operator will take the operand first, is decided by the precedence of an operator over others. For example − Operator Precedence As multiplication operation has precedence over addition, b * c will be evaluated first. A table of operator precedence is provided later. Associativity Associativity describes the rule where operators with the same precedence appear in an expression. For example, in expression a + b − c, both + and – have the same precedence, then which part of the expression will be evaluated first, is determined by associativity of those operators. Here, both + and − are left associative, so the expression will be evaluated as (a + b) − c. Precedence and associativity determines the order of evaluation of an expression . Following is an operator precedence and associativity table (highest to lowest) − 07/30/2024 44

44. Sr.No. Operator Precedence Associativity 1 Exponentiation ^ Highest Right Associative 2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative 3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative 07/30/2024 45

45. Use of Stack Example of use: prefix, infix, postfix expressions. Consider the expression A+B: we think of applying the operator “+” to the operands A and B. “+” is termed a binary operator : it takes two operands. Writing the sum as A+B is called the infix form of the expression. 07/30/2024 46

46. Thanks