Assignment II Stack,Queue, Searching, Hashing

void fun(Queue *Q)

{

    Stack S;  // Say it creates an empty stack S

 

    // Run while Q is not empty

    while (!isEmpty(Q))

    {

        // deQueue an item from Q and push the dequeued item to S

        push(&S, deQueue(Q));

    }

 

    // Run while Stack S is not empty

    while (!isEmpty(&S))

    {

      // Pop an item from S and enqueue the popped item to Q

      enQueue(Q, pop(&S));

    }

}

What does the above function do in general?

• Removes the last from Q

• 
  Keeps the Q same as it was before the call

• Makes Q empty

• Reverses the Q

How many queues are needed to implement a stack. Consider the situation where no other data structure like arrays, linked list is available to you.

• 1

• 2

• 3

• 4

Which one of the following is an application of Queue Data Structure?

• When a resource is shared among multiple consumers.

• When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes

• Load Balancing

• All of the above

Answer explanation

(A) When a resource is shared among multiple consumers: In scenarios where a resource (such as a printer, CPU time, or database connection) needs to be shared among multiple consumers or processes, a queue data structure can be used. Each consumer can enqueue their requests for the resource, and the resource can be allocated to them in the order of their requests by dequeuing from the queue. This ensures fair access to the shared resource and prevents conflicts or resource contention.

(B) When data is transferred asynchronously between two processes: When data is transferred asynchronously between two processes or systems, a queue can be used as a buffer or intermediary storage. One process enqueues the data to be sent, while the other process dequeues and processes the received data. The queue allows for decoupling the rate of data production from data consumption, ensuring smooth and efficient communication between the processes.

(C) Load Balancing: Load balancing is the practice of distributing workloads across multiple resources to optimize performance and utilization. A queue data structure can be used in load-balancing algorithms to manage incoming requests or tasks. The requests are enqueued in the queue, and the load balancer can dequeue and assign them to available resources based on various criteria (e.g., round-robin, least connections). This helps distribute the workload evenly across the resources, preventing overload and maximizing throughput.

Hence (D) is the correct option. 

Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

• Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT

• Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR

• Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT

• Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT

Answer explanation

Suppose we start filling the queue.

Let the maxQueueSize ( Capacity of the Queue) is 4.So the size of the array which is used to implement this circular queue is 5, which is n. In the beginning when the queue is empty, FRONT and REAR point to 0 index in the array. REAR represents insertion at the REAR index. FRONT represents deletion from the FRONT index.

enqueue("a"); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 1)

enqueue("b"); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 2)

enqueue("c"); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 3)

enqueue("d"); REAR = (REAR+1)%5; ( FRONT = 0, REAR = 4)

Now the queue size is 4 which is equal to the maxQueueSize. Hence overflow condition is reached.

Now, we can check for the conditions.

When Queue Full :
( REAR+1)%n = (4+1)%5 = 0
FRONT is also 0. Hence ( REAR + 1 ) %n is equal to FRONT.

When Queue Empty :

REAR was equal to FRONT when empty ( because in the starting before filling the queue FRONT = REAR = 0 )

Hence Option A is correct. 

Identify the data structure which allows deletions at both ends of the list but insertion at only one end.

• Stack

• Priority queues

• Output restricted qequeue

• Input restricted dequeue

Choose correct output for the following sequence of operations.

push(5)

push(8)

pop

push(2)

push(5)

pop

pop

pop

push(1)

pop

• 8 5 2 5 1

• 8 5 5 2 1

• 8 2 5 5 1

• 8 1 2 5 5

• A B * C + D / -

• A B C * C D / - +

• A B + C D * - / E

• A B + C D - * E /

When new data are to be inserted into a data structure, but there is not available space; this situation is usually called .......

• overflow

• Underflow

• housefull

• memoryfull

The number of comparisons done by sequential search is .......

• (N/2)-1

• (N+1)/2

• (N-1)/2

• (N+2)/2

In ......, search start at the beginning of the list and check every element in the list.

• Hash Search

• Binary search

• Linear search

• Binary Tree search