Question

We discussed a stack which expands and contracts as data is inserted and deleted. We also discussed a queue which was fixed in size. Describe a technique that could be used to implement a queue which expands and contracts.

Answer 1

Describe a technique that could be used to implement a queue which expands and contracts.

Answer :

The most essential technique is Dynamic memory allocation.

In static memory allocation the size of the queue is kept as fixed, where array is used to implement queue. So, the length of the queue cannot be expanded as much as user need. On the other hand in static array based implementation, though the elements can be deleted from queue, but as the array is already fixed sized memory block, so actual contraction of memory is not done in practical scenario.

Dynamic memory allocation technique is the most effective approach of queue expansion and contraction as per user need. Using dynamic memory allocation technique, the elements can be added to the queue as much as user needs at the time of running the program; it does not have any fixed length. So queue expands according to requirement.

On the other hand the while the elements are removed in FCFS basis, the space allocated by that elements are also freed. Means the queue is contracted most ideally.

Link list is one of the approaches of dynamic memory allocation technique, where, queue elements are expanded as individual node(with data and address part) in the memory, means after creating a particular node in the memory , the value is added to the data part of the node. In this way by adding as much as nodes in the memory user can expand the queue. At the same time, removing the nodes from the queue, the queue can be contracted in most effective way.

malloc is one of the efficient approach to dynamically allocate space in memory and expand sthe queue , where free function is used to remove the memory space occupied by queue nodes and contract the memory.

Example :

Suppose in queue , a node is required to create, the allocated memory address is p and structure name is queue, so

p=(struct queue*)malloc(sizeof(struct queue));

In this way by nodes in memory the queue can be expanded.

According to FCFS, the elements are deleted from queue, suppose the address of first node in queue is p

free(p); is used to remove first node from queue and queue is contracted.

Here below the dynamic memory allocation technique with link list, is used on queue to expand and contract it.

Here fundamental programming C programming language is used to implement the queue with dynamic memory allocation technique. Below the example is given with source code, screen shot and desired output.

PROGRAM

#include<stdio.h>
#include<malloc.h>
struct queue
{
   int data;
   struct queue *next;
}; struct queue *first=NULL,*last=NULL,*p;

/* queue expand with expand() function dynamically*/
void expand()
{
    /*dynamically allocated nodes in queue as required*/
   p=(struct queue*)malloc(sizeof(struct queue));
   /* insert value in queue*/
    printf("Enter value in queue :");
    scanf("%d",&p->data);
    p->next=NULL;
    /* if initially queue is fully contracted */
    if(first==NULL)
    {
first=p;
   last =p;    
}
/* if queue is already expanded */
else
{
   last->next=p;
   last=p;
   }
}

/* contract the queue with contract() function */
void contract()
{
/* if queue is already contacted */
   if(first==NULL)
   {
       printf("\nQueue is already empty, no further contraction possible...\n");
   }
   else
   {
       /* take the first node address in p */
       p=first;
       first=first->next;
       /* free p, which removes the first node,so now the first node address
       is not occupied by any element of queue */
       free(p);
      
   }
}

/* display the queue */
void display()
{
   struct queue *t;
   t=first;
   if(first!=NULL)
   {
   printf("\nQueue elements are :\n");
   while(t!=NULL)
   {
       printf("%d\t",t->data);
       t=t->next;
   }
   printf("\n");
   }
   else
   {
       printf("\nThe queue is fully contracted...\n");
   }
  
}
int main()
{
   int op;
   op=1;
   /* when op is 4 loop will be terminated */
   while(op!=4)
   {
       printf("\n1.Expand Queue :");
       printf("\n2.Contract Queue:");
       printf("\n3.Display:");
       printf("\n4.Exit:");
       /* console input of option */
       printf("\nEnter option : ");
       scanf("%d",&op);
       switch(op)
       {
           case 1:
               expand();
               break;
           case 2:
               contract();
               break;
           case 3:
               display();
               break;
           case 4:
               printf("Exit....");
               break;
           default:
               printf("Give correct choice ");
       }
   }
return 0;
}

SCREEN SHOT

OUTPUT