<WRAP centeralign round graybg box 96%>
<WRAP muchbigger>QUEUE DATA STRUCTURE LIBRARY</WRAP>
<WRAP bigger>John T. Rine</WRAP>
<WRAP bigger>11/01/2011</WRAP>
</WRAP>
======Objectives======
My queue library is available for download from: My library is available at: http://lab46.corning-cc.edu/~jr018429/queue.zip\\
\\
The main objectives of this project are to learn about queue data structures, and create a functioning queue library in C. What are queue data structures used for and how are they implemented? These are the questions that I will attempt to answer as this project develops.\\
======Prerequisites======
In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:
  * understand and use the C/C++ programming language
  * understand and use functions
  * understand and use pointers in general
  * understand and use pointers to pointers
  * understand and use structs
  * understand and use pointers (referencing and dereferencing) to structures
  * understand and use pointer to pointers (refeencing and dereferencing) to structures
  * understand and use malloc() to dynamically allocate memory
  * understand and use free() to deallocate memory
  * understand the linked data structures (in relation to queues) in general
  * know how to create and use a static library
  * know how to build a queue library using the items listed above

======Background======
A data structure holds data and provides operations to the user that can be performed on the data it contains. A queue is one type of data structure; it is a (FIFO) first in, first out data structure. 
======Scope======
Queue Library implementation\\
The queue Library project scope is available at:\\
http://lab46.corning-cc.edu/haas/fall2011/data/projects/queuelib\\
Linked Lists provide a foundation for dynamic structures. Further exploring Data Structures, we find that particular manipulations of these structures enable interesting possibilities for computing. Queue are another such iteration of these Data Structures we are exploring this semester.
An excellent exploration with Queues would be to extend your Linked List Library with Queue Functionality (or to create a new Queue library that depends on the Linked List library).\\ 
To create a Queue library, you may want to have the following functions:\\ 
  * create: generate a new queue
  * enqueue: add a new node to the beginning of the queue
  * dequeue: remove the node from the end of the end and return it
  * isEmpty: is the queue in an empty condition?
  * delete: delete and de-allocate the queue
  * copy: duplicate the existing queue
A queue can be relatively infinite (so long as available resources are present for allocation) or fixed in size.\\ 
Your queue implementation should be able to handle/recognize the following situations:\\ 
  * unlimited queue size
  * fixed queue size (also known as a buffer)
  * buffer overrun
  * buffer underrun
Implementing this functionality into a library will enable you to utilize it in additional projects. 

======Attributes======
The course requirement for Data Structures projects are listed at:\\
http://lab46.corning-cc.edu/haas/fall2011/data/projects 
This project has the following project attributes described on that page:
^Attribute^Qty Needed^Description^
|Pointers|8|Indirection/dereferencing are demonstarted|
|malloc/new|4|Utilization of dynamic memory allocation|
|Queue|4|Implementation/utilization of a queue|
|Libraries|4|Implementation/utilization of non-core libc library| 
\\
This project, therefore, is eligible for 20 attributes total, however, only 6 of these are achieveable per project, so project far exceeds the minimum attribute requirements.
======Code======
My library is composed of the following files and functions:\\
**queue.h**\\
queue.h is the header file for the queue library. It should be included in any .c library files whose function prototypes have been added to it. Also, it must be added to any programs utilizing the library's functions.\\
Example code:\\
<file h queue.h>
//queue.h
//John T. Rine
//November 3, 2011

#ifndef _QUEUE_H
#define _QUEUE_H

#include<stdlib.h>
#include<stdio.h>

struct Node
{
	int data;
	struct Node * prev;
	struct Node * next;
};

typedef struct Node node;

//copyQueue.c
void copyQueue(node *head, node **copyHead, node **copyTail);

//isEmpty.c
int isEmptyTail(node *);
int isEmptyHead(node *);

//createFixedQueue.c
void createFixedQueue(node **, node **, int);

//listQueueSize.c
int listQueueSizeHead(node *);
int listQueueSizeTail(node *tail);

//enQueue.c
void enQueue(node **, node **, int);

//deQueue.c
int deQueue(node **, node **);

//destroyFixedQueue.c
void destroyFixedQueueHead(node **, node **);
void destroyFixedQueueTail(node **, node **);


#endif
</file>
\\
**copyQueue.c**\\
copyQueue.c contains only one function, copyQueue. copyQueue takes as its parameters head, the head of the queue to be copied, copyHead and copyTail;  copyHead and copyTail become the head and tail of the copied queue.\\

