Homework 9

Problem Statement:

Use the program on queues we discussed in class that stores an integer in each node. Write a function that given a queue with capacity of 40 nodes, it splits the queue to two queues of 20 nodes capacity.

So if the initial queue is the following:
20 21 34 56 4 5 2 7 80 34 23 26 21 35 44 78 67 55 5,
it returns:
20 34 4 2 80 23 21 44 67 5 and its size 10, and
21 56 5 7 34 26 35 78 55 and its size 9.

Then write a second function that traverses each of the queues and prints the contents in a row in FIFO order.

Solution

The initial queue has capacity 40 and size 19. We wish to split it in such a way so that the first queue contains the numbers in the even position and the second queue contains the numbers in the odd positions. For this particular homework I'm using the C implementation given by the instructor in class. That's because of how the problem has been worded.

#include <iostream>
using namespace std;

typedef struct queue 
{
	int front, rear; //indices for which entry is the front and rear of the queue
	int size;
	unsigned capacity;
	int * array;
} queue_t;

queue_t* createQueue(int cap) //function to create an empty queue with a given capacity
{
	queue_t* q = (queue_t*) malloc(sizeof(queue_t));
	q->array = (int*) malloc(cap * sizeof(int));
	q->capacity = cap;
	q->front = 0;
	q->size = 0;
	q->rear = 0;
	return q;
}

void enqueue(queue_t * q, int x) 
{
	if(q->capacity==q->size) 
	{
		cout<<"Queue is full";
		return;
	}
	q->array[q->rear] = x;
	q->rear = (q->rear+1)%q->capacity;
	q->size++;
}

void splitQueue(queue_t* q, queue_t* split1, queue_t* split2) 
{
	for (int i=0;i<q->size;i++) 
	{
		if(i%2)
			enqueue(split2, q->array[i]);
		else
			enqueue(split1, q->array[i]);
	}
}

void printQueue(queue_t* q)
{
	cout<<"Queue of size: "<<q->size<<endl;
	for(int i = q->front; i<q->rear; i=(i+1)%q->capacity)
	{
		cout<<q->array[i]<<"->";
	}
	cout<<"end\n";
}

int main()
{
	int capacity = 40;
	int a[] = {20,21,34,56,4,5,2,7,80,34,23,26,21,35,44,78,67,55,5};
	
	queue_t* initialQueue = createQueue(capacity);
	for(int i=0; i<19; i++)
		enqueue(initialQueue,a[i]);
	
	printQueue(initialQueue);
	
	queue_t* split1 = createQueue(capacity/2);
	queue_t* split2 = createQueue(capacity/2);
	
	splitQueue(initialQueue,split1,split2);
	
	printQueue(split1);
	printQueue(split2);
	
	return 0;
}