Data structure: Stack | Computer Science for Class 12 - Humanities/Arts PDF Download

 Page 1


In this Chapter
 » Introduction
 » Stack
 » Operations on Stack
 » Implementation of Stack 
in Python
 » Notations for Arithmetic 
Expressions
 » Conversion From Infix To 
Postfix Notation
 » Evaluation of  Postfix 
Expression
Chapter
“We're going to be able to ask our 
computers to monitor things for us, and when 
certain conditions happen, are triggered, the 
computers will take certain actions and inform 
us after the fact.”
— Steve Jobs
3.1 INTRODUCTION
We have learnt about different data types in 
Python for handling values in Class XI. Recall 
that String, List, Set, Tuple, etc. are the sequence 
data types that can be used to represent collection 
of elements either of the same type or different 
types. Multiple data elements are grouped in a 
particular way for faster accessibility and efficient 
storage of data. That is why we have used different 
data types in python for storing data values. Such 
grouping is referred as a data structure.  
A data structure defines a mechanism to store, 
organise and access data along with operations 
(processing) that can be efficiently performed on 
the data. 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 structure in which each element 
may be of different types. We can apply different 
operations like reversal, slicing, counting of 
3 
Stack
Chpater-3.indd   39 18-Jun-21   2:30:02 PM
Page 2


In this Chapter
 » Introduction
 » Stack
 » Operations on Stack
 » Implementation of Stack 
in Python
 » Notations for Arithmetic 
Expressions
 » Conversion From Infix To 
Postfix Notation
 » Evaluation of  Postfix 
Expression
Chapter
“We're going to be able to ask our 
computers to monitor things for us, and when 
certain conditions happen, are triggered, the 
computers will take certain actions and inform 
us after the fact.”
— Steve Jobs
3.1 INTRODUCTION
We have learnt about different data types in 
Python for handling values in Class XI. Recall 
that String, List, Set, Tuple, etc. are the sequence 
data types that can be used to represent collection 
of elements either of the same type or different 
types. Multiple data elements are grouped in a 
particular way for faster accessibility and efficient 
storage of data. That is why we have used different 
data types in python for storing data values. Such 
grouping is referred as a data structure.  
A data structure defines a mechanism to store, 
organise and access data along with operations 
(processing) that can be efficiently performed on 
the data. 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 structure in which each element 
may be of different types. We can apply different 
operations like reversal, slicing, counting of 
3 
Stack
Chpater-3.indd   39 18-Jun-21   2:30:02 PM
STACK
Other important 
data structures 
in Computer 
Science include 
Array, Linked 
List, Binary Trees, 
Heaps, Graph, 
Sparse Matrix, 
etc.
A data structure 
in which elements 
are organised 
in a sequence is 
called linear data 
structure.
elements, etc. on list and string. Hence, a data structure 
organises multiple elements in a way so that certain 
operations on each element as well as the collective 
data unit could be performed easily. 
Stack and Queue are two other popular data 
structures used in programming. Although not directly 
available in Python, it is important to learn these 
concepts as they are extensively used in a number of 
programming languages. In this chapter, we will study 
about stack, its implementation using Python as well as 
its applications.
3.2 STACK
We have seen piles of books in the library or stack of 
plates at home (Figure 3.1). To put another book or 
another plate in such a pile, we always place (add to 
the pile) the object at the top only. Likewise, to remove 
a book or a plate from such a pile, we always remove 
(delete from the pile) the object from the top only. This 
is because in a large pile, it is inconvenient to add or 
remove an object from in between or bottom. Such an 
arrangement of elements in a linear order is called a 
stack. We add new elements or remove existing elements 
from the same end, commonly referred to as the top of 
the stack. It thus follows the Last-In-First-out (LIFO) 
principle. That is, the element which was inserted last 
(the most recent element) will be the first one to be taken 
out from the stack.
                                                      
Figure 3.1: Stack of plates and books
Chpater-3.indd   40 18-Jun-21   2:30:02 PM
Page 3