<file c copyQueue.c>
//copyQueue.c
//John T. Rine
//November 3, 2011

#include<stdio.h>
#include<stdlib.h>
#include"queue.h"

void copyQueue(node *head, node **copyHead, node **copyTail)
{
	node *new, *temp;
	new = *copyHead = *copyTail = temp = NULL;
	temp = head;
	while(temp != NULL)
	{
		if (*copyHead == NULL)
		{
			*copyHead = (node *) malloc(sizeof(node));
			*copyTail = *copyHead;
			(*copyHead)->prev = NULL;
			(*copyHead)->next = NULL;
			(*copyHead)->data = temp->data;
		}
		else
		{
			new = (node *) malloc(sizeof(node));
			new->prev = *copyTail;
			new->next = NULL;
			(*copyTail)->next = new;
			*copyTail = new;
			(*copyTail)->data = temp->data;
		}
		temp = temp->next;
	}
}
</file>
\\
**createFixedQueue.c**\\
createFixedQueue.c contains one function, createFixedQueue. This function takes three parameters; head, tail, and elements. head and tail become the head and the tail of the new queue, whereas elements is the size of the new queue.\\

<file c createFixedQueue.c>
//createFixedQueue.c
//John T. Rine
//November 3, 2011

#include<stdlib.h>
#include<stdio.h>
#include"queue.h"

void createFixedQueue(node **head, node **tail, int elements)
{
	int i;
	node *new;
	new = NULL;
	*head = *tail = NULL;

	for(i = 1; i<=elements; i++)
	{
		if (*head == NULL)
		{
			*head = (node *) malloc(sizeof(node));
			*tail = *head;
			(*head)->prev = NULL;
			(*head)->next = NULL;
		}
		else
		{
			new = (node *) malloc(sizeof(node));
			new->prev = *tail;
			new->next = NULL;
			(*tail)->next = new;
			*tail = new;
		}
	}
}
</file>
\\
**deQueue.c**\\
deQueue.c contains one function for dequeuing or removing data from a queue.\\
<file c deQueue.c>
//deQueue.c
//John T. Rine
//November 3, 2011

#include"queue.h"
#include<stdio.h>
#include<stdlib.h>

int deQueue(node **head, node **tail)
{
	int data = 0;
	node *temp = NULL;
	//temp = *tail;
	temp = *head;
	if(*head != NULL && *tail != NULL)
	{
		if (temp == *tail)
		{
			temp->prev = NULL;
			temp->next = NULL;
			data = temp->data;
			free(temp);
			*head = *tail = NULL;
		}
		else
		{
			temp->next->prev = NULL;
			*head = temp->next;
			temp->next = NULL;
			data = temp->data;
			free(temp);
		}
	}
	else
	{
		printf("No queue to dequeue...\n");
		exit(1);
	}
	return data;
}
</file>
\\
**destroyFixedQueue.c**\\
destroyFixedQueue.c contains two functions for destroying a queue. destroyFixedQueueHead destroys a queue from its head; destroyFixedQueueTail destroys a queue from its tail.\\

<file c destroyFixedQueue.c>
//destroyFixedQueue.c
//John T. Rine
//November 3, 2011

#include<stdlib.h>
#include<stdio.h>
#include"queue.h"

void destroyFixedQueueHead(node **head, node **tail)
{
	node *temp;
	node *temp2;
	temp = NULL;
	temp2 = NULL;
	temp = *head;
	while(temp != NULL)
	{
		temp2 = temp->next;
		if (temp->prev != NULL) temp->prev = NULL;
		if (temp->next != NULL) temp->next = NULL;
		free(temp);
		temp = temp2;	
	}
	*head = *tail = NULL;
}

void destroyFixedQueueTail(node **head, node **tail)
{
	node *temp;
	node *temp2;
	temp = NULL;
	temp2 = NULL;
	temp = *tail;
	while(temp != NULL)
	{
		temp2 = temp->prev;
		if (temp->prev != NULL) temp->prev = NULL;
		if (temp->next != NULL) temp->next = NULL;
		free(temp);
		temp = temp2;	
	}
	*head = *tail = NULL;
}
</file>
\\
**enQueue.c**\\
enQueue.c contains one function for putting into queue.\\
<file c enQueue.c>
//enQueue.c
//John T. Rine
//November 3,, 2011

#include<stdio.h>
#include<stdlib.h>
#include"queue.h"

