Stack 1 Introduction What is data structure? th operations at data along Wil ns: A data structui = re de lefines a mechanism to store, organize and access can be efficiently performed on the data ‘ere each element 16 a For example, stri xample, string is a data z lata structure contai e f elements whe Benn ale list ia ining a sequence of eleme e d also list is a sequence data structure in which each element mY be of different HPS We can perfor perform different operations like several, s ng, counting of element et Stack and Queue are two popular data structure used in programming .2 Stack What is stack? ™ = geese en ‘ns: Stack is a linear data structure, where insertion and deletion of an element takes place aaa commonly referred to as the top of the stack. ast will be ‘The stack follows the last-in-first-out principle where the element which was inserted I the first one to be taken out from stack. 3.2.1 Applications of stack ns of stack? What are real-life applica in an almirah Ans: a) Pile of clothes b) Multiple chairs in a vertical pile ) Bangles worn on wrist ables in pantry or on a kitchen shelf d) _ Pile of boxes of eats ¢) Plates arranged one above the other programming it is traversed from the done by placing the characters in a stack 4. List application of stack in st character to the first, reversing their To reverse a string, Ans: a) the string, which can be appearance in b) The text/image editor ‘allows user to redo/undo editing, with the most recent editing being ndone using 4 st ‘web, we move from one web page to another by accessing links between redone/un tack to track changes made. While browsing the In order to go bacl the history of browsed pages is maintained as stack °) them. 1 to the last visited web page, we may use the back button on the browser. [Link] ca aluation 4) _ Expression evi II PU Computer Science ‘Student's illuminator}on stack 2 ‘Two fimdamental operation performed on the stack they a) PUSH operation b) POP operation 6. Explain PUSH and POP operations a PUSH operation is also called as insertion operation. b) PUSH adds a new element at the TOP of the stack. ©) Wecan add elements to a stack until it is full. @) When stack is full no more element can be added to it. ©) Trying to add an element to a full stack results in an exception called ‘ov POP operations a) POP operation is also called deletion operation. b) POP delete the existing element from the TOP of the stack. ©) We can delete an element from a stack until it becomes empty. d) When stack is empty no more deletion can be done. ©) Trying to delete an element from an empty stack results in an exception called um POP operations on the stack of gi lassesCheck if the STACK is empty (no glasses in the stack) ‘ Find the number of elements (glasses) in the STACK, ‘ re ») Read the value ofthe topmost element (number on the topmost glass) in the STACK. “Te program shall define the following functions to perform these operations. “ ) Ter us ereate an empty stack named glassStack. We will do so by assigning an empty list ‘the a : ee identifier named glassStack: glassStack = list Q) : z ‘A function named is Empty 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 funetion 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 shall use the built-in method append() of list to add an element to the stack that always adds at the ‘end of the list. As there is no limit on the size of list in Python, the implemented stack will never be full unless there is no more space available in memory. Hence, we will never face ‘overflow’ (no space for new element) condition for stack. [def opPush(glassStack,element): [Link](element) 4) A function named size to read the number of elements in the glassStack. We will use the len() function of list in Python to find the number of elements in the glassStack, det (glassStack): return len(glassStack)if isEmpty(glassStack): print('Stack is empty’) return None else: x =len(glassStack) element=glassStack[x-1] retum element def opPop(elassStack): if isEmpty(glassStack): print(underflow’) return None. else: return([Link]() 2) _ A function named display to show the contents of the stack. def display(glassStack): x-len(glassStack) print(”Current elements in the stack are: ") for i in range(x-1,-1,-1): print(glassStack{i)) ‘Student's illuminator Python code to implement a stack of glasses. slassStack = list() # create empty stack add elements to stack element='glass1’ print("Pushing element " element) opPush(glassStack,element) element='glass2! Print("Pushing element ",element) ‘opPush(glassStack,element) #display number of elements in stack print("Current number of elements in stack ‘A function named top to read the most recent element (TOP) in the glassStack. def top(glassStack): ‘A function named opPop to delete the topmost element from the stack. It takes one parameter - name of the stack (glassStack) from which element is to be deleted and returns the value of the element. The function first checks whether the stack is empty or not. If it is not empty, it removes ty topmost element from it. We shall use the built- in method pop() of Python list that removes ‘element from the end of the list.‘#display the last element added to the stack print("top element is",top(glassStack)) ‘#display all elements in the stack display(glassStack) ‘#delete all elements from stack while True: item=opPop(glassStack) if item == None: print("Stack is émpty now") break else: print("Popped element is" item) ‘The output of the above program will be as follows: Pushing element glass] Pushing element glass? Current number of elements in stack is 2 Popped element is glass2 Pushing element glass3 top element is glass3 Current elements in the stack are: glass3 : glass! Popped element is glass3 Popped element is glass] Underflow Stack is empty now ‘Student's ituminator3.6 Co! infix expression. * different types of arithmetic expressions. Infix expression: tors are placed in between the 4 sle: 2+ X¥ oe expression: It is also known as polish notation. “The operators are placed before the corresponding operands are called ish notation. " Example: +xY + It is also known as reverse poli ced after the corresponding operands are called e operands are called i prefix expression. postfix expression. pe of Expression Description Operators are placed in yperands x*ytz 3.*(4+5) | tye") between the 0) ee Prefix Operators ‘are placed +2*xy before the corresponding ws | pexy*25_ operands (Polish) placed ding Operators are after the comespo” Postfix(Revers® Polish) operands notation kc data structure- Scar nd if we get an n the infix & ostfix expression. using the stac’ d, add it to the postfix expression SN vert infix expression to pi ict we oot aD: operan operator OFTHEN POP the elements from the Stack and append to string. oe postExp until the corresponding left parenthesis is popped ec while discarding both left and right parentheses cay a ELSE IF character is an operator THEN IF its precedence is lower than that of operator at the top of Stack ee THEN POP elements from the Stack till an ‘operator with precedence less than the current = + ‘operator is encountered and append to string postExp before pushing this operator on the postStack ELSE PUSH operator on the Stack ELSE Append the character to postExp Step 5: Pop elements from the Stack and append to postExp until Stack is empty ‘Step 6: OUTPUT postExp 14, Convert a given infix expression (x+y)/(2*8) into equivalent postfix expression using a stack. Ans: Let us now use this algorithm to convert a given infix expression (x + y)/(z*8) into equivalent postfix expression using a stack. Note here that stack is used to track the operators and parentheses, and a string variable contains the equivalent postfix expression. Initially both are empty. Each character in the given infix expression is processed from left to right and the appropriate action is taken as detailed in the algorithm. When each character in the given infix expression has been processed, the string will contain the ‘equivalent postfix expression. es aes wma oe pe el aad J —j7> RNa Ed a : ee s : = eoxytz8*/ xyte8 xytee* Conversion of infix expression (x+y)/(z*8) to postfix notation 1S. Write an algorithm for evaluation of postfix expression Ans: Evaluation of postfix expression ‘Step 1: INPUT postfix expression in a variable, say postExp ‘Step 2: For each character in postExp, REPEAT Step 3 Step 3: IF character is an operand THEN PUSH character on the Stack ELSE POP two elements from the Stack, apply the operator on the popped elements and the computed value onto the Stack Step 4: IF Stack has a single element THEN POP the element and OUTPUT as the net result ELSE OUTPUT “Invaild Postfix expression” fent's illuminator 1 PU Computer:Evaluation of postix expression 7 82° 4+ Multiple Choice Questions (MCQs) 1. Whatis a Stack in data structures? a) A type of queue ) A linear data structure that follows LIFO (Last In, First Out) principle ©) Anon-linear data structure @) A data structure that follows FIFO (First In, First Out) principle 2, Whats the process of adding an element to a stack called? a) Enqueue b) Pop ©) Push d) Insert 3. What is the process of removing an element from a stack called? a) Delete b) Pop ©) Dequeue d) Remove 4, Which of the following operations cause stack overflow? a) Trying to pop from an empty stack b) Trying to push into a full stack ©) Trying to access an element from an empty stack ) Performing push and pop operations alternately S$. Which function is used to check if a stack is empty? a) isFull) b) isEmpty() ©) top d) peek() Students iluminator IW PU Computer Science‘Operations in a text editor b) Function calls in recursion — © Backtracking algorithms (e.g., maze-solving) d) All of the above ‘What does the peek() function do in a stack? a) Removes the top element of the stack b) Returns the top element without = ©) Checks if the stack is full 4) Checks if the stack is empty 10. What is the maximum number of elements that can be stored in a stack of size N? a) N-I b) N ©) N+ @) Infinite 11. In which order are elements accessed ina stack? a) First In First Out (FIFO) ) Last In First Out (LIFO) ©) Random Order 4) "First Come First Serve 12. What is the output of the following sequence of stack operations? Push(1), push(2), push(3), pop(), push(4), PopQ) a) 124 b) 123 Di 12 d) 14 13. What is the condition for stack underflow? 8) Stack is empty, and pop() is called b) Stack is full, and push() is called : ©) Stack contains only one element 4) Stack is half full 14. Which of the following data structures is best suited for implementing recursion? a) Queue b) Stack ©) Array d) Linked List 15. Which of the following applications use stacks? a) Depth-First Search (DFS) in Graphs ») Parentheses Matching in Expressions : ©) Reversing a String d) All of the above 3 16. If elements are pushed onto a stack in this order: A, B, C, D, and then Popped, in which order will be removed? a) ABCD b) DCBA c) ADBC d) CBAD 7. How is a stack represented in memory using an array? a) Using a single pointer b) Using two pointers ©) Using a single variable (top) that stores the index of the topmost element @) Using a dynamic list dent's illuminator‘the following operations is NOT possible in a stack? at the bottom b) Delete from the top at the top d) Peek at the top element d list implementation of a stack, where is the new node inserted? “Atthe end of the linked list b) At the beginning of the linked list ¢) Inthe middle of the linked list d) Randomly in the list _ Assertion (A): A stack follows the Last In First Out (LIFO) principle. ‘Reason (R): In a stack, elements are added and removed from the same end, called the top. a) Both A and R are true, and R is the correct explanation of A. _ Both A and R are true, but R is not the correct explanation of A. Ais true, but R is false. Ais false, but R is true. Answer Keys | A See See ae eco oe b b a c d b b 14 | 15 | 16 | 17 | 18 | 19 | 20 - Ts ii b d b ¢ a b a Miahar Order Thinkina Skilic HQOTC