Data Types and Data StructuresData StructuresData Structures - AtomicData Structures - ArrayData Structures - Linked ListsSlide 6Slide 7Slide 8Slide 9Data Structures - Linked ListData Structures - StackData Structures - QueueData Structures - Stacks & QueuesData Types and Data Structures•When specifying data in a program we need to describe its type and its structure.•Data's type impose meaning onto data (semantics) and data's structure impose organization (syntax)onto data.•Data Type (definition): A label applied to data that tells the computer how to interpret and manipulate data.–Type tells the computer how much space to reserve for variables and how to interpret operations on them. •Data Structure (definition): The way data is organized logically.–Describes how different pieces of data are organized.(Review Slide)Data Structures•In addition to specifying the type of data, we must also specify how we want it to be organized logically.•Usually data type and structure are not related. –Example: Integer list[n] is an array of n integer values, whileBoolean blist[n] is an array of n Boolean values.•Most data structures have specific operations associated with them, and programming languages that support the structure will provide you with these operations as functions built into the language.–If not provided, you can build the functions yourself.(Review Slide)Data Structures - AtomicName AtomicDefinition A data structure containing a single value, or data item, of any type.Std Functions Assign – places a value in the atomic structure.Retrieve – returns the value currently stored in the structure.Non-Std FunctionsNoneNotesThis is the most basic data structure, from which all others are built. Contains only one data itemCan be placed anywhere in memory.Data Structures - ArrayName ArrayDefinition A group of data elements stored in contiguous memory.Std Functions Assign(n) – store a value in the nth element.Retrieve(n) – retrieves the value stored in the nth element.Non-Std FunctionsLength – returns number of elements in the array. Sort – sorts the elements of the array.Matrix operations, like determinant, transpose, etc.NotesTypically, all elements of an array are of the same type.Typically, each element in an array can be of any type.Advantage: Instant access to any element in the array (ie it is just as easy to retrieve the value of the first element as any other).Disadvantages: Hard to change the size of the array. Hard to insert new elements in the middle of the array.Data Structures - Linked Lists•Array Characteristics:–"Instant" access to every elelement (advantage)–Difficult to change size (disadvantage)•What if you needed to change the the number of elements your program was dealing with quite often?–Example: People logged into Pegasus.–Example: Tracking jobs to be scheduled in a moachine or on a real shop floor.•You could specifiy a very large array to begin with–wastes memory.–gaps appear as elements are removed.•Linked lists allow for changes in the size of the data structure.Data Structures - Linked Lists•Each element of a linked list is composed of two parts:–The data value (can be any type)–A pointer to the next element in the list (type must be a pointer)•Linked List Characteristics:–No "Instant" access to every elelement (disadvantage)–Easy to change size (advantage)1 23 4Data Structures - Linked Lists•Elements are scattered randomly through memory.1234Data Structures - Linked Lists•Easy to add an element (add the new link):12345Data Structures - Linked Lists•Easy to delete an element (add the new link):1234Data Structures - Linked ListName Linked ListDefinition A group of data elements composed of two parts: a value part and a link part. The link points to the next data element in the list.Std Functions Insert(value) – inserts a new element into the list.Remove(value) – removes an element from the list.Non-Std FunctionsNoneNotesThe variable representing the linked list points to the head of the list.The last element in the list has a value of “NULL” for its link.Advantages: The linked list can change size easily.Elements can be inserted and deleted easily into linked lists.Disadvantage: You do not have quick access to members 1 23 4Data Structures - StackName StackDefinition A structure in which only the top element is visible.Std Functions Push(value) – pushes the value on the top of the stack.Pop() – Removes the top value in a stack.Peek() – Returns the value of the top element on the stack.Non-Std FunctionsPush(value1, value2, value3..) - pushes multiple values on the stack.Pop(n) – Pops n elements off the stack.Peek(n) - Returns the value of the nth element.NotesCan be though of as a stack of plates or trays. Exhibits LIFO (Last in First Out) behavior.Useful in task scheduling in which one task must be completed before others can begin.Data Structures - QueueName QueueDefinition A list of elements in which elements are added to one end and removed from the other. Std Functions Enqueue(value) – adds the value to one end of the queue.Dequeue() – removes a value from the queue.Non-Std FunctionsNoneNotesCan be thought of as a line of customers, such as at the bank or grocers.Exhibits FIFO (First in First Out) behavior.Useful in task scheduling in which FIFO is important (Example: printer queues)Data Structures - Stacks & QueuesENTEREXITENTER EXITSTACKQUEUENOTE: STACKS AND QUEUES ARE TYPICALLY DEPICTED LIKE ARRAYS BUT THE INDIVIDUAL ELEMENTS CAN RESIDE ANYWHERE IN