When five items: A, B, C, D, and E are pushed in a stack: Order of stack becomes: A, B, C, D, and E (A at the bottom and E at the top.) stack is popped four items and each element is inserted in a queue: Order of queue: B, C, D, E (B at rear and E at the front) Order of stack after pop operations = A. Two elements deleted from the queue and pushed back stack: New order of stack = A, E, D(A at the bottom, D at the top) As D is on the top so when pop operation occurs D will be popped out. So, correct option is (D).

→ The stack is the best data structure to validate the arithmetic expression.
→ While evaluating when left parentheses occur then it pushes into the stack when right parentheses occur pop from the stack. While at the end there is empty in the stack.

Expression: 8 2 3 ^ / 2 3 * + 5 1 * –
Rule (1): If the element is a number, Push it into stack.
Rule (2): If the element is an operator, Pop operands from the stack. Evaluate the operator operation and Push the result back into the stack.

A circular queue is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end.
The front and rear pointers are initialized to point at q[2] which means third element.
First element will add at q[3] , second element will add at q[4] and so on eight element will add at q[10].
Q[10] is the end of the queue which is connected to q[0]
So ninth element can be added at q[0] pointer

Stack representation after inserting 5 elements

Stack is used for static memory allocation and Heap for dynamic memory allocation, both stored in the computer's RAM .
Variables allocated on the stack are stored directly to the memory and access to this memory is very fast, and it's allocation is dealt with when the program is compiled
Variables allocated on the heap have their memory allocated at run time and accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory . Element of the heap have no dependencies with each other and can always be accessed randomly at any time

● A deque, also known as a double ended queue, is an ordered collection of items similar to the queue. It has two ends, a front and a rear, and the items remain positioned in the collection.
● What makes a deque different is the unrestrictive nature of adding and removing items.New items can be added at either the front or the rear.
● Likewise, existing items can be removed from either end. In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.

For any number, we can check whether its ‘i’th bit is 0(OFF) or 1(ON) by bitwise ANDing it with “2^i” (2 raise to i).,
1) Let us take number 'NUM' and we want to check whether it's 0th bit is ON or OFF
bit = 2 ^ 0 (0th bit)
if NUM & bit == 1 means 0th bit is ON else 0th bit is OFF
2) Similarly if we want to check whether 5th bit is ON or OFF
bit = 2 ^ 5 (5th bit)
if NUM & bit == 1 means its 5th bit is ON else 5th bit is OFF.
Let us take unsigned integer (32 bit), which consist of 0-31 bits. To print binary representation of unsigned integer, start from 31th bit, check whether 31th bit is ON or OFF, if it is ON print “1” else print “0”. Now check whether 30th bit is ON or OFF, if it is ON print “1” else print “0”, do this for all bits from 31 to 0, finally we will get binary representation of number. void bin(unsigned n)
{
unsigned i;
for (i = 1 << 31; i > 0; i = i / 2)
(n & i)? printf("1"): printf("0");
}
int main(void)
{
bin(7);
printf("\n");
bin(4);
}

a+bc-d＾e＾f
⟶ left to right
Step 1: abc+

Max-Heap has 5 elements:
The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.

Since it is mentioned in the question that both of the operations are performed efficiently. Hence even the worst case time complexity will be O(1) by the use of the Circular queue there won't be any need of shifting in the array.

Final Pop sequence: 22112

Step-1: Pop elements from Stack-1 and push into Stack-2.
For this,
int x=element=stack-1,pop();
stack-2.push(element);

Step-2: Once the complete stack-1 gets copied to Stack-2, then we can simply call pop() on s2, it will remove the element-1.
So, A queue can be implemented using 2 stacks.

Initially stack is empty. We are using last in first out strategy.
Step-1: PUSH 15,PUSH 4 and PUSH 6 from bottom to top. Now top of the stack value is 6.
Step-2: Perform MULT operation. 6*4=24. Now present stack values are from bottom is 15 and 24.
Step-3: Next again PUSH 30. Now top of the stack is 30.
Step-4: Perform ADD operation. 30+24=54
Step-5: Now present stack values are from bottom is 15 and 54. Perform ADD operation.
Step-6: 15+54=69

