### Data Structures – lists, stacks and Queues - Revision Notes

CBSE Class 12 Computer Science (Python)

Data Structures – lists, stacks and Queues
Revision Notes

• Some important points of Data structure are as follows:
• A data structure is a normal group of data of different data types which can be processed as a single unit.
• Simple data structures are normally built from primitive data types.
• Simple data structure can be combined in various ways to form compound data structure. The compound data structures may be linear (whose elements form a sequence) and non-linear (which are multi-level).
• A Linear list or an array refers to a named list of a finite number 'n' of similar data elements whereas a structure refers to a named collection of variables of different data types.
• Stacks are "LIFO" (Last In First Out) lists where insertions and deletions take place only at one end.
• Queues are "FIFO" (First In First Out) lists where insertions take place at rear end and deletions take place at the front end.
• In linear search, each element of the array is compared with the given Item to be searched for one by one.
• List Comprehension is a concise description of a list that shorthands the list creating for loop in the form of a single statement.
• A list that has one or more lists as its elements is a nested list.
• A regular two-dimensional list is a list having lists as its elements and each element-list has the same shape i.e., same number of elements (length).
• A list that has lists with different shapes as its elements is also a 2d list but it is an irregular 2d list, also known as a ragged list.
• Internally a 2D list stores references of its element lists at its indexes.
• A stack is a linear structure implemented in "LIFO" (Last In First Out) manner where insertions and deletions take place only at one end i.e., the stack's top.
• An insertion in a stack is called pushing and a deletion from a stack is called popping.
• When a stack, implemented as an array, is full and no new element can be accommodated, it is called an OVERFLOW.
• When a stack is empty and an element's deletion is tried from the stack, it is called an UNDERFLOW.
• Polishing string refers to the notation in which the operator symbol is placed either before its operands (this form is called prefix notation) or after its operands (this form is called postfix notation). The usual form, in which the operator is placed in between the operands, is called infix notation.
• A queue is a linear structure implemented in FIFO (First In First Out) manner where insertions can occur only at the rear end and deletions can occur only at the front end.
• Circular Queues are the queues implemented in circle form rather than a straight line.
• Dequeues (double-ended queues) are the refined queues in which elements can be added or removed at either end but not in the middle.
• An input restricted deque is a deque which allows insertions at only one end but allows deletions at both ends of the list.
• An output restricted deque is a deque which allows deletions at only one end of the list but allows insertions at both ends of the list.