In this Chapter
 » Introduction
 » Stack
 » Operations on Stack
 » Implementation of Stack 
in Python
 » Notations for Arithmetic 
Expressions
 » Conversion From Infix To 
Postfix Notation
 » Evaluation of  Postfix 
Expression
Chapter
“We're going to be able to ask our 
computers to monitor things for us, and when 
certain conditions happen, are triggered, the 
computers will take certain actions and inform 
us after the fact.”
— Steve Jobs
3.1 INTRODUCTION
We have learnt about different data types in 
Python for handling values in Class XI. Recall 
that String, List, Set, Tuple, etc. are the sequence 
data types that can be used to represent collection 
of elements either of the same type or different 
types. Multiple data elements are grouped in a 
particular way for faster accessibility and efficient 
storage of data. That is why we have used different 
data types in python for storing data values. Such 
grouping is referred as a data structure.  
A data structure defines a mechanism to store, 
organise and access data along with operations 
(processing) that can be efficiently performed on 
the data. 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 structure in which each element 
may be of different types. We can apply different 
operations like reversal, slicing, counting of 
3 
Stack
Chpater-3.indd   39 18-Jun-21   2:30:02 PM
STACK
Other important 
data structures 
in Computer 
Science include 
Array, Linked 
List, Binary Trees, 
Heaps, Graph, 
Sparse Matrix, 
etc.
A data structure 
in which elements 
are organised 
in a sequence is 
called linear data 
structure.
elements, etc. on list and string. Hence, a data structure 
organises multiple elements in a way so that certain 
operations on each element as well as the collective 
data unit could be performed easily. 
Stack and Queue are two other popular data 
structures used in programming. Although not directly 
available in Python, it is important to learn these 
concepts as they are extensively used in a number of 
programming languages. In this chapter, we will study 
about stack, its implementation using Python as well as 
its applications.
3.2 STACK
We have seen piles of books in the library or stack of 
plates at home (Figure 3.1). To put another book or 
another plate in such a pile, we always place (add to 
the pile) the object at the top only. Likewise, to remove 
a book or a plate from such a pile, we always remove 
(delete from the pile) the object from the top only. This 
is because in a large pile, it is inconvenient to add or 
remove an object from in between or bottom. Such an 
arrangement of elements in a linear order is called a 
stack. We add new elements or remove existing elements 
from the same end, commonly referred to as the top of 
the stack. It thus follows the Last-In-First-out (LIFO) 
principle. That is, the element which was inserted last 
(the most recent element) will be the first one to be taken 
out from the stack.
                                                      
Figure 3.1: Stack of plates and books
Chpater-3.indd   40 18-Jun-21   2:30:02 PM
COMPUTER SCIENCE - CLASS XII
 
 
How does a compiler 
or an interpreter 
handle function calls 
in a program?
The operating 
system in computer 
or mobile allocates 
memory to different 
applications for 
their execution. How 
does an operating 
system keep track 
of the free memory 
that can be allocated 
among programs/
applications to be 
executed?
3.2.1  APPLICATIONS OF STACK
Some of the applications of stack in real-life are:
• Pile of clothes in an almirah
• Multiple chairs in a vertical pile
• Bangles worn on wrist 
• Pile of boxes of eatables in pantry or on a kitchen 
shelf
Some examples of application of stack in programming 
are as follows:
• When we need to reverse a string, the string is 
traversed from the last character till the first 
character. i.e. characters are traversed in the reverse 
order of their appearance in the string. This is very 
easily done by putting the characters of a string in 
a stack.
• We use text/image editor for editing the text/image 
where we have options to redo/undo the editing 
done. When we click on the redo /undo icon, the 
most recent editing is redone/undone. In this 
scenario, the system uses a stack to keep track of  
changes made. 
• While browsing the web, we move from one web page 
to another by accessing links between them. In order 
to go back to the last visited web page, we may use the 
back button on the browser. Let us say we accessed 
a web page P1 from where we moved to web page P2 
followed by browsing of web page P3. Currently, we 
are on web page P3 and want to revisit web page P1. 
We may go to a previously visited web page by using 
the BACK button of the browser.  On clicking the 
BACK button once, we are taken from web page P3 
to web page P2, another click on BACK shows web 
page P1. In this case, the history of browsed pages is 
maintained as stack.
• While writing any arithmetic expression in a program, 
we may use parentheses to order the evaluation 
of operators. While executing the program, the 
compiler checks for matched parentheses i.e. each 
opening parenthesis should have a corresponding 
closing parenthesis and the pairs of parentheses 
are properly nested. In case of parentheses are 
Chpater-3.indd   41 18-Jun-21   2:30:02 PM
Page 4