Everyone thought that answer in worst case time is O(n) for both the cases but using circular queue, we can implement in constant amount of time.

Process scheduling operating system is application of queue.

→ Recursion is implemented stack
→ Scheduling can be implemented using Queue.
→ The inorder traversal of binary search gives sorting order.

Breadth first search and Process scheduling can be implemented by using Queue.
Binary search can be implemented by using recursion. So Stack is suitable for implementing function calls.

Front and rear initially points to same location and once rear is incremented by 1 it means element is added and front is used to delete so here we don't need front for 1 element in the queue.

Postfix Expression are usually converted from infix Expression using Stack Data structure.
Algorithm
We have Postfix[ ] Array, Stack, Infix[ ] Array
1. Scan the given expression (Infix ) from Left to Right [ one character at a time].
2. Check Whether the given character is an operator [+, -, *, /, ^ etc] or operand.
3. If it is an operand, then copy it in the Prefix Array.
4. If it is a operator then,
1. Check whether, Stack is empty or not
2. If it is empty then, push the operator in the stack and go to step
3. If Stack is not empty then compare the precedence of Top of stack with operator.
4. If the Top of Stack has higher or equal precedence then pop it and copy in the postfix array.
5. If the operator has higher precedence, push it in the stack and go to step 5.
6. If Stack is not empty go back to step 4(1).
5. Continue solving the expression in usual manner until the expression come to end.
6. Pop the remaining operand in the stack and copy it to postfix array.

→ Every processor provides us with some form of call instruction, which pushes the address of the next instruction on the stack and transfers control to the address specified by the call.
→ When the called procedure is done, it issues a return instruction, which pops the address from the top of the stack and transfers control there.
→ That’s just the basic processor mechanism that makes it easy to implement procedure calls. The actual details of identifying the parameters, placing them on the stack, executing a call instruction are up to the compiler.
→ In the called function, the compiler is responsible for ensuring any registers that may be clobbered are saved, allocating stack space for local variables, and then restoring the registers and stack prior to a return.

Step-1: Initially P,Q,R,S and T are pushed in a stack. The stack elements will be placed in LIFO manner. It beans that bottom of the stack value from P to T.
Step-2: Then we have to pop 4 elements. So, present having only one element,that is P.
Step-3: 4 elements we have to insert into a Queue. Queue follows FIFO manner.
Step-4: Again we have to delete two elements from queue and inserted into stack.
Step-5: The inserted elements are T and S.
Step-6: Final pop element is S.
Step-7: Stack having only two elements. P and T.

→n_A is the number of elements in stack A and n_B is the number of elements in stack B, Where “n” is total elements we can insert into stack.
→The sum of the n_A and n_B is equal to the number of elements there is no possibility of inserting element into stack.

The infix string a+b*c-d/e*h.
=a+[bc*]-d/e*h // Select highest priority operators and convert into postfix form,If same priority then go for associativity
=a+[bc*]-[de/]*h
=a+[bc*]-[de/h*]
=[abc*+]-[de/h*]
=abc*+de/h*-

→Various Queues like Ready queue,Job Queue , Waiting Queue and so on are used in the operating system for process scheduling.
→Queue is also used for Breadth first traversal also

Step-1: Insert all elements into stack in reverse order then the stack is look like

Step-2: Stack is pooped five elements then stack is look like

Step-3: Popped five elements are inserted into a queue then queue is look like

Step-4: Two elements are deleted from the queue

Step-5: deleted queue elements are pushed back onto the stack

Top of the stack is B.

→ Implementing queue by using two stack:
(1) When calling the enqueue method, simply push the elements into the stack 1.
(2) If the dequeue method is called, push all the elements from stack 1 into stack 2, which reverses the order of the elements. Now pop from stack 2.
→ A stack can be implemented using two queues

