Computer Science Test - 11

The correct answer is option 1.

Concept:

A stack is a linear data type that acts as a collection of elements. A stack is a linear data structure that operates memory allocation and deallocation on the Last-In-First-Out (LIFO) principle. In linear data structures, the elements are accessed in sequential order but it is not compulsory to store all elements sequentially. It has two main operations:

• Push, which adds a new element to the collection, and
• Pop, which removes the most recently added element that hasn't been removed yet.

Hence the correct answer is Last­-in-­first­-out (LIFO) manner.

Additional Information

Stack applications:

• Balancing of symbols.
• Infix to postfix conversion.
• Evaluation of postfix expression.
• Implementing function calls.
• Finding of spans in stock markets.
• Page-visited history in a web browser.
• Undo sequence in the text editor.
• Matching tags in Html and xml.

Stack data structure is suitable for evaluating postfix expression. 

Stack : Stack is a linear data structure in which elements are inserted and deleted from one end only i.e. top of the stack. It follows a order to insert the elements into stack which is known as LIFO (Last in first out). Operations that are performed on a stack are : Push , Pop and peek.

Applications of stack :

• Stack can be used for evaluating arithmetic expression.(Postfix, prefix evaluation).
• It can be used for conversion from one expression to another.
• It can be used to check matching parenthesis in any expression.
• It can be used for memory management.
• It can undo the operation of a document editor or similar environment.
• It is used for backtracking.
• It keeps track of page visiting history  of a web user.
• It is used in the implementation of recursive procedures.

Evaluation rule of postfix expression :

1) While reading the expression from left to right, push the element in the stack if it is an operand.

2) Pop the two operands from the stack, if the element is an operator and evaluate it.

3) Push back the result of evaluation. Repeat till the end of expression.

Stack:

• Stack is a data structure which possesses the LIFO property i.e. last in first out. The element which inserted at the last will come out first from the stack.
• Two operations that can be performed on the stack are Push and Pop.
• Push is used to insert element into the stack and pop operation is used to remove element from the top of the stack.

Applications of stack:

1) Expression conversion such as infix to postfix, infix to prefix.

2) Expression evaluation

3) Parsing well-formed parenthesis

4) Decimal to binary conversion

5) Reversing a string

6) Storing function calls

Note:

Queue data structure is used for process scheduling operating system. 

Concept:

() has highest precedence

* and / has same precedence while + and – has same precedence

(* and /) and higher precedence than (+, -)

Associativity is left to right:

Explanation:

(A + B) * C – D * E / F

A B + * C – D * E / F

A B + C * – D * E / F

A B + C * – D E * / F

A B + C * – D E * F /

A B + C * D E * F / –

Key Points   Stack is a simple linear data structure that is used for storing data. In stack, the order in which the data arrives is the most important. Considering this, a stack can be defined as an ordered list in which insertion and deletion are performed at one end which is called top.

The element inserted at the last is the first one to be deleted. Hence, a stack is called First In Last Out (FILO) or Last In First Out (LIFO) list.

Mainly the following three basic operations are performed in the stack:

Push: Push operation adds an item/data into the stack. If the stack is full, then it is called an Overflow condition.

Pop: Pop operation removes an item/data from the stack. The items are popped in the reversed order in which they are pushed into the stack. If the stack is

empty, then it is called an Underflow condition.

So the poped elements are 1,5

Hence the correct answer is 1,5.

Additional InformationApplications of the stack:

• Balancing of symbols.
• Infix to Postfix /Prefix conversion.
• Implementing function calls (recursion).
• Undo sequence in a text editor.
• Forward and backward features in web browsers.
• Other applications can be Backtracking, a Knight tour problem, a rat in a maze, an N-queen problem, and a sudoku solver.

The stack pointer is pointing at top of the stack, that is, to element 2

After 1^st pop:

2 is deleted

After 2^nd pop:

4 is deleted

After 3^rd pop

1 is deleted

A – B + C / (D – E) * F

A – B + C / –DE * F     //bracket has highest precedence

A – B + /C–DE * F      //associativity of * and / is left to right with same precedence

A – B + */C–DEF

–AB + */C–DEF     //associativity of + and – is left to right with same precedence

+–AB*/C–DEF

Therefore answer 4 is correct.

Postfix expression: 6 2 3 * / 4 2 * + 6 8 * -

PUSH: 50, 60, 70

POP: 70 and POP: 60

PUSH: 80, 90, 100,110

POP: 110

PUSH: 120, 130

POP: 130 and POP 120

PUSH: 140

POP: 140

PUSH(50), PUSH(60) (2), PUSH(70) (1), POP, POP, PUSH(80), PUSH(90), PUSH(100), PUSH(110) (3), POP, PUSH(120) PUSH(130)(4), POP, POP, PUSH(140), POP

for a)

for b)

So, 2 3 5 4 1

for c)

so, 4 3 5 2 1

for d)

So, the permutation 3, 4, 1, 5, 2 is invalid