In this Chapter
 » Introduction
 » Stack
 » Operations on Stack
 » Implementation of Stack 
in Python
 » Notations for Arithmetic 
Expressions
 » Conversion From Infix To 
Postfix Notation
 » Evaluation of  Postfix 
Expression
Chapter
“We're going to be able to ask our 
computers to monitor things for us, and when 
certain conditions happen, are triggered, the 
computers will take certain actions and inform 
us after the fact.”
— Steve Jobs
3.1 INTRODUCTION
We have learnt about different data types in 
Python for handling values in Class XI. Recall 
that String, List, Set, Tuple, etc. are the sequence 
data types that can be used to represent collection 
of elements either of the same type or different 
types. Multiple data elements are grouped in a 
particular way for faster accessibility and efficient 
storage of data. That is why we have used different 
data types in python for storing data values. Such 
grouping is referred as a data structure.  
A data structure defines a mechanism to store, 
organise and access data along with operations 
(processing) that can be efficiently performed on 
the data. 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 structure in which each element 
may be of different types. We can apply different 
operations like reversal, slicing, counting of 
3 
Stack
Chpater-3.indd   39 18-Jun-21   2:30:02 PM
STACK
Other important 
data structures 
in Computer 
Science include 
Array, Linked 
List, Binary Trees, 
Heaps, Graph, 
Sparse Matrix, 
etc.
A data structure 
in which elements 
are organised 
in a sequence is 
called linear data 
structure.
elements, etc. on list and string. Hence, a data structure 
organises multiple elements in a way so that certain 
operations on each element as well as the collective 
data unit could be performed easily. 
Stack and Queue are two other popular data 
structures used in programming. Although not directly 
available in Python, it is important to learn these 
concepts as they are extensively used in a number of 
programming languages. In this chapter, we will study 
about stack, its implementation using Python as well as 
its applications.
3.2 STACK
We have seen piles of books in the library or stack of 
plates at home (Figure 3.1). To put another book or 
another plate in such a pile, we always place (add to 
the pile) the object at the top only. Likewise, to remove 
a book or a plate from such a pile, we always remove 
(delete from the pile) the object from the top only. This 
is because in a large pile, it is inconvenient to add or 
remove an object from in between or bottom. Such an 
arrangement of elements in a linear order is called a 
stack. We add new elements or remove existing elements 
from the same end, commonly referred to as the top of 
the stack. It thus follows the Last-In-First-out (LIFO) 
principle. That is, the element which was inserted last 
(the most recent element) will be the first one to be taken 
out from the stack.
                                                      
