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

A project for Data Structures by Dave Schoeffler during the Fall 2011 semester.

This project was begun on November 8th and was completed on November 11th.
=====Objectives=====
The purpose of this project is to explore the nature of queues through their use in various functions. This project will also require an understanding of malloc(), structs, pointers.
 and passing them to functions. The heart of queue is a linked list. An understanding of how linked lists work will also be vital.The understanding of the preceding will allow me to successfully create a queue data structure.

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

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

=====Background=====
The point of this project is to implement a queue[[http://lab46.corning-cc.edu/opus/fall2011/dschoeff/start#queue]] that will store characters.

A queue is a data structure that is made up of a group of "nodes" that store data. The heart of a queue is a linked list. A queue in fact is a linked list of nodes that contain data. The real difference between these two data structures is that a queue is limited in what operations can be performed on the list. A queue is a **FIFO** data structure meaning that the first value that is added to the queue will be the first value removed. Think of this as a line at the bank where once you enter the line the only way to get out is at the end. There is no leaving the line from the entrance. The names for adding a node to the beginning of a queue and removing a node from the end of the queue are known as enqueue[[http://lab46.corning-cc.edu/opus/fall2011/dschoeff/start#enqueuing]] and dequeue[[http://lab46.corning-cc.edu/opus/fall2011/dschoeff/start#dequeuing]] respectively. 

This project will implement a queue that stores character data. It will give the user the functionality to create a queue and enqueue and dequeue nodes from the queue. These functions will be stored in a library.

=====Scope=====
To better utilize the functionality of the queues we've been studying in class, a personal implementation for use as a library will be undertaken for use in other projects and activities this semester.

A library implementation will be created which has the following functions:

  * **create**: create a queue data structure
  * **enqueue**: enqueue a node to the queue
  * **dequeue**: dequeue a node from the queue


=====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
  * queues: this code will implement the use of queues

=====Code=====

====Header File====
<code c>
/****************************************************************
* Header file. This includes the function protypes for          *
* the queue manipulation functions.                             *                                                          
****************************************************************/
#ifndef _QUEUE_H
#define _QUEUE_H
#include "linkedlist.h"
void enqueue(Node** start, Node** end, int, char ch);
char dequeue(Node** start, Node** end, int index);
#endif
</code>

====Functions====
===enqueue.c===
<code c>
//compile with: gcc -c enqueue.c                                                          
//
//Function enqueue() enqueues anode to the queue. If there is no queue in existence
//it will create one. This function is almost exactly like the insert function in my 
//doubly linked library.

#include "queue.h"
#include <stdlib.h>
void enqueue(Node** start, Node** end, int index, char ch) 
{

   int i;
   Node* tmp;
   Node* tmp2;
   tmp  = *start;

   if (*start == NULL) // if our queue is empty
   {   
      (*start) = (Node *) malloc (sizeof(Node));
      (*end) = tmp = *(start);
      (*start) -> prev = NULL;
      (*end) -> prev = NULL;
      (*start) -> value = ch; 
   }   
   else// we are enqueing a node
   {   
      tmp2 = (Node *) malloc (sizeof(Node));
      tmp2 -> next = (*start); // point new node's next at (*start)
      (*start) -> prev = tmp2; // point (*start)'s prev at tmp2
      (*start) = (*start) -> prev; // move (*start) to new node
      (*start) -> value = ch; // put value in node
   }   
}
</code>
===dequeue.c===
<code c>
//compile with: gcc -c dequeue.c                                                          
//
// Function dequeue() removes a node from a given queue and frees the
// memory for that node
#include "linkedlist.h"
#include <stdlib.h>
char dequeue(Node** start, Node** end, int index)
{
   int i;
   char ch; 
   Node* tmp;
   tmp = *start;
   if((*start) != NULL)
   {   
      // Move tmp to exact node we wish to delete
      for( i=0; i<index; i++)
      {   
         tmp = tmp -> next;
      }   
      ch = tmp -> value;
      if ((tmp != *start) && (tmp != *end))
      {   
         tmp -> next -> prev = tmp -> prev;
         // The node after points to the node before tmp
         tmp -> prev -> next = tmp -> next;
         // Now, the now before points to the node after tmp
         tmp -> prev = NULL;
         tmp -> next = NULL;
         // tmp is now disconnected from the queue
         free (tmp); // deallocate the node tmp is pointing to
      }   
      else if (*start == *end) // queue is only a single node
      {   
         free(tmp);
         (*start) = (*end) = NULL;
      }   
      else if (tmp == *start)
      {
         tmp -> next -> prev = NULL;
         // The node following tmp is no longer pointing to us
         (*start) = (*start) -> next;
         tmp -> next = NULL; // Disconnect tmp from the queue
         free(tmp); // deallocate the node tmp is pointing to
      }
      else // tmp is equal to end
      {
         tmp -> prev -> next = NULL;
         // The node preceding tmp is no longer pointing to us
         (*end) = (*end) -> prev;
         // Adjust end to point to the new end of the queue
         tmp -> prev = NULL; // Disconnect tmp from the queue
         free(tmp); // deallocate the node tmp is pointing to
      }
   }
   else
   {
      ch = '\n';
   }
   return(ch);
}  
</code>

====Main Function====
===queue.c===
<code c>
/*Author: Dave Schoeffler                                                                 
* Purpose: This Program implements my queue library
*          of functions. This library gives you the functionality
*          to create a queue, enqueue a node to the queue, dequeue
*          a node from the queue and display the queue This program is menu 
*          driven. In addition to utilizing my queue library of
*          functions this program will also use the doubly linked
*          library.
*
* Compile with: gcc -o queue queue.c -L. -lqueue -L.. -ldll
*
* Execute with: ./queue
*
*/

// Include files
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
// main function
int main()
{
   // declare variables
   int i = 0, index, flag = 0;
   signed int count;
   char junk, input, input2, choice, ch; 
   Node *start, *end, *tmp;
  
   // initialize variables
   start = end = tmp = NULL;
   create(&start, &end, &tmp);
   //main while loop that allows the user to perform multiple operations
   while (flag == 0)
   {
      printf("Select which operation to perform on the queue.\n");
      printf("Enter - 1 - to enqueue a node.\n");
      printf("Enter - 2 - to dequeue\n");
      printf("Enter - 3 - to display queue.\n");
      printf("Enter - q - to quit.\n"); 
      scanf("%c", &choice);
      scanf("%c", &junk);
      switch(choice)
      {
         case '1':
            printf("Enter character to enqueue to list: ");
            scanf("%c", &input);
            scanf("%c", &junk);

            enqueue(&start, &end, 0, input);
            display(&start);
            break;
         case '2':
            count = countList(start, count); 
            if(count > 0)
            {
               ch = dequeue(&start, &end, count);
               printf("The value that was dequeued is: %c\n", ch);
               display(&start);
            }
            else if(count == 0)
            {
               ch = dequeue(&start, &end, count);
               printf("The value that was dequeued is: %c\n", ch);
            }
            else
            {
               printf("No node to dequeue...\n");
            }
            break;
         case '3':
            display(&start);
            break;
         case 'q':
         case 'Q':
            flag = 1;
            break;
         default:
            printf("Invalid entry!\n");
            break;
      }
   }
   return 0;
}              
</code>



=====Execution=====
To test my program I will enqueue the string "abcd" into the queue and then dequeue those node from the queue. Notice that when I try to dequeue a node when their are no nodes to handles that situation.

<cli>
lab46:~/src/data/queue$ ./queue
Enter a character (# to quit): a
Enter a character (# to quit): b
Enter a character (# to quit): c
Enter a character (# to quit): d
Enter a character (# to quit): #
Select which operation to perform on the queue.
Enter - 1 - to enqueue a node.
Enter - 2 - to dequeue
Enter - 3 - to display queue.
Enter - q - to quit.
2
The value that was dequeued is: d
[0] value: a
[1] value: b
[2] value: c
Select which operation to perform on the queue.
Enter - 1 - to enqueue a node.
Enter - 2 - to dequeue
Enter - 3 - to display queue.
Enter - q - to quit.
2
The value that was dequeued is: c
[0] value: a
[1] value: b
Select which operation to perform on the queue.
Enter - 1 - to enqueue a node.
Enter - 2 - to dequeue
Enter - 3 - to display queue.
Enter - q - to quit.
2
The value that was dequeued is: b
[0] value: a
Select which operation to perform on the queue.
Enter - 1 - to enqueue a node.
Enter - 2 - to dequeue
Enter - 3 - to display queue.
Enter - q - to quit.
2
The value that was dequeued is: a
Select which operation to perform on the queue.
Enter - 1 - to enqueue a node.
Enter - 2 - to dequeue
Enter - 3 - to display queue.
Enter - q - to quit.
2
No node to dequeue...
Select which operation to perform on the queue.
Enter - 1 - to enqueue a node.
Enter - 2 - to dequeue
Enter - 3 - to display queue.
Enter - q - to quit.
1
Enter character to enqueue to list: g
[0] value: g
Select which operation to perform on the queue.
Enter - 1 - to enqueue a node.
Enter - 2 - to dequeue
Enter - 3 - to display queue.
Enter - q - to quit.
1
Enter character to enqueue to list: j
[0] value: j
[1] value: g
Select which operation to perform on the queue.
Enter - 1 - to enqueue a node.
Enter - 2 - to dequeue
Enter - 3 - to display queue.
Enter - q - to quit.
3
[0] value: j
[1] value: g
Select which operation to perform on the queue.
Enter - 1 - to enqueue a node.
Enter - 2 - to dequeue
Enter - 3 - to display queue.
Enter - q - to quit.
q
lab46:~/src/data/queue$
</cli>
=====Reflection=====
So this project came a while lot easier to me than the previous one. I think some of the lessons I learned when building my stack library helped me know how to approach this project better. I successfully built and implemented my queue library of functions. The main function I tested them in allowed the user to choose from a menu what operation they would like to perform on the queue. I enjoyed doing this project more than the others as well because I felt like I knew a little bit more about what I was doing. I did have a slight hiccup dealing with a segmentation fault. I kept on trying to debug my code but wasn't able to break in one of my functions. I finally was able to get help from Matt about this and we got the problem sorted out. I look forward to using the knowledge I gained from this project into the projects to come.


=====References=====

    * [[http://en.wikipedia.org/wiki/Queue_%28data_structure%29]]
    * C++ Programming D.S. Malik
    * Matthew Haas