Tuesday, March 13, 2012

Double Ended Queue ( DEQUE)





It is a homogeneous list of elements in which insertion and deletion operations are performed from both the ends i.e, we can insert elements from the rear end or from the front ends. Hence, it is called double-ended queue. It is commonly referred to as deque.

There are two types of deques. These two types are due to the restrictions put to preform either the insertions or deletions only at the end. They are :

1) Input Restricted Deque 
2) Output Restricted Deque

Four Operations :

=> Insertion of an element at the REAR end of the queue
=> Deletion of an element from the FRONT end of the queue
=> Insertion of an element at the FRONT end of the queue
=> Deletion of an element from the REAR end of the queue


For an input-restricted deque only the operations 1,2,3 & 4 are valid. And for an output-restricated deque only the operations specified in 1,2,3 are valid.

a) Insertion of an element at the REAR end of the queue

void dqinsert_rear(int q[10],int front,int rear,int item,int MAXSIZE)
{
   if(rear == (MAXSIZE-1))
   {
      printf(" QUEUE is full ");
      return;
   }
  rear=rear+1;
  q[rear]=item;
}


b) Deletions of an element from the FRONT end of the queue

void dqdelete_front(int q[10],int front,int rear,int item)
{
    if(front == rear)
    {
         printf(" QUEUE is empty ");
         return;
    }

    front=front+1;
    item=q[item];
}



3) Insertion of an element at the FRONT end of the queue

void dqinsert_front(int q[10], int front, int rear, int item)
{
     if(front == 0)
     {
            printf(" QUEUE is full");
            return;
     }
     front=front-1;
     q[front]=item;

}



d) Deletion of an element from the REAR end of the queue


void dqdelete_rear( int q[10], int front, int rear, int item)
{
   if(front == rear)
   {
       printf(" QUEUE is empty ");
       return;
   }

   rear=rear-1;
   item=q[item];

}




e) Function to display the contents (status) of a QUEUE

void dq_display(int q[10], int front, int rear)
{
    if(front <= rear)
    {
         printf(" Status of the Queue \n");
         for(i = front; i<=rear; i++)
         printf("%d",dq[i]);
    }
    else
        printf(" QUEUE is empty ");

}

Thursday, March 8, 2012

Important Questions On Linked List :::

1) What pointer type is used to implement the heterogeneous linked list in C ?
Ans :

The answer is the void pointer.
The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. Since we can't use ordinary pointers for this, we use the void pointer. Void Pointer is a generic pointer type, and capable of storing pointer to any type.





2) Can we do a Binary Search on a LInked List ?
Ans :

We can get to the middle of the array just by saying array[middle].
Now, we cannot do the same with a linked list. We will have to write your own, possible inefficient algorithm to get the value of the middle node of a linked list. In a linked list, you lose the ability to get the value of any node in a constant time.

One solution to the inefficiency of getting the middle of the linked list during a binary search is to have the first node contain one additional pointer that points to he node in the middle. Decide at the first node if you need to check the first or the second half of the linked list. Continue doing that with each half list.




3) Whether Linked List is linear or Non Linear data structure ?

Ans :


According to Access strategies Linked LIst is a linear one.
According to Storage Linked List is a Non Linear One.






4) How can we search for data in a Linked List ?

Ans :

The only way to search a linked list is with a linear search, because the only way a linked list's members cab be accessed is sequentially. Sometimes it is quicker to take the data from a linked list and store it in a different data structure so that searches can be more efficient.






5) What member function places a new node at the end of the Linked List ?

Ans:


The appendNode() member function places a new node at the end of the linked list. The appendNode() requires an integer representing the current data of the node.







6) What does the prototype of calloc() look like ?

Ans :  

void *calloc(size_t num, size_t size);




7) What is the lenth of the null() list ?

Ans :    1