Test: Queues & Stacks - Computer Science Engineering (CSE) MCQ

Answer A - Circular Queue Implementation

Both operations can be performed in O(1) time in Circular Queue implimentation where Enqueue and Dequeue operation are done at last node. Single pointer needed at last node.

Let's analyze each statement to determine which ones are true:

i. First-in-first-out types of computations are efficiently supported by STACKS.
   - This statement is false. Stacks support Last-in-First-out (LIFO) operations, not FIFO. So, this statement is not true.

ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.**
   - This statement is generally true. Linked lists allow for efficient insertion and deletion operations, which are costly in arrays due to the need to shift elements.

iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.
   - This statement is true. Circular arrays can utilize the entire array space more efficiently and avoid unnecessary shifts compared to a linear array with two indices.

iv. Last-in-first-out type of computations are efficiently supported by QUEUES.
   - This statement is false. Last-in-first-out (LIFO) operations are supported by stacks, not queues. Queues support First-in-First-out (FIFO) operations.

Conclusion

Based on the analysis:

- Statement ii and iii are true:
  - ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
  - iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.

Therefore, the correct answer is:

1. (ii) and (iii) are true

A queue can be implemented using two stacks.
Let queue be represented as " q "
and stacks used to implement q be "stack1" and "stack2".
q can be implemented in two ways:
Method 1 (By making EnQueue operation costly)

This method makes sure that newly entered element is always at the bottom of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.

enQueue(q, x)

1) While stack1 is not empty, push everything from satck1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.

dnQueue(q)

1) If stack1 is empty then error
2) Pop an item from stack1 and return it

Method 2 (By making deQueue operation costly)

In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is
empty then all the elements are moved to stack2 and finally top of stack2 is returned.

enQueue(q, x)

1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)

1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from satck1 to stack2.
3) Pop the element from stack2 and return it.

Answer is (a)
The order in which insert and delete operations are performed matters here.
The best case: Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push
operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed.
The worst case: First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed. Other than first, in all delete operations, 1 pop operation is performed. So, total m + n pop operations and 2n push operations are performed (n push for insert() and m push for delete())

insert() will inserts the value in just reverse order.

rear = Write
front = Read
full: (REAR+1) mod n == FRONT
empty: REAR == FRONT
Only option A matches.

There are three possible operations on queue- Enqueue, Dequeue and MultiDequeue. MultiDequeue is calling Dequeue multiple times based on a global variable k. Since, the queue is initially empty, whatever be the order of these operations, there cannot be more no. of Dequeue operations than Enqueue operations. Hence, the total no. operations will be  n only.

Answer is Next pointer to Rear node has Pointer to Front node.
Hence, only  II is correct.

Lets try something different when you read the word pop then delete the last pushed element and print it ..now delete the push word which we have already executed ..now go on from left to right and do the same
So, Output will be 20, 20, 10, 10, 20

push 1 push 2 push 3 pop 3 push 4 pop 4 push 5 pop 5 pop 2 pop 1 then o/p is 3,4,5,2,1 option b

Implementing stack using priority queue require first element inserted in stack will be deleted at last, and to implement it using deletemin() operation of queue will require first element inserted in queue must have highest priority.
So the keys must be in strictly decreasing order.

let us represent stack-life of i^th element as S(i). The i^th element will be in stack till (n-i) elements are pushed and popped. Plus one more Y for the time interval between the push of   i^th  element and the i+1^th element. So, 

Since the stacks are growing from opposite ends, initially top1 = 1 and top2 = MAXSIZE. Now, to make the space usage most efficient we should allow one stack to use the maximum possible space as long as other stack doesn't need it. So, either of the stack can grow as long as there is space on the array and hence the condition must be top1 = top2 - 1;

Here is the procedure first :
Scan Infix Expression from left to right whenever you see operand just print it.
But In case of operator
if(stack is empty) then push it.
if(precedence(tos) < precedence(current operator) ) push it.
else if (precedence(tos) > precedence(current operator) ) pop and print.

