Program to implement dynamically allocated Queue using linked list.

 #include <stdio.h>  
 #include <stdlib.h>  
 struct tag  
 {  
     int data;  
     struct tag *link;  
 };  
 typedef struct tag * NODE;  
 void ins_rnode();  
 void del_fnode();  
 void display();  
 int main()  
 {  
     int ch, element, dnum;  
     NODE front = NULL;  
     NODE rear = NULL;  
     do  
     {  
         printf("\nOPERATIONS ON QUEUE: ");  
         printf("\n1.) INSERT");  
         printf("\n2.) DELETE");  
         printf("\n3.) DISPLAY");  
         printf("\n4.) EXIT");  
         printf("\nEnter your choice: ");  
         scanf("%d", &ch);  
         switch(ch)  
         {  
             case 1: printf("\nEnter element to insert into the queue: ");  
                   scanf("%d", &element);  
                   ins_rnode(&front, &rear, element);  
                   break;  
             case 2: del_fnode(&front);  
                   break;  
             case 3: display(&front);  
                   break;  
             case 4: break;  
             default: printf("\nWrong choice!! Enter choice again.");  
         }  
     }while(ch!=4);  
 }  
 void ins_rnode(NODE *front, NODE *rear, int ele)  
 {  
     NODE newnode, temp;  
     temp = *front;  
     newnode = (NODE)malloc(sizeof(struct tag));  
     if(newnode == NULL)  
     {  
         printf("\nInsufficient memory.");  
         return;  
     }   
     newnode->data = ele;  
     newnode->link = NULL;  
     if(*front == NULL && *rear == NULL)  
     {  
         *front = newnode;  
         *rear = newnode;  
     }  
     else  
     {  
         while(temp->link != NULL)  
         {  
             temp = temp->link;  
         }  
         temp->link = newnode;  
         *rear = newnode;  
     }  
 }  
 void del_fnode(NODE *front)  
 {  
     NODE c;  
     if(*front == NULL)  
     {  
         printf("\nQueue is empty");  
         return;  
     }  
     c = *front;  
     printf("\nDeleted node: %d\n", c->data);  
     *front = c->link;  
     free(c);  
 }  
 void display(NODE *front)  
 {  
     NODE temp;  
     temp = *front;  
     if(*front == NULL)  
     {  
         printf("\nQueue is empty");  
         return;  
     }  
     printf("\nQueue is: ");  
     while(temp != NULL)  
     {  
      printf("%d ", temp->data);  
         temp = temp->link;  
     }  
 }  

Program to implement dynamically allocated Queue.

Dynamic allocation of memory is different from the static memory allocation. Static memory allocation is where we allocate more memory than required initially. It may be so that we may use the entire allocated memory or fall short of memory or use less memory and hence in any of the above cases memory is not managed properly.
So the solution for such a problem is the method of allocating memory during run time. There are four functions which help us to allocate, reallocate and deallocate memory as per our needs and requirements during run time. They are:
a.) Malloc    [Allocates a single block of memory]
b.) Calloc    [Allocates a contiguous block of memory initially filled with zero's]
c.) Realloc  [Reallocates memory whenever required, may be more or less]
d.) Free      [Deallocates previously allocated memory]

Source Code: 

 #include <stdio.h>  
 #include <stdlib.h>  
 #define realloc(p,n)             // Macro definition for realloc function  
 void insert();  
 void deleteq();  
 void display();  
 int capacity = 1;  
 int rear = -1;  
 int front = 0;  
 int main()  
 {  
     int *p;  
     int choice, ele;  
     p = (int*)malloc(sizeof(int)); //allocating memory to pointer  
     do  
     {  
         printf("\n\nOperations on stack: \n");  
         printf("\n1.) PUSH");  
         printf("\n2.) POP");  
         printf("\n3.) DISPLAY");  
         printf("\n4.) EXIT");  
         printf("\nEnter your choice: ");  
         scanf("%d", &choice);  
         switch(choice)  
         {  
             case 1: printf("\nEnter an element to push: ");  
                   scanf("%d", &ele);  
                   insert(&p, ele);  
                   break;  
             case 2: deleteq(&p);  
                   break;  
             case 3: display(p);  
                   break;  
             case 4: break;  
             default: printf("\nInvalid choice. Enter again...");  
         }  
     }while(choice!=4);  
     free(p);  
 }  
 void insert(int **p, int ele)  
 {  
     if(rear == capacity-1)  //checking if allocated memory is full  
     {    //if full reallocate memory by doubling capacity size  
         capacity*=2;  
         realloc(p, capacity);  
         printf("\nCapacity increased");  
     }  
     rear++;  
     *(*p+rear) = ele;  //storing value in pointer  
 //   printf("\nCapacity: %d", capacity);   remove comment to understand changes in the capacity values  
 }  
 void deleteq(int **p)  
 {  
     if(front > rear)  
     {  
         printf("\nQueue empty");  
     }  
     else  
     {  
         printf("\nDeleted element: %d", *(*p+front));  
         front++;  
         capacity--;  
         realloc(p, capacity);  
 //       printf("\nCapacity: %d", capacity);   remove comment to understand changes in the capacity values  
     }  
 }  
 void display(int *p)  
 {  
     int i;  
     if(front > rear)  
     {  
         printf("\nQueue is empty");  
     }  
     else  
     {  
         printf("\nContents of Queue are: ");  
         for( i=front ;i<=rear ;i++)  
         {  
             printf("%d  ", *(p+i));  
         }  
     }  
 }  

