Unit i: Computational Thinking
ramming -2 Visit to website: learnpythondcbse.com
Chapter-10 Data Structure - II
Stack and Queue
1 Stack
2 Example: Implementing Stack In Python
3 Queue
4 Example: Implementation of Queue
Page ofVisit to webs
O Data Structure - II
Linear data structures are collections of components arranged in a
straight line
> Astack is a data structure that keeps objects in Last-In-First-Out (LIFO)
order ees oe
> Objects are added to the top
of the stack
> Only the top of the stack can
Push a new Pop a book
be accessed hod ‘book on top rnp
Asta of
ack
> Apile of books or a stack of (inaccessible) four books
dinner plates can be thought of examples of stacks.
It has three primitive operations:
e Push: Add an element to the stack
* Pop: Remove an element from the stack
© Peek: Get the topmost element of the stack
In Python, a stack is implemented using a list object.
© To push an item in the stack, use the list
function append list.append{(item)
© To pop an item in the stack, use the list function pop list.pop()
To get the top most item in the stack, write list{-1]
Page 20f9Uni
‘omputational Thinking and Programming -2
File Est Formet Run Options Window Help
# Created By: learnpython4cbse.com B
# Stack using List
# Function to check Stack is empty or not
def isEmpty (Lst)
if len(Lst)
return 1
else:
return 0
# Function to add (PUSH) elements in Stack
def Push_Stack(Lst,val):
Lst append (val)
top=len (Lst) -1
# Function to Delete (POP) elements in Stack
def Pop_Stack(Lst):
if isempty (Lst) :
return "UnderFlow"
else:
ele=Lst.pop()
if len(Lst)
top=None
else:
top=len (Lst)-1
return ele
# Function to Display Top element of Stack
def Peek _Stack(Lst):
if iszmpty (ist):
return "UnderFlow"
else:
top=len (Lst)-1
return Lst[top]
Ln37 Cok 23
Page 3.0f9
‘Visit to website: learnpythondcbse.com
Chapter-10 Data Structure - IIUnit I: Computational Thinking and! Visit to website: learnpythondcbse.com
gramming -2
Chapter-10 Data Structure - II
[Sk yD
Fie Eat Format fun Opbons_vindow “Help
# Function to Display elements of Stack F|
cf Display_Stack(Lst)
ip isBapty (ist)
print ("No Item to Display.....")
else:
fen (Lst) -1
print (" (TOP) ", en
wails tp=0:
print (ist (tpl, "<-',end=" ")
tp -=1
print Q)
»
# Driver function
Jost main():
List
Top
while Truet
print)
print ("##### STACK OPERATIONS #####")
print ("1. PUSH- Insertion")
print ("2. POP- Deletion")
print ("3. PEEK- Show Top Element") .
print ("4. DISPLAY - Show Stack")
print ("0. EXIT")
choice=int (input ("Enter Your Choic:
if choice==1:
Element=int (input ("Enter El
Push_Stack (List, Element)
elif choice==2:
Element=Pop_stack (List) +
if Element=="UnderFlow":
print ("stack is Empty")
else:
print ("Deleted Element was
" Element)
elif choice==3:
Element=Peek_stack (bist)
Lf Blement=="UnderFlow":
print ("stack is Empty")
else:
print ("Top Element : ",Element)
e1if choice:
Display_stack (List)
elif choice:
print ("Good Luck.
break
main () |
”
Page dofUnit I: Computational Thinking and Programming -2
‘Visit to website: learnpythondcbse.com
Chapter-10 Data Structure - II
OUTPUT
‘itt STACK OPERATIONS ###t
1. PUSH- Insertion
2. POP- Deletion
3. PEEK- Show Top Element
4, DISPLAY - Show Stack
0. EXIT
Enter Your Choice: 1
Enter Element to Push: 20
‘uit STACK OPERATIONS sits
1. PUSH- Insertion
2. POP- Deletion
3. PEEK- Show Top Element
4, DISPLAY - Show Stack
0. EXIT
Enter Your Choice: 1
Enter Element to Push: 30
‘itt STACK OPERATIONS ##s#t
1. PUSH- Insertion
2. POP- Deletion
3. PEEK- Show Top Element
4. DISPLAY - Show Stack
0. EXIT
Enter Your Choice: 1
Enter Element to Push: 88
‘Hitt STACK OPERATIONS itis
1. PUSH- Insertion
2. POP- Deletion
3, PEEK- Show Top Element
4, DISPLAY - Show Stack
0. EXIT
Enter Your Choice: 4
[TOP] 88 <- 30 <- 20 <-
‘aititttt STACK OPERATIONS ###it
1. PUSH- Insertion
2. POP- Deletion
3. PEEK- Show Top Element
4, DISPLAY - Show Stack
0. EXIT
Enter Your Choice: 3
Top Element: 88
‘uit STACK OPERATIONS sits
1. PUSH- Insertion
2. POP- Deletion
3. PEEK- Show Top Element
4, DISPLAY - Show Stack
0. EXIT
Enter Your Choice: 2
Deleted Element was: 88
‘uit STACK OPERATIONS sits
1. PUSH- Insertion
2. POP- Deletion
3, PEEK- Show Top Element
4, DISPLAY - Show Stack
0. EXIT
Enter Your Choice: 4
[TOP] 30 <- 20 <-
itt STACK OPERATIONS ####t
1. PUSH- Insertion
2. POP- Deletion
3. PEEK- Show Top Element
4, DISPLAY - Show Stack
0. EXIT
Enter Your Choice: 0
GoOd Lucksrvsree
Page Sof 9Queues are data structures that follow the First In First Out (FIFO) i.e. the
first element that is added to the queue is the first one to be removed.
> Waiting in line
Real life examples v of queue
> Waiting on hold for tech we )
support ) ) ) )
> Applications related to New element is
added to the rear
Computer Science of the queue
> Round robin scheduling
> Key board buffer
QUEUE OPERATIONS:
> Peek : getting first value of QUEUE i.e. of FRONT position.
Queue[Front] _ # Front is an int storing index of first element of queue
> Enqueue: addition of new item in QUEUE at REAR position.
e.g. Queue. append(Item)
> Dequeue: removal of item from the beginning of QUEUE.
e.g. Queue.pop(0)
Page 6 of 9Uni
‘omputational Thinking and Programming -2 Visit to website: learnpythondcbse.com
Chapter-10 Data Structure - II
File Edit Format Run Options Window Help
\|I# Created By: learnpython4cbse.com I
|| # Queue using List
# Function to check Queue is empty or not
def isEmpty (qLst):
if len(qLst
return 1
else:
return 0
# Function to add elements in Queue
def Enqueue (qLst, val):
qist . append (val)
if len(qLst!
front=rea:
else:
rear=len (qLst)-1
# Function to Delete elements in Queue
def Dqueue (qLst) :
if isempty(qust) :
return "UnderFlow"
else: |
val = qhst.pop(0)
y if len (qust)= j
front=rear=None
return val
# Function to Display top element of Queue
def Peek(qLst) :
if isempty(qLst) :
return "UnderFlow"
else:
front=0
return qLst [front]
Und Cobo
Page 7 of 9Unit I: Computational Thinking and! Visit to website: learnpythondcbse.com
Chapter-10 Data Structure - II
(se Ques - Dvn Sm
Fie Eat Fomat fon Opens Window Hep
¥ Function to Display elements of queue -
dof Display (gist):
| if isimpty(qhst) +
print ("No Ttem to Dispay in Queue.
els:
tp = len(qust)-1
print (* [FRONT:
front = 0
i = front
rear = len(qhst)-1
while (i