void enQueue(node **head, node **tail, int data)
{
	int i;
	node *temp, *temp2;
	temp = temp2 = NULL;

	temp = *head;

	while(temp != NULL)
	{
		temp = temp->next;
	}

		if (*head == NULL)
		{
			*head = (node *) malloc(sizeof(node));
			*tail = *head;
			(*head)->prev = NULL;
			(*head)->next = NULL;
			(*head)->data = data;
		}
		else// if (*tail == temp)
		{
			temp2 = (node *) malloc (sizeof(node));
			temp2->prev = *tail;
			temp2->next = NULL;
			(*tail)->next = temp2;
			*tail = temp2;
			(*tail)->data = data;
		}
}
</file>
\\
**isEmpty.c**\\
isEmpty.c contains two functions, isEmptyTail and isEmptyHead, to test a queue for to see if it is empty. If the queue is empty, both return true, otherwise they returns false.\\
<file c isEmpty.c
//isEmpty.c
//John T. Rine
//November 3, 2011

#include<stdio.h>
#include<stdlib.h>
#include"queue.h"

int isEmptyTail(node *tail)
{
	if (tail == NULL) return 1;
	else return 0;
}

int isEmptyHead(node *head)
{
	if (head == NULL) return 1;
	else return 0;
}
</file>
\\
**listQueueSize.c**\\
listQueueSize.c contains two functions for returning the size of a queue. listQueueSizeHead takes head as its parameter; listQueueSizeTail takes tail as its parameter.\\
<file c listQueueSize.c>
//listQueueSize.c
//John T. Rine
//October 12, 2011


#include<stdlib.h>
#include<stdio.h>
#include"queue.h"

int listQueueSizeHead(node *head)
{
	int size = 0;
	while (head != NULL)
	{	
		head = head->next;
		size++;
	}
	return size;
}

int listQueueSizeTail(node *tail)
{
        int size = 0;
        while (tail != NULL)
        {
                tail = tail->prev;
                size++;
        }
        return size;
}
</file>
\\
**queueTest.c**\\
queueTest.c is a program used to test the queue library.\\
<file c queueTest.c>
//queueTest.c
//Author: John T. Rine
//Date: November 3, 2011


#include"queue.h"

int main(int argc, char **argv)
{
	int i, data;
	node *head, *tail, *temp, *copyHead, *copyTail;
	head = tail = temp = copyHead = copyTail = NULL;
	
	printf("Head is = 0x%x; Tail is = 0x%x\n", head, tail);
	printf("\nCreating a fixed size queue of 10 nodes...\n");
	createFixedQueue(&head, &tail, 10);
	printf("\nHead is = 0x%x; Tail is = 0x%x\n", head, tail);
	printf("\nSize of the list is: %d\n", listQueueSizeTail(tail));
	
	i = 10;
	temp = tail;
	while(temp != NULL)
	{
		temp->data = i;
		i--; 
		temp = temp->prev;
	}
	if(isEmptyTail(tail)) printf("\nQueue is empty!\n");
	else printf("\nQueue is not empty!\n");

	temp = tail;
	while(temp != NULL)
	{
		printf("\nThis node contains %d\n", temp->data);
		temp = temp->prev;
	}
	printf("\nMaking a copy of the queue...\n");
	copyQueue(head, &copyHead, &copyTail);
	printf("\nDestroying the first Queue...\n");
	destroyFixedQueueTail(&head, &tail);
	if(isEmptyTail(tail)) printf("\nQueue is empty!\n");
	else printf("\nQueue is not empty!\n");
	printf("\nHead is = 0x%x; Tail is = 0x%x\n", head, tail);
	printf("\nPrinting values of copy of queue...\n");
	temp = copyTail;
	while(temp != NULL)
	{
		printf("\nThis node contains %d\n", temp->data);
		temp = temp->prev;
	}
	if(isEmptyTail(copyTail)) printf("\nCopy of queue is empty!\n");
	else printf("\nCopy of queue is not empty!\n");
	printf("\nDestroying copy of the queue...\n");
	destroyFixedQueueTail(&copyHead, &copyTail);
	if(isEmptyTail(copyTail)) printf("\nCopy of queue is empty!\n");
	else printf("\nCopy of queue is not empty!\n");

	printf("\nStarting a new queue using enqueue and a dequeue...\n");
	printf("\nEnter the number of data to push onto the queue...\n");
	scanf("%d", &i);

	int ii;
	ii = i;
	head = tail = NULL;
	for(;i > 0; i--)
	{
		printf("\nEnter the value to be pushed onto the queue...\n");
		scanf("%d", &data);
		enQueue(&head, &tail, data);
	}
	for(;ii > 0; ii--)
	{
		printf("Data = %d\n", deQueue(&head, &tail));
	}
	
	getchar();
}
</file>
\\
**makeQueue.bat**\\
The Windows batch file makeQueue.bat automates, manufacture of all of the .o files, the creation of the static library file, compiling, linking, and execution of queueTest, the test file.\\
Example code:\\
<file bat makeQueue.bat>
el *.o
del *.exe
del *.a
gcc -c copyQueue.c -o copyQueue.o
gcc -c createFixedQueue.c -o createFixedQueue.o
gcc -c deQueue.c -o deQueue.o
gcc -c destroyFixedQueue.c -o destroyFixedQueue.o
gcc -c enQueue.c -o enQueue.o
gcc -c isEmpty.c -o isEmpty.o
gcc -c listQueueSize.c -o listQueueSize.o
ar rcs libQueuedll.a *.o

