 |
| DYNAMIC QUEUE using DYNAMIC STACK |
//TITLE DYNAMIC QUEUE by modifying DYNAMIC STACK
//AUTHOR VINAY CHOUDHARY
//DATE 26 OCT 2009
//This is a C program for DYNAMIC queue using stack functions
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define NUM 5
/*
*pos : we will use "pos" to point to top element in array, used in pop, value updates in push.
*arr : pointer to array which is allocated memory at run-time.Can be replaced by static array. Just comment out part where we are using malloc() for array in push().
num : "num" tells how much data is present.
*next : "*next" is pointer to next stack element.
*/
typedef struct blk{
int *pos;
int *arr;
int num;
struct blk *next;
}stack;
/*
PUSH FUCTION : we pass head as pointer and data here. Head is stored in backup for returning new value when stack is created for first time, else it contains old head value.
In loop above we check if head exists and go to last stack,which has next == null. There we check if head(stack) exists or not or if array is full for current last stack. In both cases we create a new stack as temp. temp points to NULL, since it will be last stack and has no data at present so num = 0 for temp and make pos to point to base of arr.
Now if stack doesnt exist then assign temp as head of stack since we will add data to it. Also since this is new head, store it in backup for returning purpose, else if array has filled for current last stack attach newly created temp stack to stack by storing its address in next of curent stack and make head same as temp since we add data to newly created stack(temp) using head(head=temp).
Then add data and increment index and return backup
*/
stack* push(stack *head,int data)
{
stack* backup,*temp;
for(backup = head;head && head->next != NULL;head = head->next);
if(head == NULL || head->num == NUM)
{
temp = (stack *)malloc(1*sizeof(stack));
temp->arr = (int*)malloc(NUM*sizeof(int));
temp->next = NULL;
temp->num = 0;
temp->pos = temp->arr;
if(backup == NULL)
backup = head = temp;
else if(head->num == NUM)
head = head->next = temp;
}
head->arr[head->num++] = data
return backup;
}
//POP FUNCTION: we pass head as pointer and data as pointer here.
//save backup as head;
//Read data at pos. pos is where queue starts
//since data at pos is read, now we will read next element next time so //pos++
//and take data in pointer passed, which is collected in main
//here we check if array of current last stack has become empty, if so
//second last stack, use temp to make second last stack to point to NULL. //Hence stack
//pointed by temp is now the last stack. Free memory of stack to be deleted.
//NOTE THAT stack is deleted only when no data is left
//whether updated or not return backup which is collected as head in main //program
stack* pop(stack *head,int *data)
{
stack* backup,*temp=NULL;
backup = head;
*data = *head->pos;
head->pos++;
--head->num;
if(head->num == 0)
{
temp = head->next;
free(head->arr);
free(head);
backup = temp;
}
return backup;
}
void display(stack *head)
{
int *p,i;
printf("\nCURRENT STACK: ");
if(!head)
printf("DOESN'T EXIST");
while(head)
{
for(i=0,p=head->pos;i<head->num;p++,i++)
printf("%d ",*p);
head = head->next;
}
}
void main()
{
stack *head=NULL;
int data,run=1;
char ch;
while(run)
{
display(head);
printf("\n\nWHAT TO DO ?");
printf("\n1. PUSH\n2. POP\n3. DISPLAY\n4. EXIT\nYOUR OPTION : ");
scanf(“%c”,&ch);
switch(ch)
{
case '1':
{
printf("Enter number to push: ");
scanf(“%d”,&data);
head = push(head,data);
break;
}
case '2':
{
if( (head) )
{
head = pop(head,&data);
printf("DATA POPPED: %d",data);
}
else
printf("CAN'T POP: NO DATA IN STACK");
break;
}
case '3':
{
display(head);
break;
}
case '4':
{
run = 0;
break;
}
default:
{
printf("\nENTER VALID OPTION");
break;
}
}
}
printf("\n\n");
}
