As per

Term wise
Syllabus
2024-25

Chapter
Data-structures:
Stack

Computer Science
Class XII ( As per CBSE Board)
 Learning objectives

Objective

• Linear data structures

• Type of Linear data structures

▪ Stacks – PUSH, POP using a list (Single Data, Multiple Data)

▪ Queue- INSERT, DELETE using a list (Single Data, Multiple Data)

• Implementation in Python

2
 Data Structure
What is Data Structure ?
• Data structures are a way of organizing and storing data so

that they can be accessed and worked with efficiently.

• Linear Data Structures

▪ Data collections of ordered items
▪ Order depends on how items

are added and removed

▪ Once added item stays in position

▪ Examples: stacks, queues

3
 Linear Data Structure

Characteristics Linear Data Structures:

• Two ends (left – right, front – rear)

• Linear structures distinguished by how items are added and
removed
• Additions of new items only allowed at the end
• Deletion of existing items only allowed at the end
• Appear in many algorithms

4
 Linear Data Structure
Stack:
• Stacks are linear Data Structures which are based on the principle
of Last-In-First-Out (LIFO) where data which is entered last will
be the first to get accessed.
▪ Addition/removal of items always takes place at same end (top)
▪ Base represents bottom and contains item has been in stack the
longest
▪ Most recently added to be removed first (last in-first-out, LIFO)
▪ Top: newer items;
▪ bottom: lower items

5
 Stack
Operations of Stack
• PUSH: pushing (adding) elements into Top of Stack,
• POP: Popping (deleting) elements and accessing elements from Top of
Stack.
• TOP: This TOP is the pointer to the current position of the stack.

6
 Stack

Applications Using Stacks

• Stacks are prominently used in applications such as:
▪ Recursive Programming
▪ Reversing words
▪ Expression Conversion
• In-fix to Post-fix
▪ Backtracking
▪ Undo mechanisms in word editors
▪ Check if delimiters are matched
• Matching of opening and closing symbols: {,},[,],(,)
• Check: {{a}[b]{[{c}](d(e)f)}((g))} and ({[a}b(c)])

7
 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 define 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.
Python Data Structure
 Data-structures

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"];
 Data-structures

Access Items From A List

List items can be accessed using its index position.
e.g.
list =[3,5,9]
print(list[0]) 3
5
print(list[1]) 9
print(list[2]) output Negative indexing
print('Negative indexing') 9
print(list[-1]) 5
print(list[-2]) 3
print(list[-3])
 Data-structures

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
 Data-structures

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.
 Data-structures

Stack:
A stack is a linear data structure in which all the
insertion and deletion of data / values are done at one end only.
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
a PUSH operation.
Deletion from stack is also known
as POP operation in stack.
 Data-structures

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.
• 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.
 REAL LIFE EXAMPLES OF STACK

B SA UB RU E S H P , 9787640719 YES WE CS
 Data-structures

Using List as Stack in Python:

The concept of Stack implementation is easy in Python ,
because it support 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 and to pop out an element we
use pop() function. These functions work quiet efficiently
and fast in end operations.
 Data-structures

Stack e.g.
program:
stack = [5, 9, 3]
stack.append(7)
stack.append(11) OUTPUT
print(stack) [5, 9, 3, 7, 11]
print(stack.pop()) 11
print(stack) [5, 9, 3, 7]
print(stack.pop()) 7
print(stack) [5, 9, 3]
 Stack

Stack - Abstract Data Type

• Stack() creates a new, empty stack; no parameters and returns an
empty stack.
• push(item) adds a new item at top of stack; needs the item and
returns nothing.
• pop() removes top item; needs no parameters, returns item, stack is
modified
• peek() returns top item from the stack but doesn’t remove it; needs no
parameters, stack is not modified
• isEmpty() test if stack is empty; needs no parameters, returns a
boolean value
• size() returns number of items on stack; needs no parameters; returns
an integer

19
IMPORTANT TERMS:
• Stack UNDERFLOW happens when we try to pop (remove) an
item from the empty stack
• Stack OVERFLOW happens when we try to push (add) an
item to the fully filled stack (max position)
• PEEK: getting the most recent value of stack .i.e value at TOP
 STACK IMPLEMENTATION PROGRAM
def isempty(stk):
def peek(stk):
if stk==[]:
return True if isempty(stk):
else: return "Underflow"
return False else:
def push(stk,item): top=len(stk)-1
stk.append(item) return stk[top]
top=len(stk)-1
def display(stk):
def pop(stk):
if isempty(stk): if isempty(stk):
return "Underflow" return "Underflow"
else: else:
item=stk.pop() top=len(stk)-1
if len(stk)==0:
print(stk[top],"<--top"
top=None
else: )
top=len(stk)-1 for i in
return item range(top-1,-1,-1):
print(stk[i])
 STACK IMPLEMENTATION PROGRAM
stack=[]
top=None
while
True:
print("Stack operation")
elif choice==3:
print("1.Push") item=peek(stack)
print("2.Pop") if item=="Underflow":
print("3.Peek") print("Underflow! Stack is empty")
print("4.Display") else:
print("The top most item is\t",item)
print("5.Exit")
elif choice==4:
choice=int(input("Enter valid choice\t"))
display(stack)
if choice==1: elif choice==5:
item=int(input("Enter an item to push\t")) break
push(stack,item) else:
print("Invalid choice")
elif choice==2:
item=pop(stack)
if item=="Underflow":
print("Underflow!,Stack is empty")
else:
print("The popped item is",item)
 Stack
Implementing Stack using List in Python
#Program to implement Stack Operation on Single data
def push(stack,x): #function to add element at the end of list
stack.append(x)
def pop(stack): #function to remove last element from list
n = len(stack)
if(n<=0):
print("Stack empty....Pop not possible")
else:
stack.pop()
def display(stack): #function to display stack
entry
if len(stack)<=0:
print("Stack empty...........Nothing to display")
for i in stack:
print(i,end=" ")
25
 Stack
#main program starts from here
x=[]
choice=0
while (choice!=4):
print("********Stack Menu***********")
print("1. push(INSERT)")
print("2. pop(DELETE)")
print("3. Display ")
print("4. Exit")
choice = int(input("Enter your choice :"))
if(choice==1):
value = int(input("Enter value "))
push(x,value)
if(choice==2):
pop(x)
if(choice==3):
display(x)
if(choice==4):
11
print("You selected to close this program")
 Conclusion!

• We learned about:
▪ Linear data structures
▪ Type Linear data structures
• Stacks – PUSH, POP using a list (Single Data, Multiple Data)
▪ Implementation in Python

Thank you

19