Figure 3.1: Stack of plates and books
Chpater-3.indd   40 18-Jun-21   2:30:02 PM
COMPUTER SCIENCE - CLASS XII
 
 
How does a compiler 
or an interpreter 
handle function calls 
in a program?
The operating 
system in computer 
or mobile allocates 
memory to different 
applications for 
their execution. How 
does an operating 
system keep track 
of the free memory 
that can be allocated 
among programs/
applications to be 
executed?
3.2.1  APPLICATIONS OF STACK
Some of the applications of stack in real-life are:
• Pile of clothes in an almirah
• Multiple chairs in a vertical pile
• Bangles worn on wrist 
• Pile of boxes of eatables in pantry or on a kitchen 
shelf
Some examples of application of stack in programming 
are as follows:
• When we need to reverse a string, the string is 
traversed from the last character till the first 
character. i.e. characters are traversed in the reverse 
order of their appearance in the string. This is very 
easily done by putting the characters of a string in 
a stack.
• We use text/image editor for editing the text/image 
where we have options to redo/undo the editing 
done. When we click on the redo /undo icon, the 
most recent editing is redone/undone. In this 
scenario, the system uses a stack to keep track of  
changes made. 
• While browsing the web, we move from one web page 
to another by accessing links between them. In order 
to go back to the last visited web page, we may use the 
back button on the browser. Let us say we accessed 
a web page P1 from where we moved to web page P2 
followed by browsing of web page P3. Currently, we 
are on web page P3 and want to revisit web page P1. 
We may go to a previously visited web page by using 
the BACK button of the browser.  On clicking the 
BACK button once, we are taken from web page P3 
to web page P2, another click on BACK shows web 
page P1. In this case, the history of browsed pages is 
maintained as stack.
• While writing any arithmetic expression in a program, 
we may use parentheses to order the evaluation 
of operators. While executing the program, the 
compiler checks for matched parentheses i.e. each 
opening parenthesis should have a corresponding 
closing parenthesis and the pairs of parentheses 
are properly nested. In case of parentheses are 
Chpater-3.indd   41 18-Jun-21   2:30:02 PM
STACK
mismatched, the compiler needs to throw an error. 
To handle matching of parentheses, stack is used.
3.3 OPERATIONS ON STACK
As explained in the previous section, a stack is a 
mechanism that implements LIFO arrangement hence 
elements are added and deleted from the stack at one 
end only. The end from which elements are added or 
deleted is called TOP of the stack. Two fundamental 
operations performed on the stack are PUSH and POP. 
In this section, we will learn about them and implement 
them using Python.
3.3.1 PUSH and POP Operations   
• PUSH adds a new element at the TOP of the stack. 
It is an insertion operation. We can add elements 
to a stack until it is full. A stack is full when no 
more elements can be added to it. Trying to add an 
element to a full stack results in an exception called 
‘overflow’. 
• POP operation is used to remove the top most element 
of the stack, that is, the element at the TOP of the 
stack. It is a delete operation. We can delete elements 
from a stack until it is empty i.e. there is no element 
in it. Trying to delete an element from an empty stack 
results in an exception called ‘underflow’.
A stack is used 
to insert and delete 
elements in LIFO 
order. Same principle 
is followed in adding 
and removing glasses 
from a pile of glasses.  
Let us create a stack of 
glasses assuming that 
each glass is numbered. 
Visual representations 
of PUSH and POP 
operations on a stack 
of glasses are shown in 
Figure 3.2.
(i) Empty 
    Stack
(ii) Push 1 (iii) Push 2 (iv) Pop (v) Push 3
1 1 1
3
(x) Empty 
    Stack
(vi) Push 4 (vii) Pop
1
3
4
(viii) Pop
1 1
3
1
2
Top
Top
Top
Top
Top
Top
Top
(2 will be 
removed)
(4 will be 
removed)
(3 will be 
removed)
(ix) Pop
(1 will be 
removed)
Figure 3.2: PUSH and POP operations on the stack of glasses
Chpater-3.indd   42 18-Jun-21   2:30:03 PM
Page 5


In this Chapter
 » Introduction
 » Stack
 » Operations on Stack
 » Implementation of Stack 
in Python
 » Notations for Arithmetic 
Expressions
 » Conversion From Infix To 
Postfix Notation
 » Evaluation of  Postfix 
