DATA STRUCTURE-LINEAR LIST & STACK-QUEUE
Introduction to Data Structure:
Data Structure is a named group of data of different data types which is stored in a specific way and can be
processed as a single unit. A data structure has well-defined operations, behaviour and properties. Data
Structure is the organisation of data in the computer’s memory.
Data Type defines the type of values we can store and operations we can perform. For example- in a variable
of int data type we cannot store decimal values. Data type also specifies the amount of memory a variable
consumes. Data Structure is the physical implementation that clearly defines a way of storing, accessing and
manipulation of data stored in Computer’s memory.
Python supports Lists as a collection of elements of heterogeneous data type. In Python we will use List as a
Data Structure.
Different Types of Data Structure:
Data structure can be classified into the following two types:
Simple Data Structure: These are built from primitive data types like integer, float, string
or Boolean.
Example: Linear List or Array.
Complex Data Structure : Simple data structures can be combined in various ways to form
more complex data structures called Compund Data Structure. It is of two types:
i) Linear : These are single level data structure i.e. elements are stored in a
Linear or Sequential form.
Example : STACK, QUEUE, LINKED LIST
ii) Non-Linear: These are multilevel data structure.
Example: TREE and GRAPH
Introduction to different types of Data Structure:
Linear List/Arrays:
It refers to a named list of finite number of similar data elements. Each of the data elements
can be accessed by its unique index/subscript position usually 0,1,2,3,…
For example- if the list named “mylist” contains 10 elements -then the first element will be
mylist[0], second will be mylist[1] and so on.
Arrays can be Single Dimensional or Multi Dimensional. In Python- arrays are implemented
through List data types as Linear List or through NumPy arrays.
Stack:
It is a Data Structure that allows us to insert and delete items from one end of the list
Only. This end is called TOP.
Stack works on LIFO principle. It means the item which is added in the list at last will be
removed from the list at first.
Real life Examples: Stack of Plates, Stack of Books etc.
Computer based Examples: Undo Operation, Function Call etc.
Queue:
It is a Data Structure that allows insertion and deletion of elements from different ends
i.e. insertion from REAR END and deletion from FRONT END.
Queue works on FIFO principle. It means the item which is added in the list at first will
will be removed from the list at first.
Real life Examples: People standing in Queue for booking tickets.
Computer based Examples: Keyboard typing, Printing Job etc.
Linked List:
Linked List is a dynamic data structure i.e. the size of a Linked List is not pre-determined before
the execution of the program. It consumes memory as per requirement during runtime and
every item allocated dynamically is be known as NODE.
Each NODE contains 2 parts:
(1) INFO/LIST part which stores the actual data to store like roll no. name, marks etc.
(2) LINK part which holds the memory address of the next allocated node in memory
creating chain of linked items.
There are two types of Linked List- (i) Singly Linked List and (ii) Doubly Linked List
Trees:
Trees are multilevel Data Structure having hierarchical relationships among its elements called
Nodes.
Topmost node is called the Root of the tree and bottom most node is called Leaf of the tree.
Each of the node holds the address of nodes below it.
Basic Operations on Data Structure:
e.g. pop() not only deletes but also
returns the deleted element.
List Comprehensions:
A List Comprehension is a shorthand for list creation using for loop in the form of a single statement.
e.g. 1
Consider the following code:
mylist=[]
for i in range(1,6):
[Link](i*4)
print(mylist)
The above code can be written using List Comprehension as:
e.g.2
Consider the following code:
mylist=[]
for i in range(1,16):
if i%2==0:
[Link](i)
The above code can be written using List Comprehension as:
e.g.3
Consider the following code:
mylist=[]
for i in range(2,10):
if i%3==0:
[Link](‘@’)
else:
[Link](‘*’)
The above code can be written using List Comprehension as:
e.g.4
Arr=[]
for i in [10,20,30]:
for j in [5,10,15]:
[Link](i+j)
print(Arr)
The above code can be written using List Comprehension as:
Advantages of List Comprehensions:
Code Reduction : A code of 3 or more lines gets reduced to single line.
Faster Code Processing : List comprehensions are executed faster than their equivalent for loops
because:
i) Python will allocate the list’s memory before adding the elements to it, instead
of having to resize on runtime.
ii) Also call to append() function gets avoided thus reducing the function
overheads.
Two-Dimensional List:
A 2-D List is a list having all elements as list of same shape i.e. a 2-Dimensional List is a List of Lists.
For e.g.
Mylist=[[20,40,60],[5,10,15],[9,18,27]]
The above is a 2–D List with 3 rows and 3 columns. First Value will be at index [0][0], Second Value will be at
index [0][1] and last will be at index [2][2].
e.g.
Write a Python Program to print a 2-D List in Matrix format.
Ans:
Stack Data Structure:
A stack is a collection of data items that can be accessed at only one end, called top.
In Stack-items can be inserted and deleted from “top” end only.
Stack is a dynamic data structure as it can grow (with increase in number of elements) or shrink (with decrease
in number of elements).
The last item inserted in a Stack is the first one to be deleted. Therefore, Stack follows the concept of Last-
In-First-Out (LIFO) data structure.
Two main operations in a Stack are PUSH & POP. PUSH means inserting new item at the top and POP means
deleting an item from top of the Stack.
The working mechanism of Stack can be graphically represented as :
7 56 top
6 37
5 58
4 26
Positiion
3 25
2 84
1 28
0 11
Length of the List=8
Now, if we want to add a new element-say 100, then the element will be inserted at the “top” position.
8 100 top
7 56
6 37
5 58
Positiion 4 26
3 25
2 84
1 28
0 11
The element 56 onwards shifted towards down and the new element is inserted at the top.
Hence, Length of the List=9
Now, if we have to delete an element –we have to follow LIFO i.e. the element wihich is inserted into the
Stack at last-is the element to be removed from the Stack at first.
100 is removed from the
top
Terminologies of Stack:
Peek: Getting the most recent value of stack i.e value at TOP. This technique is also known as
Inspection.
Overflow: Overflow is an error which occurs when the user tries to push an item in the Stack when the
Stack 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: Underflow is an error when the user tries to pop or delete an item from an empty Stack. This
situation occurs when the Stack is currently empty but still user tries to pop an item from the
Stack.
Implemenation of Stack as a List:
Let us consider that the name of the list is STACK and TOP is the position of the last element in the list.
So, TOP=len(STACK)-1
In order to perform Peek, we can use: print(STACK[TOP])
In order to perform a Push operation in the Stack i.e. to insert an element at the TOP position we can
use: [Link](<item>)
In order to pop or remove the item from the TOP position we can use: [Link]()
Before we delete an element from the Stack or display all the elements of the Stack we must check for
Underflow. This can be done as:
if(STACK==[]):
# Take Necessary Actions.
Write a Python Program using functions to perform Insertion, Deletion and Traversal in a stack
implemented as a List storing the name and age of few persons.
Ans:
This function will check the
def isEmpty(Stack):
if(Stack==[]): Stack is empty or not
return True
else:
return False
def Pushing (Stack, Item): This function will add a new
[Link](Item) item in the Stack. Top is
top=len(Stack)-1 adjusted accordingly.
def Popping(Stack):
if(isEmpty(Stack)==True):
This function will remove an
return "UnderFlow"
else: item from the top of the
Item=[Link]() stack. Underflow is checked
if(len(Stack)==0): before popping.
top=None
else:
top=len(Stack)-1
return Item
This function will return the
def Peek(Stack):
if(isEmpty(Stack)): topmost item from the
return "UnderFlow" Stack.
else:
top=len(Stack)-1
return Stack[top]
def Traversal(Stack):
if(isEmpty(Stack)==True): This function will display the
print("Stack Empty!!!!")
Stack item in LIFO format.
else:
top=len(Stack)-1
for i in range(top,-1,-1):
print(Stack[i])
top=None
Stack=[]
flag=True
while(flag):
print('Press 1 to Insert')
print('Press 2 to Delete') User Interaction Menu
print('Press 3 to Peek')
print('Press 4 to Display')
print('Press 5 to Quit')
c=int(input('Enter Your Choice[1-5]:'))
if(c==1):
name=input('Enter Name:')
age=int(input('Enter Age:'))
Item=[name,age]
Pushing(Stack,Item)
elif(c==2):
item=Popping(Stack)
if(item==-1):
print('Underflow..Cannot Delete')
else:
print(item,'Deleted')
elif(c==3):
item=Peek(Stack)
if item=="Underflow":
print("Stack Empty!!!!")
else:
print('Topmost Item=',item)
elif(c==4):
Traversal(Stack)
else:
print('Quitting the Program')
flag=False
Output:
Press 1 to Insert
Press 2 to Delete
Press 3 to Peek
Press 4 to Display
Press 5 to Quit
Enter Your Choice[1-5]:1
Enter Name: David
Enter Age:21
Press 1 to Insert
Press 2 to Delete
Press 3 to Peek
Press 4 to Display
Press 5 to Quit
Enter Your Choice[1-5]:1
Enter Name:Sam
Enter Age:29
Press 1 to Insert
Press 2 to Delete
Press 3 to Peek
Press 4 to Display
Press 5 to Quit
Enter Your Choice[1-5]:1
Enter Name:Henry
Enter Age:30
Press 1 to Insert
Press 2 to Delete
Press 3 to Peek
Press 4 to Display
Press 5 to Quit
Enter Your Choice[1-5]:3
Topmost Item= ['Henry', 30]
Press 1 to Insert
Press 2 to Delete
Press 3 to Peek
Press 4 to Display
Press 5 to Quit Element Inserted at last is
Enter Your Choice[1-5]:2 deleted first.
['Henry', 30] Deleted
Press 1 to Insert
Press 2 to Delete
Press 3 to Peek
Press 4 to Display
Press 5 to Quit
Enter Your Choice[1-5]:4
Displaying in LIFO Order
['Sam', 29]
['David', 21]
Press 1 to Insert
Press 2 to Delete
Press 3 to Peek
Press 4 to Display
Press 5 to Quit
Enter Your Choice[1-5]:5
Quitting the Program