QUEUE AND TREE

A queue is another special kind of list, where items are inserted at one end call ed therear and deleted at the other end called the front. Another name for a queue is a“FIFO” or “First-in-first-out” list.

The operations for a queue are  analogues to those for a stack, the difference is  that theinsertions go at the end of the list, rather than the beginning. We shall use thefollowing operations on queues:
• enqueue: which inserts an element at the end of the queue.
• dequeue: which deletes an element at the start of the queue.

Representation of Queue: 
 

 

Source code for Queue operations using array: 

In order to create a queue we require a one dimensional array Q(1:n) and twovaria ble s  f  ront and rear. The conventions we shall adopt for these two variables arethat front is always 1 less than the actual front of the queue and rear always points tothe last element in the queue. Thus, front = rear if and only if there are no elements inthe queue. The initial condition then is front = rear = 0. The various queue operationsto perform creation, deletion and display the elements in a queue are as follows:

1. insertQ(): inserts an element at the end of queue Q.
2. deleteQ(): deletes the first element of Q.
3. displayQ(): displays the elements in the queue. 

# include <conio.h>
# define MAX 6
int Q[MAX];
int front, rear;
void insertQ()
{
       int data;
       if(rear == MAX)
         {
                 printf("\n Linear Queue is full");
                  return;
          }
      else
          {
                             printf("\n Enter data: ");
                             scanf("%d", &data);
                              Q[rear] = data;
                                 rear++;
                                 printf("\n Data Inserted in the Queue ");
          }
}

void deleteQ()
                         {
                                   if(rear == front)
                                    {
                                         printf("\n\n Queue is Empty..");
                                           return;
                                     }
                                 else
                                    {
                                        printf("\n Deleted element from Queue is %d", Q[front]);
                                        front++;
                                    }
                         }

void displayQ()
                       {
                                       int i;
                                       if(front == rear)
                                       {
                                                printf("\n\n\t Queue is Empty");
                                                 return;
                                        }
                                    else
                                       {
                                               printf("\n Elements in Queue are: ");
                                               for(i = front; i < rear; i++)

                                                {
                                                             printf("%d\t", Q[i]);
                                                  }
                                        }
                          }
 

int menu()
                  {
                               int ch;
                               clrscr();
                              printf("\n \tQueue operations using ARRAY..");
                              printf("\n -----------**********-------------\n");
                              printf("\n 1. Insert ");
                              printf("\n 2. Delete ");
                              printf("\n 3. Display");
                              printf("\n 4. Quit ");
                              printf("\n Enter your choice: ");
                              scanf("%d", &ch);
                              return ch;
               }

void main()

{
            int ch;
            do
              {
                               ch = menu();
                               switch(ch)
                                   {
                                            case 1:
                                                          insertQ();
                                                          break;

                                           case 2:
                                                          deleteQ();
                                                          break;
                                           case 3:
                                                           displayQ();
                                                            break;
                                           case 4:
                                                            return;
                                     }
                                        getch();
             } while(1);
 

}

Linked List Implementation of Queue:

We can represent a queue as a linked list. In a queue data is deleted from the  front  endand inserted at the rear end. We can perform similar operations on the two ends of alist. We use two pointers front and rear for our linked queue implementation. 

Source code for queue operations using linked list:

# include <stdlib.h>
# include <conio.h>
struct queue

{
         int data;
        struct queue *next;
};

typedef struct queue node;
node *front = NULL;
node *rear = NULL;

node* getnode()
{
       node *temp;
       temp = (node *) malloc(sizeof(node)) ;
       printf("\n Enter data ");
       scanf("%d", &temp -> data);
       temp -> next = NULL;
       return temp;
}

void insertQ()
{
           node *newnode;
           newnode= getnode();
           if(newnode== NULL)
              {
                  printf("\n Queue Full");
                   return;
               }
           if(front == NULL)
            {
                  front = newnode;
                   rear=newnode;
             }
          else
             {
                      rear -> next = newnode;
                      rear=newnode;
              }
 

               printf("\n\n\t Data Inserted into the Queue..");

}

void deleteQ()
{
               node *temp;
               if(front == NULL)
                 {
                        printf("\n\n\t Empty Queue..");
                        return;
                   }
                   temp = front;
                   front = front -> next;
                   printf("\n\n\t Deleted element from queue is %d ", temp -> data);
                    free(temp);
}

void displayQ()
{
                   node *temp;
                   if(front == NULL)
                     {
                           printf("\n\n\t\t Empty Queue ");
                      }
                    else
                      {
                                        temp = front;
                                        printf("\n\n\n\t\t Elements in the Queue are: ");
                            while(temp != NULL)
                                     {
                                                    printf("%5d ", temp -> data);
                                                       temp = temp -> next;
                                        }
                       }
}

char menu()
{
                           char ch;
                           clrscr();
                           printf("\n \t..Queue operations using pointers.. ");
                           printf("\n\t -----------**********-------------\n");
                           printf("\n 1. Insert ");
                           printf("\n 2. Delete ");
                           printf("\n 3. Display");
                           printf("\n 4. Quit ");
                           printf("\n Enter your choice: ");
                           ch = getche();
                           return ch;
}

void main()
{
               char ch;
               do
                   {
                           ch = menu();
                            switch(ch)
                              {
                                         case '1' :
                                                           insertQ();
                                                           break;
                                         case '2' :
                                                           deleteQ();
                                                           break;
                                         case '3' :
                                                           displayQ();
                                                           break;
                                        case '4':
                                                           return;
                              }
                                          getch();
                   } while(ch != '4');
}

DOWNLOAD TREE NOTES:   DOWNLOAD PDF FILE