Here, stack size is 5. Stack operations are explained in step by step.

Applications
1. Implementation of recursion
2. Evaluation of a postfix expression
3. Expression evaluation and syntax parsing
4. Backtracking
5. Compile time memory management
6. Reverse a string

In this problem look very difficult to solve, but problem is following standard formula only.
Step-1: Total number of letters/operands with duplication is 5.
Step-3: To find total number of ways, we have catalan formula.
Here, n=5
Catalan number = (2n)! / (n! * (n+1)!)
= (2*5)! / (5! * (5+1)!)
= 10! / (5! * 6!)
= 14
Note: We used catalan formula because they given in fully parenthesized to yield an infix expression.

Initially the queue order is

Step-1: Delete ‘a’ from queue. The deletion operation performs First In First Out.We will perform the deletion at front end
After deleting queue will become

Step-3: Delete ‘b’ from queue. The deletion operation performs First In First Out.
After deleting queue will become

Step-3: Delete ‘c’ from queue. The deletion operation performs First In First Out.
After deleting queue will become

Step-4: Insert the element “c” into the queue, We will perform the insertion at rear end
The elements of queue after inserting the element ”c” are

Step-5: Insert the element “b” into the queue,then the elements of queue after inserting the element ”b” are

step-6: Insert the element “a” into the queue,then the elements of queue after inserting the element ”a” are

→ Step-1,step-2 and step-3 are deletion operations and step-4,step-5 and step-6 are deletions operations.
→ So total 3 deletions and 3 insertions are required to get required configuration.

Average case in linked list:

Worst case in linked list:

Postfix expression: d ef + / bc * +

Application of data structure queue is implementation of priority queues. In a priority queue, an element with high priority is served before an element with low priority. In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined. While priority queues are often implemented with heaps.
Applications:
1.Bandwidth management
2.Discrete event simulation
3.Dijkstra's algorithm
4.Huffman coding
5.Best-first search algorithms
6.ROAM triangulation algorithm
7.Prim's algorithm for minimum spanning tree

Given infix notation, we have to change infix notation into postfix notation.
after converting postfix notation the notations are ab* cde /* +

Total 5 PUSH and 4 POP operations performed.

S1: TRUE: It is a data structure in which the intrinsic ordering of the elements does determine the result of its basic operations.
S2: TRUE: The elements of a priority queue may be complex structures that are ordered on one or several fields.

Option-A: According to constraint,
Push(A) then Pop(A)
Push(B) then Pop(B)
Push(C) then Pop(C)
Then the possible pop sequence is ABC. So, it is TRUE
Option-B: According to given constraint, Push(A),Push(B) and Push(C) then Pop(C),
Pop(B) and Pop(A). The possible Pop sequence is CBA. So, it is TRUE
Option-C: According to given constraint, Push(A) and Push(B) then Pop(B) and Pop(A)
then push(C) and Pop(C). The possible Pop sequence is BAC. So, it is TRUE
Option-D: This is not possible.

→ Priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it.
→ In a priority queue, an element with high priority is served before an element with low priority.
→ In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.
→ While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map".
→ just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.

Queue is FIFO(First In First Out) and Stack is LIFO(Last In First Out).

The above data clearly using first in first out(FIFO) condition. FIFO we are using queue data structure.

To print values in reverse order we are preferring stack data structure only. Stack using Last in first out(LIFO) procedure.

→ Stack is used to implement recursion. It uses Last in first out procedure.
→ Recursion is one the application of stack. It supports many applications.
Applications:
1. Expression Evaluation
2. Expression Conversion
3. Syntax Parsing
4. Backtracking
5. Parenthesis Checking
6. String Reversal

Queue applications:
1. CPU scheduling
2. Disk Scheduling
3. synchronization(IO Buffers, pipes, file IO, etc.)
4. Breadth First search
5. Implementation of priority queues.