Expression
Chapter
“We're going to be able to ask our 
computers to monitor things for us, and when 
certain conditions happen, are triggered, the 
computers will take certain actions and inform 
us after the fact.”
— Steve Jobs
3.1 INTRODUCTION
We have learnt about different data types in 
Python for handling values in Class XI. Recall 
that String, List, Set, Tuple, etc. are the sequence 
data types that can be used to represent collection 
of elements either of the same type or different 
types. Multiple data elements are grouped in a 
particular way for faster accessibility and efficient 
storage of data. That is why we have used different 
data types in python for storing data values. Such 
grouping is referred as a data structure.  
A data structure defines a mechanism to store, 
organise and access data along with operations 
(processing) that can be efficiently performed on 
the data. 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 structure in which each element 
may be of different types. We can apply different 
operations like reversal, slicing, counting of 
3 
Stack
Chpater-3.indd   39 18-Jun-21   2:30:02 PM
STACK
Other important 
data structures 
in Computer 
Science include 
Array, Linked 
List, Binary Trees, 
Heaps, Graph, 
Sparse Matrix, 
etc.
A data structure 
in which elements 
are organised 
in a sequence is 
called linear data 
structure.
elements, etc. on list and string. Hence, a data structure 
organises multiple elements in a way so that certain 
operations on each element as well as the collective 
data unit could be performed easily. 
Stack and Queue are two other popular data 
structures used in programming. Although not directly 
available in Python, it is important to learn these 
concepts as they are extensively used in a number of 
programming languages. In this chapter, we will study 
about stack, its implementation using Python as well as 
its applications.
3.2 STACK
We have seen piles of books in the library or stack of 
plates at home (Figure 3.1). To put another book or 
another plate in such a pile, we always place (add to 
the pile) the object at the top only. Likewise, to remove 
a book or a plate from such a pile, we always remove 
(delete from the pile) the object from the top only. This 
is because in a large pile, it is inconvenient to add or 
remove an object from in between or bottom. Such an 
arrangement of elements in a linear order is called a 
stack. We add new elements or remove existing elements 
from the same end, commonly referred to as the top of 
the stack. It thus follows the Last-In-First-out (LIFO) 
principle. That is, the element which was inserted last 
(the most recent element) will be the first one to be taken 
out from the stack.
                                                      
Figure 3.1: Stack of plates and books
Chpater-3.indd   40 18-Jun-21   2:30:02 PM
COMPUTER SCIENCE - CLASS XII
 
 
How does a compiler 
or an interpreter 
handle function calls 
in a program?
The operating 
system in computer 
or mobile allocates 
memory to different 
applications for 
their execution. How 
does an operating 
system keep track 
of the free memory 
that can be allocated 
among programs/
applications to be 
executed?
3.2.1  APPLICATIONS OF STACK
Some of the applications of stack in real-life are:
• Pile of clothes in an almirah
• Multiple chairs in a vertical pile
• Bangles worn on wrist 
• Pile of boxes of eatables in pantry or on a kitchen 
shelf
Some examples of application of stack in programming 
are as follows:
• When we need to reverse a string, the string is 
traversed from the last character till the first 
character. i.e. characters are traversed in the reverse 
order of their appearance in the string. This is very 
easily done by putting the characters of a string in 
a stack.
• We use text/image editor for editing the text/image 
where we have options to redo/undo the editing 
done. When we click on the redo /undo icon, the 
most recent editing is redone/undone. In this 
scenario, the system uses a stack to keep track of  
changes made. 
• While browsing the web, we move from one web page 
to another by accessing links between them. In order 
to go back to the last visited web page, we may use the 
back button on the browser. Let us say we accessed 
a web page P1 from where we moved to web page P2 
followed by browsing of web page P3. Currently, we 
are on web page P3 and want to revisit web page P1. 
We may go to a previously visited web page by using 
the BACK button of the browser.  On clicking the 
BACK button once, we are taken from web page P3 
to web page P2, another click on BACK shows web 
page P1. In this case, the history of browsed pages is 
maintained as stack.
• While writing any arithmetic expression in a program, 
we may use parentheses to order the evaluation 
of operators. While executing the program, the 
compiler checks for matched parentheses i.e. each 
opening parenthesis should have a corresponding 
closing parenthesis and the pairs of parentheses 
are properly nested. In case of parentheses are 
Chpater-3.indd   41 18-Jun-21   2:30:02 PM
STACK
mismatched, the compiler needs to throw an error. 
To handle matching of parentheses, stack is used.
3.3 OPERATIONS ON STACK
As explained in the previous section, a stack is a 
mechanism that implements LIFO arrangement hence 
elements are added and deleted from the stack at one 
end only. The end from which elements are added or 
deleted is called TOP of the stack. Two fundamental 
operations performed on the stack are PUSH and POP. 
In this section, we will learn about them and implement 
them using Python.
3.3.1 PUSH and POP Operations   
• PUSH adds a new element at the TOP of the stack. 
It is an insertion operation. We can add elements 
to a stack until it is full. A stack is full when no 
more elements can be added to it. Trying to add an 
element to a full stack results in an exception called 
‘overflow’. 
• POP operation is used to remove the top most element 
of the stack, that is, the element at the TOP of the 
stack. It is a delete operation. We can delete elements 
from a stack until it is empty i.e. there is no element 
in it. Trying to delete an element from an empty stack 
results in an exception called ‘underflow’.
A stack is used 
to insert and delete 
elements in LIFO 
order. Same principle 
is followed in adding 
and removing glasses 
from a pile of glasses.  
Let us create a stack of 
glasses assuming that 
each glass is numbered. 
Visual representations 
of PUSH and POP 
operations on a stack 
of glasses are shown in 
Figure 3.2.
(i) Empty 
    Stack