ar rcs libQueuedll.a *.o
gcc -I. queueTest.c -o queueTest libQueuedll.a

queueTest

pause
</file>
\\
**makeQueue.sh**\\
The bash shell script file makeQueue.sh automates the manufacture of all of the .o files, the creation of the static library file, compiling, linking and execution of queueTest, the test file.\\
Example code:\\
<file sh makeQueue.sh>
#!/bin/bash
rm *.o
rm queueTest

gcc -c copyQueue.c -o copyQueue.o
gcc -c createFixedQueue.c -o createFixedQueue.o
gcc -c deQueue.c -o deQueue.o
gcc -c destroyFixedQueue.c -o destroyFixedQueue.o
gcc -c enQueue.c -o enQueue.o
gcc -c isEmpty.c -o isEmpty.o
gcc -c listQueueSize.c -o listQueueSize.o

ar rcs libQueuedll.a *.o
gcc -I. queueTest.c -o queueTest libQueuedll.a

./queueTest
</file>
======Execution======
** Execution of makeQueue.bat (compilation, creation of a static library, linking, and execution of the queueTest test program on a Windows machine**
<cli>

C:\Documents and Settings\rinejt\Desktop\queue>del *.o

C:\Documents and Settings\rinejt\Desktop\queue>del *.exe
Could Not Find C:\Documents and Settings\rinejt\Desktop\queue\*.exe

C:\Documents and Settings\rinejt\Desktop\queue>del *.a

C:\Documents and Settings\rinejt\Desktop\queue>gcc -c copyQueue.c -o copyQueue.o


C:\Documents and Settings\rinejt\Desktop\queue>gcc -c createFixedQueue.c -o crea
teFixedQueue.o

C:\Documents and Settings\rinejt\Desktop\queue>gcc -c deQueue.c -o deQueue.o

C:\Documents and Settings\rinejt\Desktop\queue>gcc -c destroyFixedQueue.c -o des
troyFixedQueue.o

C:\Documents and Settings\rinejt\Desktop\queue>gcc -c enQueue.c -o enQueue.o

C:\Documents and Settings\rinejt\Desktop\queue>gcc -c isEmpty.c -o isEmpty.o

C:\Documents and Settings\rinejt\Desktop\queue>gcc -c listQueueSize.c -o listQue
ueSize.o

C:\Documents and Settings\rinejt\Desktop\queue>ar rcs libQueuedll.a *.o

C:\Documents and Settings\rinejt\Desktop\queue>ar rcs libQueuedll.a *.o

C:\Documents and Settings\rinejt\Desktop\queue>gcc -I. queueTest.c -o queueTest
libQueuedll.a

C:\Documents and Settings\rinejt\Desktop\queue>queueTest
Head is = 0x0; Tail is = 0x0

Creating a fixed size queue of 10 nodes...

Head is = 0x3e2430; Tail is = 0x3e2508

Size of the list is: 10

Queue is not empty!

This node contains 10

This node contains 9

This node contains 8

This node contains 7

This node contains 6

This node contains 5

This node contains 4

This node contains 3

This node contains 2

This node contains 1

Making a copy of the queue...

Destroying the first Queue...

Queue is empty!

Head is = 0x0; Tail is = 0x0

Printing values of copy of queue...

This node contains 10

This node contains 9

This node contains 8

This node contains 7

This node contains 6

This node contains 5

This node contains 4

This node contains 3

This node contains 2

This node contains 1

Copy of queue is not empty!

Destroying copy of the queue...

Copy of queue is empty!

Starting a new queue using enqueue and a dequeue...

Enter the number of data to push onto the queue...
5

Enter the value to be pushed onto the queue...
1

Enter the value to be pushed onto the queue...
2

Enter the value to be pushed onto the queue...
3

Enter the value to be pushed onto the queue...
4

Enter the value to be pushed onto the queue...
5
Data = 1
Data = 2
Data = 3
Data = 4
Data = 5

C:\Documents and Settings\rinejt\Desktop\queue>pause
Press any key to continue . . .
</cli>
\\
** Execution of makeQueue.sh (compilation, creation of a static library, linking, and execution of the queueTest test program on a Linux machine**
<cli>
lab46:~/src/data/queue$ ./makeQueue.sh
Head is = 0x0; Tail is = 0x0

Creating a fixed size queue of 10 nodes...

Head is = 0x8c3010; Tail is = 0x8c3130

Size of the list is: 10

Queue is not empty!

This node contains 10

This node contains 9

This node contains 8

This node contains 7

This node contains 6

This node contains 5

This node contains 4

This node contains 3

This node contains 2

This node contains 1

Making a copy of the queue...

Destroying the first Queue...

Queue is empty!

Head is = 0x0; Tail is = 0x0

Printing values of copy of queue...

This node contains 10

This node contains 9

This node contains 8

This node contains 7

This node contains 6

This node contains 5

This node contains 4

This node contains 3

This node contains 2

This node contains 1

Copy of queue is not empty!

Destroying copy of the queue...

Copy of queue is empty!

Starting a new queue using enqueue and a dequeue...

Enter the number of data to push onto the queue...
5

Enter the value to be pushed onto the queue...
1

Enter the value to be pushed onto the queue...
2

Enter the value to be pushed onto the queue...
3

Enter the value to be pushed onto the queue...
4

Enter the value to be pushed onto the queue...
5
Data = 1
Data = 2
Data = 3
Data = 4
Data = 5
lab46:~/src/data/queue$
</cli>
\\
**Addition and committal of the queue library and test file to the Subversion repository.**\\
<cli>
lab46:~/src/data$ svn add queue
A         queue
A         queue/createFixedQueue.c
A         queue/deQueue.c
A         queue/copyQueue.c
A         queue/destroyFixedQueue.c
A         queue/isEmpty.c
A         queue/enQueue.c
A         queue/listQueueSize.c
A         queue/makeQueue.bat
A         queue/queue.h
A         queue/queueTest.c
A         queue/makeQueue.old
A         queue/makeQueue.sh
A  (bin)  queue/queueTest
lab46:~/src/data$ svn commit -m "Added and committed queue files -John T. Rine"
Sending        data/Stack/libdll.a
Adding         data/queue
Adding         data/queue/copyQueue.c
Adding         data/queue/createFixedQueue.c
Adding         data/queue/deQueue.c
Adding         data/queue/destroyFixedQueue.c
Adding         data/queue/enQueue.c
Adding         data/queue/isEmpty.c
Adding         data/queue/listQueueSize.c
Adding         data/queue/makeQueue.bat
Adding         data/queue/makeQueue.old
Adding         data/queue/makeQueue.sh
Adding         data/queue/queue.h
Adding  (bin)  data/queue/queueTest
Adding         data/queue/queueTest.c
Transmitting file data ..............
Committed revision 24.
lab46:~/src/data$
</cli>
\\
**Committal of queue library files after cleaning them up**
<cli>
lab46:~/src/data/queue$ svn commit -m "Cleaned up queue library -John T. Rine"
Sending        queue/deQueue.c
Sending        queue/queueTest
Sending        queue/queueTest.c
Transmitting file data ...
Committed revision 25.
lab46:~/src/data/queue$
</cli>
======Reflection======
Since I was successful at getting linked lists and stacks to work using doubly linked lists, my confidence level was much higher going into this project. It was good to use linked nodes again but this time in a slightly different usage as repetition helps engrain the concepts into one's mind. It was also good to once again create a static library of queue functions. This library could be used later in another project.

======References======
  * http://www.dtic.upf.edu/~rramirez/TA/stack.pdf (Stacks, Queues, and Linked Lists)
  * http://www.cs.ucf.edu/courses/cop3502h.02/linklist3.pdf (Application of linked lists, stacks, and queues)
  * http://www.ece.utexas.edu/~adnan/360C/stacks-queues-lists.pdf