Reversing a Stack using Queue.

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5

struct tag
{
        int a[SIZE];
        int top;
};                                                                 //Structure definition for stack
typedef struct tag stack;


struct tagg
{
        int items[SIZE];
        int rear;
        int front;
};                                                                  //Structure definition for queue
typedef struct tagg QUEUE;


void push();
int pop();
void display();
void rev();                       //Function declarations(parameters not required at declaration)


int main()
{
        int ch, element, dnum;
        stack st;
        st.top= -1;

        do
        {                                                                 //Displaying menu for operations on stack
                printf("\n1.) PUSH");
                printf("\n2.) POP");
                printf("\n3.) DISPLAY");
                printf("\n4.) REVERSE");
                printf("\n5.) EXIT");
                printf("\nEnter your choice: ");
                scanf("%d", &ch);

                switch(ch)
                {
                        case 1: printf("\nEnter element to push: ");
                                    scanf("%d", &element);
                                    push(&st, element);
                                    break;

                        case 2: dnum = pop(&st);
                                    if(dnum != -1)
                                    printf("\nDeleted element: %d", dnum);
                                    break;

                        case 3: display(st);
                                    break;

                        case 4: rev(&st);
                                    break;

                        case 5: break;

                        default: printf("\nWrong choice!! Enter choice again.");
                  }
         }while(ch!=5);

}

void push(stack *s, int ele)
{
        if(s->top == SIZE-1)
        {
                printf("\nStack is overflow");
        }
        else
        {
                (s->top)++;
                s->a[s->top] = ele;;
        }
}

int pop(stack *s)
{
        if(s->top == -1)
        {
                printf("\nStack is underflow");
                return(-1);
        }
        else
        {
                return(s->a[(s->top)--]);
        }
}

void display(stack s)
{
        int i;
        if(s.top == -1)
        {
               printf("\nStack is empty");
        }
        else
        {
                for(i=s.top; i>=0; i--)
                {
                           printf("\n%d", s.a[i]);
                }
         printf("\n");
         }
}

//Function to reverse a stack using queue
void rev(stack *s)
{
        QUEUE q;
        q.rear = -1;
        q.front = 0;

        if(s->top==-1)
        {
                printf("\nStack empty");
                return;
        }

        while((s->top) > -1)
        {
                 q.items[++(q.rear)] = s->a[(s->top)--];
        }

        while(q.front <= q.rear)
        {
                  s->a[++(s->top)] = q.items[(q.front)++];
        }

}

ORDINARY QUEUE:

Queue is data structure in which the first inserted element is the first deleted element. It is also known as a FIFO(First In First Out). The program implementation using structure is as follows.

/*Include the necessary header files(stdio.h, stdlib.h, conio.h)*/

#define QSIZE 5 //Maximum elements in Queue

struct tag //structure definition

{

int items[QSIZE];

int rear;

int front;

};

typedef struct tag QUEUE;

void insert();

int Delete();

void display(); //Function Prototypes

int main()

{

QUEUE q;

int element, dnum, choice;

q.rear = -1;

q.front = 0;

do

{

printf("\n\nOperations on Ordinary Queue: ");

printf("\n\n1.) INSERT");

printf("\n\n2.) DELETE");

printf("\n\n3.) DISPLAY");

printf("\n\n4.) QUIT");

printf("\n\nEnter your choice: ");

scanf("%d", &choice);

switch(choice)

{

case 1: printf("\nEnter the element into queue: ");

scanf("%d", &element);

insert(&q, element); //Function call by reference

break;

case 2: dnum = Delete(&q); // Function call by reference

if(dnum != -1)

{

printf("\nDeleted element: %d", dnum);

}

break;

case 3: display(q); //Function call by value

break;

case 4: break;

default: printf("\nInvalid choice! Enter again.");

}

}while(choice!=4);

getch();

}

//Function to insert elements into the queue

void insert(QUEUE *q, int element)

{

if(q->rear == QSIZE - 1)

{

printf("\nQueue is full.");

return;

}

else

{

(q->rear)++;

q->items[q->rear] = element;

}

}

//Function to delete an element from the front of queue.

int Delete(QUEUE *q)

{

if(q->front > q->rear)

{

printf("\nQueue is empty.");

return(-1);

}

else

{

return(q->items[(q->front)++]);

}

}

//Function to display the contents of queue from front to rear.

void display(QUEUE q)

{

int i;

if(q.front > q.rear)

printf("\n\nQueue empty.");

else

{

printf("\nQueue is: \n\n");

for(i=q.front; i<=q.rear; i++ )

{

printf("%d ", q.items[i]);

}

}

}