else if (precedence(tos) == precedence(current operator) ) then check for associativity.In case Operators are Left to right
then pop and print it otherwise push the current operator (Right to Left Associativity)
And once you have scanned infix expression completely. Make sure pop all the element and print it in same order.
Here the infix expression is a+b×c−d^e^f
a : print it
+ : push into the Operator Stack
b : print it
* : its having higher precedence than + then push into Operator Stack
c : print it
'-' : '-' is having less precedence than '*' so pop from operator stack and print '*'.after this stack will be having '+' on
top.which is having same precedence as '-' but both are left to right associative then just pop + and print it.Now stack is
empty. Push '-' to it.
d : print it
'^' : top of the stack is having '-' which has lower precedence than '^' so simply push '^' into stack
e : print it.
'^' : Now top of the stack is '^' and has same precedence so associativity will come to picture. Since '^' is right associative
as given in question. So '^' will be pushed.
f : print it.
Now we have scanned entire infix expression.Now pop the stack untill it becomes empty.This way you will get
abc*+def^^-

STACK Scan the expression from left to right whenever a left paranthesis is encountered just PUSH it into stack and whenever a right paranthesis is encountered just POP it from stack ..if at the end of expression we are left with an empty stack then it is a correctly parenthesized expression

A. push a & pop a, push b & pop b, push c & pop c, and finally push d and pop d
sequence of popped elements will come to abcd
B. first push abcd, and after that pop one by one sequence of popped elements will come to dcba
C. push abc, and after that pop one by one sequence of popped elements will come to cba, now push d and pop d, final
sequence comes to cbad
D. this sequence is not possible because 'a' can not be pooped before 'b' any how

i Element to be pushed

Initial State f(φ) = 0 For Empty Stack F(S) is 0.

Then we push each element ( )one by one and calculate f(s)for each insertion as given

Is the function to compute F(s) for each insertions

1. INSERT 2 into Stack

Similarly ,

The value of F(s) after inserting all elements into stack is 3 

push 8 so stack is 8
push 2 so stack is 8 2
push 8 2 3
^ pop 3 and 2 perform opn 2^3 and push to stack. stack is 8 8
/ pop 8 and 8 perform 8/8 and push result to stack . stack is 1
push 2 stack is 1 2
push 3 stack is 1 2 3
* pop 3 and 2 perform by 2*3 and push . stack is 1 6

B) 25
let first part
5 ----push
2------push
push------5*2=10. (pops 5 and 2)

push 3
push 3
push 2
push 3+2 = 5 (pops 2 and 3)
push 5*3 = 15 (pops (5 and 3)
push 15 + 10 = 25 (pops (15 and 10)

(C) is the answer. While ENQUEUE we REVERSE the stack, PUSH the element and then again REVERSE the stack. For DEQUE we simply POP the element.
(Option (B) can be used to get the first element from the stack by doing a POP after REVERSE for DEQUEUE and PUSH for\ ENQUEUE. But we have to restore the stack using REVERSE (otherwise next POP won't work) which means DEQUEUE actually needs 3 instructions and not 2)

we have to keep symbol into stack and when we get two operands followed by operator ..we will apply operator on last two operands

symbol                     stack

10                       10 (keep in stack)
 5                 10 5 (keep in stack)

+                  10 5 + = 10+5 = 15 ( apply operator on last 2 operands)

60                 15 60 (keep in stack) 

6                  15 60 6 (keep in stack)

/                        15 60 6 / = 15 10 ( apply operator on last  2 operands)

*                      15 10 * = 150 ( apply operator on last 2 operands)

8                     150 8 (Keep in stack)   

-                  150 8 - = 150 - 8 = 142 (apply operator on last 2 operands)

First push (((( on stack. Now when ) comes pop all (((( and push ) on stack. Now push ((( and stack become )((( . Now when ) come it pop all ((( from stack and new stack become )). Again ) comes and stack become ))) . Now push (((( on stack and the stack becomes (((())). Now pop one by one and get option D as the answer

Since the stack data structure follows LIFO order. When we pop() items from stack, they are popped in reverse order of their insertion (or push())

At the end of while loop, we must check whether the stack is empty or not. For input ((()), the stack doesn't remain empty after the loop.