(ii) Push 1 (iii) Push 2 (iv) Pop (v) Push 3
1 1 1
3
(x) Empty 
    Stack
(vi) Push 4 (vii) Pop
1
3
4
(viii) Pop
1 1
3
1
2
Top
Top
Top
Top
Top
Top
Top
(2 will be 
removed)
(4 will be 
removed)
(3 will be 
removed)
(ix) Pop
(1 will be 
removed)
Figure 3.2: PUSH and POP operations on the stack of glasses
Chpater-3.indd   42 18-Jun-21   2:30:03 PM
COMPUTER SCIENCE - CLASS XII
3.4 IMPLEMENTATION OF STACK IN PYTHON 
We have learnt so far that a stack is a linear and ordered 
collection of elements. The simple way to implement a 
stack in Python is using the data type list.  We can fix 
either of the sides of the list as TOP to insert/remove 
elements. It is to be noted that we are using  built-in 
methods append() and pop() of the list for implementation 
of the stack. As these built-in methods insert/delete 
elements at the rightmost end of the list, hence explicit 
declaration of TOP is not needed.  
Let us write a program to create a STACK (stack of 
glasses as given in Figure 3.2) in which we will:
• insert/delete elements (glasses) 
• check if the  STACK is empty (no glasses in the stack) 
• find the  number of elements (glasses) in the STACK 
• read the value of the topmost element (number on 
the topmost glass) in the STACK 
The program shall define the following functions to 
perform these operations:
• Let us create an empty stack named glassStack. 
We will do so by assigning an empty list to the 
identifier named glassStack :
glassStack = list()
• A function named isEmpty to check whether the 
stack glassStack is empty or not. Remember trying 
to remove an element from an empty stack would 
result in ‘underflow’. This function returns True if 
the stack is empty, else returns False.
def isEmpty(glassStack):
    if len(glassStack)==0:
        return True
    else:
        return False
• A function named opPush to insert (PUSH) a new 
element in stack. This function has two parameters 
- the name of the stack in which the element is to be 
inserted (glassStack) and the element that needs 
to be inserted. We know that insertion of an element 
is always done at the TOP of the stack. Hence, we 
NOTES
Chpater-3.indd   43 18-Jun-21   2:30:03 PM