Summary notes on topic "STACK" based on NCERT 11th & 12th Book.
-----------------------------------
• Stack is a data structure in which insertion and deletion is done from one end only, usually referred to as TOP.
• Stack follows LIFO principle using which an element inserted in the last will be the first one to be out.
• PUSH and POP are two basic operations performed on a stack for insertion and deletion of elements, respectively.
• Trying to pop an element from an empty stack results into a special condition underflow.
• In Python, list is used for implementing a stack and its built-in-functions append and pop are used for insertion and deletion, respectively.
Hence, no explicit declaration of TOP is needed.
• Any arithmetic expression can be represented in any of the three notations viz. Infix, Prefix and Postfix.
• While programming, Infix notation is used for writing an expression in which binary operators are written in between the operands.
• A single traversal from left to right of Prefix/ Postfix expression is sufficient to evaluate the expression as operators are correctly placed as per their order of precedence.
• Stack is commonly used data structure to convert an Infix expression into equivalent Prefix/Postfix notation.
• While conversion of an Infix notation to its equivalent Prefix/Postfix notation, only operators are PUSHed onto the Stack.
• When evaluating any Postfix expression using Stack, only operands are PUSHed onto it.
MCQ Qu-Ans
Qu: The end from which elements are added or deleted is called _________ of a stack.
Qu: Trying to add an element to a full stack results in an exception called __________
Qu: __________ adds a new element at the TOP of the stack.
Qu: Built-in method of list to add an element to the stack.
Qu: Trying to pop an element from an empty stack results into a special condition called________ .
Qu: Any arithmetic expression can be represented in any of the notation.
Qu: x+y can be written as xy+. This is called
$ads={1}
Qu: Polish mathematician Jan Lukasiewicz in the 1920’s introduced a different way of representing arithmetic expression, called
Qu: Insertion in queue happens at the ________ end. Deletion happens at the __________.
Qu: Queue is an ordered linear data structure, following ___________ strategy.
Qu: The postfix form of the expression (A+ B)*(C*D- E)*F / G is?
Qu: The data structure required to check whether an expression contains balanced parenthesis is?
Qu: What data structure would you mostly likely see in a non recursive implementation of a recursive algorithm?
Qu: The process of accessing data stored in a serial access memory is similar to manipulating data on a ------?
Qu: The postfix form of A*B+C/D is?
Qu: Which data structure is needed to convert infix notation to postfix notation?
Qu: The prefix form of A-B/ (C * D ⋀ E) is?
Qu: What is the result of the following operation Top (Push (S, X))
Qu: The prefix form of an infix expression p + q - r * t is?
Qu: Which data structure is used for implementing recursion?
Qu: The result of evaluating the postfix expression 5, 4, 6, +, *, 4, 9, 3, /, +, * is?
Qu: Convert the following infix expressions into its equivalent postfix expressions (A + B ⋀D)/(E - F)+G
Qu: Convert the following Infix expression to Postfix form using a stack x + y * z + (p * q + r) * s, Follow usual precedence rule and assume that the expression is legal.
Qu: Which of the following statement(s) about stack data structure is/are NOT correct?
Qu: Consider the linked list implementation of a stack. Which of the following node is considered as Top of the stack?
$ads={2}
Qu: Consider the usual implementation of parentheses balancing program using stack. What is the maximum number of parentheses that will appear on stack at any instance of time during the analysis of ( ( ) ( ( ) ) ( ( ) ) )?
Qu: Which of the following is not an inherent application of stack?
Qu: Which of the following operation take worst case linear time in the array implementation of stack?
Qu: The type of expression in which operator succeeds its operands is?
Qu: Which of the following application generally use a stack?
Qu: If the elements “A”, “B”, “C” and “D” are placed in a stack and are deleted one at a time, in what order will they be removed?
Qu: What is the minimum number of stacks of size n required to implement a queue of size n?
Qu: Assume that the operators +,-, X are left associative and ⋀ is right associative. The order of precedence (from highest to lowest) is ⋀, X, +, -. The postfix expression corresponding to the infix expression a + b X c – d ⋀ e ⋀ f is
