DATA
STRUCTURES
It a way of organizing and storing data in such
a manner so that it can be accessed and
work over it can be done efficiently and less
resources are required.
It defines the relationship between the data
and the operations over those data.
There are many various types of data
structures defined that make it easier for the
computer programmer, to concentrate on the
main problems rather than getting lost in the
details of data description and access.
List
It is a collections of items and each item has its own index value.
Index of first item is 0 and the last item is n-1.Here n is number of items in a list.
Indexing of list
Creating a list
Lists are enclosed in square brackets [ ] and each item is separated by a
comma.
e.g.
list1 = [‘English', ‘Hindi', 1997, 2000]
list2 = [11, 22, 33, 44, 55 ]
list3 = ["a", "b", "c", "d"]
Access Items From A List
List items can be accessed using its index position.
e.g.
list =[3,5,9]
print(list[0]) 3
print(list[1]) 5
print(list[2]) 9
print('Negative indexing') output Negative indexing
print(list[-1]) 9
print(list[-2]) 5
print(list[-3]) 3
Iterating Through A List
List elements can be accessed using looping
statement. e.g.
list =[3,5,9]
for i in range(0, len(list)):
print(list[i])
Output
3
5
9
Important methods and functions of List
Function Description
list.append() Add an Item at end of a list
list.extend() Add multiple Items at end of a list
list.insert() insert an Item at a defined index
list.remove() remove an Item from a list
del list[index] Delete an Item from a list
list.clear() empty all the list
list.pop() Remove an Item at a defined index
list.index() Return index of first matched item
list.sort() Sort the items of a list in ascending or descending order
list.reverse() Reverse the items of a list
len(list) Return total length of the list.
max(list) Return item with maximum value in the list.
min(list) Return item with min value in the list.
list(seq) Converts a tuple, string, set, dictionary into list.
Stack:
A stack is a linear data structure in which all the
insertion and deletion of data /values are done at
one end only i.e. top.
It is type of linear data structure.
It follows LIFO
(Last In First Out) property.
Insertion / Deletion in stack can only
be done from top.
Insertion in stack is also known as
PUSH operation.
Deletion from stack is also known as
POP operation.
Using List as Stack in Python
The concept of Stack implementation is easy in Python,
because it supports inbuilt functions (append() and
pop()) for stack implementation.
By Using these functions make the code short and
simple for stack implementation.
To add an item to the top of the list, i.e., to push an
item, we use append() function
To pop out an element, we use pop() function.
These functions work quiet efficiently and fast in end
operations.
Stack Operations – Push & Pop
def push(stk,i):
stk.append(i)
top=len(stk)-1
def pop(stk):
if stk==[]:
return "Underflow“
else:
i=stk.pop()
if len(stk)==0:
top=None
else:
top=len(stk)-1
return I
def Display(stk):
if stk==[]:
print("Stack Empty")
else:
top=len(stk)-1
print("Top->",stk[top])
for a in range(top-1,-1,-1):
print(stk[a])
stack=[ ]
top=None # top - position in the stack
while True:
print("STACK OPERATIONS")
print("1.PUSH")
print("2.POP")
print("3.Display")
print(“4.Exit")
ch=int(input("Enter your choice(1-4)"))
if ch==1:
i=int(input("Enter data"))
push(stack,i)
elif ch==2:
data=pop(stack)
if data=="Underflow":
print("Underflow!Stack is empty!")
else:
print("Popped item is",data)
elif ch==3:
Display(stack)
elif ch==4:
break
else:
print("Invalid choice!")
Execution
STACK OPERATIONS STACK OPERATIONS STACK OPERATIONS
1.PUSH 1.PUSH 1.PUSH
2.POP 2.POP 2.POP
3.Display 3.Display 3.Display
4.Exit 4.Exit 4.Exit
Enter your choice(1-4)1 Enter your choice(1-4)2
Enter your choice(1-4)3
Enter data 10
Top->20 Popped item is 10
STACK OPERATIONS 10
1.PUSH STACK OPERATIONS
2.POP STACK OPERATIONS 1.PUSH
3.Display 1.PUSH 2.POP
4.Exit 2.POP 3.Display
Enter your choice(1-4)3 3.Display 4.Exit
Top->10 4.Exit Enter your choice(1-4)3
Enter your choice(1-4)2 Stack Empty
STACK OPERATIONS Popped item is 20
1.PUSH STACK OPERATIONS
2.POP STACK OPERATIONS 1.PUSH
3.Display 2.POP
1.PUSH
4.Exit
2.POP 3.Display
Enter your choice(1-4)1
3.Display 4.Exit
Enter data 20
4.Exit Enter your choice(1-4)4
Enter your choice(1-4)3 >>>
Top->10
Applications of Stack
• Expression Evaluation: It is used to evaluate prefix, postfix and
infix expressions.
• Expression Conversion: It can be used to convert one
form of expression(prefix,postfix or infix) to one another.
Infix a+b Prefix +ab Postfix ab+
• Syntax Parsing: Many compilers use a stack for parsing the syntax
of expressions.
• Backtracking: It can be used for back traversal of steps in a
problem solution.
• Parenthesis Checking: Stack is used to check the proper opening
and closing of parenthesis.
• String Reversal: It can be used to reverse a string.
• Function Call: Stack is used to keep information about the
active functions or subroutines.
