Data Structures Class 12 Notes

Data Structures Class 12 Notes

DATA STRUCTURES

A data structure defines a mechanism to store, organise and access data along with operations (processing) that can be efficiently performed on the data. A data structure is a group of data that have different data types which can be accessed as a unit .

For example, string is a data structure containing a sequence of elements where each element is a character. On the other hand, list is a sequence data structures in which each element may be of different types.We can apply different operations like reversal, slicing, counting of elements etc. on list and string.

Hence, a data structure organises a multiple elements in a way so that certain operations on each elements as well as the collective data unit could be performed easily.

Data Structures Class 12 Notes

Data type vs Data structure

• A data type defines a set of values along with well-defined operations stating its input-output behavior.
• A data structure is a physical implementation that clearly defines a way of storing, accessing, manipulating data stored in a data structure.
For example, List as a data type which can store heterogeneous data type of elements, but when implemented as data structure its behavior is clearly prescribed (searching, sorting etc.)

Implementation of data structures can be done in two ways.

Simple Data Structures : Built from primitive data types(integers, real, character, boolean). Example Array or Linear list

Compound Data Structures : Simple data structures are used to form more data structure . They are classified into two types

1.Linear : Means elements are stored in sequential order.

Example: Stack, Queue, Linked List

2.Non Linear : Data can be stored as multilevel structures.

Example Trees, Graph

(Only similarity between stack and queue is that both belong to linear data structures)

Data Structures Class 12 Notes

What is Stack?

• Stack is a Linear Data Structure
• Stack is a list of elements in which an element may be inserted or deleted only at one end ,called the TOP of the stack
• It follows the principle of Last In First Out (LIFO).
• LIFO means the elements inserted last would be the first to be deleted

Operations on Stack

There are mainly two types of Operation that can be done with stack.

i) Push 

ii) Pop 

Push: Insertion of a element on the top of the stack is called Push.

Data Structures Class 12 Notes

Pop : Removal of an element from the top of the stack is called Pop.

Push and Pop Operations are done from single end called TOP

Data Structures Class 12 Notes

Overflow and Underflow case

Overflow : It refers to a situation , when one tries to push an element an element in stack/queue, that is already full . In Python, (for stacks and list implemented as list ), since list can grow, OVERFLOW condition does not arise until the memory is exhausted .

Underflow : It refers to a situation when one tries to pop/delete an item from an empty stack or queue. That is stack or queue is currently having no element and still one tried to pop an element.

Data Structures Class 12 Notes

Implementation of stack using list

The implementation of stack using list in Python is the easiest of all programming language.

Basic operations performed on stack are:

1. Creating a stack
2. Push/Adding elements to the stack
3. Checking for empty stack
4. Pop/Deleting elements from a stack
5. Traversal/Displaying a stack

List methods used and Important things to remember

1. list.append(element) – It is used to implement push operations(used to append or add elements at the end of the list)
2. list.pop() –It is used to implement pop operations(removing elements at the end)
3. list[::-1]-List slicing is used to print the elements in the reverse order from top position to list[0]
4. top=len(list)-1 (length of list -1)
5. stack – LIFO(Last In First Out)
6. Push and Pop through one end(Top)

Data Structures Class 12 Notes

Applications of Stack

1. Reversing a word/line: This can be accomplished by pushing each character on to a stack as it is read. When the line is finished, characters are popped off the stack and they will come off in the reverse order.
2. The compilers use stacks to store the previous state of a program when a function is called during recursion.
3. Backtracking is a form of recursion. But it involves choosing only one option out of possibilities. Used in solving Puzzle Sudoku.
4. Undo mechanism in Text editors by keeping all the text changes in a stack.

Implementation of a stack using list – menu oriented program