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:

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

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.

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;
	}
}

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.

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;
		}
	}
}

deQueue.c
deQueue.c contains one function for dequeuing or removing data from a queue.

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;
}

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.

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;
}

enQueue.c
enQueue.c contains one function for putting into queue.

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;
		}
}

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.

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;
}

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.

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;
}

queueTest.c
queueTest.c is a program used to test the queue library.

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();
}

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:

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

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:

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

Execution

Execution of makeQueue.bat (compilation, creation of a static library, linking, and execution of the queueTest test program on a Windows machine

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 . . .

Execution of makeQueue.sh (compilation, creation of a static library, linking, and execution of the queueTest test program on a Linux machine

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$

Addition and committal of the queue library and test file to the Subversion repository.

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$

Committal of queue library files after cleaning them up

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$

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

Lab46 Wiki

Sidebar

Table of Contents

Objectives

Prerequisites

Background

Scope

Attributes

Code

Execution

Reflection

References

Lab46 Wiki

User Tools

Site Tools

Sidebar

Table of Contents

Objectives

Prerequisites

Background

Scope

Attributes

Code

Execution

Reflection

References

Page Tools