Data Structures
[Link] data type?
Ans: A data type defines a set of values along with well-defined operations stating its input-output behaviour.
Eg: You cannot put a decimal point in an integer or two strings cannot be multiplied.
[Link] data structures?
Ans:A data structure is a physical implementation that clearly defines a way of storing, accessing, manipulating
data stored in a data structure.
The data stored in a data structure has a specific work pattern. Eg: In stack, all insertion and deletions take place
at one end only.
Array:
If the name of the linear list of 10 element is LIL, then its elements will be as LIL[0],LIL[1],LIL[2]……
Array may be one dimensional, two dimensional or multi-dimensional.
Arrays are implemented through list data types or linear list or NumnPy Arrays.
Stacks:
In Stacks list stored and accessed in a special way, where LIFO (Last in First Out) is followed.
In stack, insertion and deletion take place only at one end, called top.
Eg: Stack is similar to a stack of plates.
Queues:
Queue data structures are FIFO (First in First Out) list, where insertion take place at the “rear” end of
the queue and deletion take place at the “front” end of the queue.
Eg: Queue is such as same as a line of people waiting for their turn to vote.
Linked List:
Linked list are special lists of some elements linked to one another.
The logical ordering is represented by having each element pointing to the next element.
Each element is called node. Each element has two parts.
INFO part-It is a part which stores information
Reference part-It is used to store the reference of next element.
Singly and doubly linked list:
Trees:
Trees are multilevel data structures having a hierarchical relationship among its elements called nodes.
Top most node is called the root of the tree and bottom most nodes are called the leaves of the trees.
Each node has some reference pointers pointing to the nodes below it.
Operations on Data structures:
[Link]: Insertion means addition of a new data element in a data structure.
[Link]: Deletion means removal of a data element from a data structure. The data element is searched for
before its removal.
[Link]: Searching involves searching for the specified data element in a data structure.
[Link]: Traversal of data structure means processing all the data elements of it, one by one.
[Link]: Arranging data elements of a data structure in a specified order is called sorting.
[Link]: Combing elements of two similar data structures to form a new data structure of same type is called
merging.
Stack:
POP operation-Removing element from the top of the stack.
PUSH operation-Adding element at the top of the stack.
Dynamic data structure-It can grow and shrink. (Increase /decrease the number of elements.)
Static data structure-It has fixed size.
Other stack terms:
Peek:
Refers to inspecting the value at the stack’s top without removing it. It is also sometimes referred to as
inspection.
Overflow:
Refers to the situation (ERROR) when one tries to push an item in stack that is full.
This situation occurs when the size of the stack is fixed and cannot grow further or there is no memory
left to accommodate new item.
Underflow:
Refers to the situation (ERROR) when one tries to pop/delete an item from an empty stack.
This situation occurs when the stack having no item and still one tries to pop an item.
Implementing stack in Python:
Peek: <stack>[top]
Push: <stack>. append (<item>)
Pop: <stack>.pop()
Types of stack Item-node:
An Item stored in a stack is called item-node sometimes.
Eg: Stack of integers-All the elements of the stack will be integers. (Item-node type-Integers)
Stack of characters-All the elements of stack will be a string. (Item-node type-String)
Stack of logically related information-When you contain logically group information such as member
details, employee details you store all the details in list. (Item-node type- a List)
Polish Strings:
Complex arithmetic operations can be converted into polish strings using stack which then can be executed
with two operands and one operator.
Infix Notations-Operators within the expression.
Eg: (A+B)/(C-D)
Postfix Notations-Operators after the expressions.
Eg: AB+CD-/
Prefix Notations-Operators before the expressions.
Eg: /+AB-CD
#If the program is List based follow the given structure:
Stack=[]
L=[1,2,3,4,5,6,7,8,9]
def push(L,N):
for a in L:
if a%5==0:
[Link](a)
def pop(L):
While stack:
print([Link]())
else:
print(“stack empty”)
push(L,N)
pop(L)
#If the program is dictionary based follow the given structure:
Stack=[]
L={“aa”:100,”bb”:55,”cc”:76,”dd”:90}
def push(L,N):
for key in L:
if L[key]>80:
[Link](key)
def pop(L):
while Stack:
print([Link]())
else:
print(“stack empty”)
push(L,N)
pop(L)