Data Structure Chapter Notes | Computer Science for Grade 12 PDF Download

Data Structures and Lists

Revision Notes

• A data structure is a named group of data of different data types which can be processed as a single unit.
  
• Queues are FIFO lists where insertion take place at REAR end and deletion take place at FRONT end.
• Stacks are LIFO lists where insertion and deletions take place at one end referred as TOP.
• Some important sorting algorithms are Bubble sort, Insertion sort and selection sort.
• Some applications of stacks are :
  • Expression evaluation
  • String Reversal
  • Memory management
• Circular queues are the queues postfix conversion implemented in circular form rather than a straight line.
• Array : A set of contiguous collection of similar data type. In contrast Python lists are actually arrays of variable length and have elements of different data types.
• Sequential allocation of memory: Elements stored in object or neighbour of their declaration.
• Traversal : To move in a list in a sequential manner starting from first to last element. 
• Raw data are raw facts.
• Data item represent single unit of values of certain type.
• Simple data structures are normally built from primitive data types e.g. arrays or linear lists.
• Compound data structures are formed by combining simple data structures. 
• Linear data structures are arrangement of elements to from a sequence e.g. stack, queue and linked list. 
• Non-linear data structure are multilevel data structures e.g Tree and graph.
• Operations on Data Structures
  • Insertion means addition of a new data element in a data structure. 
  • Deletion means removal a data element from a data structure. 
  • Searching means to look for a specified data element in a data structure.
  • Traversal refers to one-by-one processing of all the data elements.
  • Sorting means arranging all the data elements of a data structure in a specified order.
  • Merging means combining two similar, data structure to from a new data structure of same type
• Sequential Allocation : The elements of a sequence data type are allotted memory sequentially.
• Getsizeof() function of sys module is used to check for the memory size of something.

Stacks

Revision Notes

• A stack is a linear structure implemented in LIFO manner.
• Insertions and deletions both occur only at one end i.e. TOP.
• Removing data is called POP. 
• Adding data is called PUSH.  
• It is a dynamic data structure i.e. it can grow and shrink. 
• Peek refers to inspecting the value at stack’s top without removing it.  
• Overflow refers to when one tries to push an item in stack that is full. 
• Underflow refers to when one tries to POP an item from an empty stack.    
• Postfix notation refers to when operator is placed after its operands.

Queues

Revision Notes

• Queues are linear data structures implemented in FIFO (First In First Out) order. 
• Insertions take place at the “rear ” end and deletions take place at the “Front” end of the queue. 
• Deques or double-ended queues are the refined queues in which elements can be removed or added at either end but not in the middle.  
• Input restricted deque is one which allows insertions at only one end but deletions are allowed at both ends.   
• Output restricted queues is one which allows deletions at only one end of the list but insertions are allowed at both ends. 
• Enqueue – Insertion of an element in the queue.
• Dequeue – Deletion of an element in the queue.