======Project: Queue Library Implementation======

A project for Data Structures by Brad Hammond during the Fall of 2011.



=====Objectives=====
Implement a queue data structure based on a doubly linked list to gain a better understanding of how a queue is implemented in memory.

=====Prerequisites=====
In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

  * understand pointers
  * understand structs
  * understand malloc()
  * ability to create a linked data structure

=====Background=====
The idea behind this project is to gain a better understanding of how a queue data structure is implemented in computer memory. A queue is an abstract data type that can be based on either a linked list or an array. A queue is considered to be a first in first out data structure or FIFO. Like a stack, it has a limited amount of operations that can be performed on it: enqueue, dequeue, and front. Enqueue will add a value to the back of the queue. Dequeue will remove a value from the front of the queue. And front will return the value from the front of the queue but will not remove the value.

=====Attributes=====

  * pointers: pointers are at the heart of dynamic structures.
  * malloc/new: dynamic memory allocation.
  * linked lists: this code is going to implement linked lists.
  * doubly linked lists: not only is the code implementing a linked list, it is implementing doubly linked lists.
  * libraries: this code will be part of a library that can be reused in other projects

=====Code=====

<code c>
#include "List.h"
#define NULL 0

int empty(List* q)
{
	if (listLength(q) == 0)
		return 1;
	else
		return 0;
}

int front(List *q)
{
	int val;
	
	if (q -> first == NULL)
		return -1;

	val = getValue(q, listLength(q) - 1);

	return val;
}

int enqueue(List *q, int val)
{
	if (q -> first == NULL)
		appendToList(q, val);
	else
		insertInList(q, 0, val);
	
	return 0;
}

int dequeue(List *q)
{
	int val;

	if (q -> first == NULL)
		return -123456789;
	
	val = getValue(q, listLength(q) - 1);
	deleteNode(q, listLength(q) - 1);

	return val;
}

</code>

<code c>
#ifndef _QUEUE
#define _QUEUE

//Checks whether or not the queue is empty
//Returns 1 if true 0 if false.
int empty(List*);

//Returns the value at the front of the queue
//without removing it from the queue. Upon
//success returns the value at the front of 
//the queue or a -1 upon failure.
int front(List*);

//Adds a value to the back of the queue. Returns 
//a value of 0.
int enqueue(List*, int);

//Returns and removes a value from the front of 
//the queue. If the queue is NULL a large negative
//value is returned otherwise the value at the front
//of the queue is returned.
int dequeue(List*);

#endif
</code>
=====Execution=====
Again, if there is associated code with the project, and you haven't already indicated how to run it, provide a sample run of your code:

<cli>
brad@dhcp-181:/media/06F6-9DC2/Notepad++/Programs/LinkedList$ g++ -o qTest LinkedList.c Queue.c qTest.c
brad@dhcp-181:/media/06F6-9DC2/Notepad++/Programs/LinkedList$ ./qTest
Enter a value (-1 to exit): 2
Enter a value (-1 to exit): 3
Enter a value (-1 to exit): 4
Enter a value (-1 to exit): 5
Enter a value (-1 to exit): 6
Enter a value (-1 to exit): 7
Enter a value (-1 to exit): -1
Values enqueued.
Dequeueing items...
2, 3, 4, 5, 6, 7, 
brad@dhcp-181:/media/06F6-9DC2/Notepad++/Programs/LinkedList$ 

</cli>

=====Reflection=====
Comments/thoughts generated through performing the project, observations made, analysis rendered, conclusions wrought. What did you learn from doing this project? 

Much like with the stack most of the work here was done within the linked list library. The only major difference between the queue library and the stack library is the need to implement FIFO rather than LIFO. Also, like with the stack library the compiler was not recognizing NULL so I had to define it myself within the header file. 

=====References=====
In performing this project, the following resources were referenced:

  * [[http://en.wikipedia.org/wiki/Queue_%28abstract_data_type%29]]
  * [[http://lab46.corning-cc.edu/opus/fall2011/bh011695/start#queuesarray_based_vs_linked_list_based]]
  * [[http://lab46.corning-cc.edu/user/bh011695/portfolio/libdll]]

Generally, state where you got informative and useful information to help you accomplish this project when you originally worked on it (from Google, other wiki documents on the Lab46 wiki, etc.)