A project for Data Structures by Tyler Galpin during the Fall 2011.

This project took about one day to complete and was completed on November 22nd, 2011.

The point of this project is to make a usable Queue library that can be used not only in a test implementation, but can be applied to any program that may make use of a queue comprised of a linked list. Through this, a greater understanding of what a queue is should be attained.

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

• Understanding of linked list
• Understanding of doubly linked list
• Basic understanding of what a queue is
• Understanding of pointers

As previously stated, a working queue library is the goal. It should be able to manipulate the data in the queue however we need it to. As is such,the following functions must be in it:

• Enqueue–Add a node, FIFO style
• Dequeue– Remove a node, FIFO style
• Display– Display queue, make note of where top and bottom is

The implementation is relatively straightforward. I just need it to demonstrate that the logic of a queue is present. For this, a menu is included in the main part of the program to let you choose which function you'd like to test.

• linked list: The queue is based off of a linked list
• doubly linked list: The queue uses a doubly linked list.
• pointers: make up the backbone of the data structure
• malloc: needed in the creation of new queues/nodes
• queue: This would be a queue.
• library: That is what is being made/used!
• File I/O: Used in main.c for test implementation

/*
 * Queue implimentation -- header file
 *
 * Fall2011 Data Structures
 */
 
#ifndef _QUEUELIB_H
#define _QUEUELIB_H
 
// Include files
#include <stdio.h>
#include <stdlib.h>
 
// Create our node structure
struct node {
	int value;
	struct node *next;
	struct node *prev;
};
typedef struct node Node;
 
Node *head, *tail, *tmp;
 
void enqueue(int);
void dequeue();
void displayQueue();
 
#endif

/*
 * Queue implimentation -- main
 *
 * Fall2011 Data Structures
 */
 
#include "queuelib.h" 
 
// main function
int main()
{
	int i, input, choice;
	puts("Please enter a value (-1 to stop:): ");
	scanf("%d", &input);
	while(input != -1)
	{
		enqueue(input);
		puts("Please enter a value (-1 to stop:): ");
		scanf("%d", &input);
	}
	puts("Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit]");
	scanf("%d", &choice);
	while (choice != 0)
	{
		if (choice == 1)
		{
			input=0;			
			puts("Please enter a value (-1 to stop:): ");
			scanf("%d", &input);
			while(input != -1)
			{
				enqueue(input);
				puts("Please enter a value (-1 to stop:): ");
				scanf("%d", &input);
			}
			input=0;
		}
		else if (choice == 2)
		{
			dequeue();
		}
		else if (choice == 3)
		{
			displayQueue();
		}	
		puts("Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit]");
		scanf("%d", &choice);
	}
/*
	while((tmp=pop())!=NULL)
	{
		printf("value: %d\n", tmp->value);
		free(tmp);
	}
*/
	return(0);
}

#include"queuelib.h"
 
void enqueue(int value)
{
	if (head==NULL)//No values in the queue yet
	{
		head = (Node *) malloc(sizeof(Node));//Initialize head (first) node
		tail=head;//tail (last) node is also the head node
		head->next=NULL;//Nothing before
		head->prev=NULL;//Nothing after
		tmp=head;//Make tmp have the same value as head up until now
		head->value=value;//Give input value to head
	}
	else if (head == tail)//Only one node in queue
	{
		tmp= (Node *) malloc(sizeof(Node));
		tail->prev=tmp;//Last node in line becomes tmp
		tmp->next=tail;//Tmp points to the former last in line, currently tail
		tail=tail->prev;//Tail is redefined as the last node again
		tail->value=value;//tail's value becomes inputted value
		tail->prev=NULL;//nothing after tail, it is end of the queue
	}
	else
	{
		tmp=head;//Set tmp to front node
		int i=0;
	       	while(tmp != NULL)
	        {   
        	        i++;
                	tmp=tmp->next;
       		}   //Move tmp to end node
        	tmp = (Node *) malloc (sizeof(Node));
        	tail -> prev = tmp;//The node last in line becomes tmp
        	tmp -> next = tail;//The node after the last is tail
        	tail = tail -> prev;//Tail becomes end node again
        	tail -> value = value;//Give tail the input value
        	tail -> prev = NULL;//Nothing after tail
	}
}

#include"queuelib.h"
 
void dequeue()
{
	tmp=head;//Move tmp to head
	tmp->prev->next=NULL;//Make the next of tmp's prev NULL
	head=head->prev;//The node after head the new head node
	tmp->next=NULL;//Nothing ahead of tmp
	free(tmp);//deallocate tmp
}

#include"queuelib.h"
 
void displayQueue()
{
	int n=0;
	tmp=head;
	printf("\n[Front of queue]\n");
	while(tmp != NULL)
	{
		printf("[%d]: %d\n", n+1,tmp->value);
		n++;
		tmp=tmp->prev;
	}
	printf("[End of queue]\n");
}

This is how to compile and execute:

lab46:~/src/data/queue$ ar rcs libdll.a *.o
lab46:~/src/data/queue$ gcc -o testimple main.c -L. -ldll
lab46:~/src/data/queue$ ./testimple

This was another adequately sized project that did not take me very long. This is due to the fact that it only required a reworking of the queue library.

In performing this project, the following resources were referenced:

• Matt Haas + Class lecture
• Fellow classmates (simple discussion about the aspects of our personal implementations)
• C Programming Language O'Reilly Pocket Reference