This is the queue.h
T
This is the test.c
Project Description and Requirements Dynamic memory is physically allocated in a linear manner, but can logically be used as if it were connected end-to-end. In this way, a linearly allocated array can be used in a circular manner. The following structured data type defines the data structure of a queue with an internal circular buffer: int rear; typedef struct Queue { int front; //the array index of the front element 1/the array index of the rear element int size; //the number of elements in the queue int capacity; //the capacity of the queue int *array; 1/the pointer to the circular buffer } Queue; Whenever a circular queue is empty, both the front index and rear index should be holding an invalid array index -1, and the size should be 0. The queue capacity will remain the same throughout the queue's entire life. This project involves a header file, queue.h, which contains the definition for the Queue structured data type, as well as functional prototypes for all the required functions in this project. You should #include this header file from your queue.c source file, like so: #include "queue.h" The test.c provided with this project may not be comprehensive. Please be sure to develop your own test cases, and spend some time thinking of what might break each of the required functions. Submission and Grading Rubrics: The only file required to submit is a single source file, named queue.c. This source file should contain only definitions for the required functions listed in queue.h, and no other additional function. Your source file must not contain a main() function. Do not submit additional source files, and do not submit a modified queue.h header file. Your program must compile and run to receive credit. Programs that do not compile will receive an automatic zero. More detailed rubrics are as follows: Correctness: 80% Program Comments: 10% Program Efficiency: 10% Sample Program Output: The following sample output from running the provided test case will also demonstrate the essential idea of how to use a linear array in a circular manner. Starting from an empty queue, front = -1, rear = -1, size = 0, capacity = 3 The queue has: Adding 8 to the rear, front = 0, rear - 0, size = 1, capacity - 3 The queue has: 8 Adding 61 to the rear, front = 0, rear = 1, size = 2, capacity = 3 The queue has: 8 61 Adding 16 to the rear, front = 0, rear = 2, size = 3, capacity = 3 The queue has: 8 61 16 Adding 34 to the rear, front = 0, rear = 2, size = 3, capacity - 3 The queue has: 8 61 16 Adding 58 to the rear, front = 0, rear = 2, size = 3, capacity = 3 The queue has: 8 61 16 Making the queue empty, front = -1, rear = -1, size = 0, capacity = 3 The queue has: Adding 42 to the rear, front = 0, rear = 0, size = 1, capacity = 3 The queue has: 42 Adding 53 to the rear, front = 0, rear = 1, size = 2, capacity = 3 The queue has: 42 53 Adding 4 to the rear, front - 0, rear - 2, size - 3, capacity - 3 The queue has: 42 53 4 Adding 36 to the rear, front = 0, rear = 2, size = 3, capacity = 3 The queue has: 42 53 4 Adding 49 to the rear, front = 0, rear = 2, size = 3, capacity = 3 The queue has: 42 53 4 Removing 42 from the front, front = 1, rear = 2, size = 2, capacity = 3 The queue has: 53 4 Removing 53 from the front, front = 2, rear = 2, size = 1, capacity = 3 The queue has: 4 #ifndef QUEUE_H #define QUEUE_H typedef struct Queue { int front; //the array index of the front element int rear; //the array index of the rear element int size; //the number of elements in the queue int capacity; //the capacity of the queue int *array; //the pointer to the circular buffer } Queue; //create an empty queue with an array of the desired capacity Queue *createQueue(int capacity); //destroy the queue Queue * destroyQueue (Queue *9); //return 1 if the queue is empty, otherwise int isEmpty(Queue *q); //make the queue empty void makeEmpty(Queue *q); //return 1 if the queue is full, o otherwise int isFull(Queue *q); //add a new element to the rear of the queue void enqueue (Queue *q, int data); //remove and return the front element from the queue int dequeue (Queue *q); //print the queue elements void printQueue (Queue *q); #endif #include
#include #include "queue.h" int main() { Queue *q; int i, temp; q = createQueue (3); printf(" Starting from an empty queue, front = %d, rear = %d, size = %d, capacity = %d ", q->front, q->rear, q->size, q->capacity); printf("The queue has: "); printQueue (9); printf(" "); srand(time(NULL)); for (i = 0; i front, q->rear, q->size, q->capacity); printf("The queue has: "); printQueue(q); printf(" "); if (i == 4) { makeEmpty(); printf(" Making the queue empty, front = %d, rear = %d, size = %d, capacity = %d ", q->front, q->rear, q->size, q->capacity); printf("The queue has: "); printQueue (9); printf(" "); } } for (i = 0; i front, q->rear, q->size); printf("The queue has: "); printQueue (9); printf(" "); for (i = 0; i front, q->rear, q->size, q->capacity); printf("The queue has: "); printQueue (9); printf(" "); } } Project Description and Requirements Dynamic memory is physically allocated in a linear manner, but can logically be used as if it were connected end-to-end. In this way, a linearly allocated array can be used in a circular manner. The following structured data type defines the data structure of a queue with an internal circular buffer: int rear; typedef struct Queue { int front; //the array index of the front element 1/the array index of the rear element int size; //the number of elements in the queue int capacity; //the capacity of the queue int *array; 1/the pointer to the circular buffer } Queue; Whenever a circular queue is empty, both the front index and rear index should be holding an invalid array index -1, and the size should be 0. The queue capacity will remain the same throughout the queue's entire life. This project involves a header file, queue.h, which contains the definition for the Queue structured data type, as well as functional prototypes for all the required functions in this project. You should #include this header file from your queue.c source file, like so: #include "queue.h" The test.c provided with this project may not be comprehensive. Please be sure to develop your own test cases, and spend some time thinking of what might break each of the required functions. Submission and Grading Rubrics: The only file required to submit is a single source file, named queue.c. This source file should contain only definitions for the required functions listed in queue.h, and no other additional function. Your source file must not contain a main() function. Do not submit additional source files, and do not submit a modified queue.h header file. Your program must compile and run to receive credit. Programs that do not compile will receive an automatic zero. More detailed rubrics are as follows: Correctness: 80% Program Comments: 10% Program Efficiency: 10% Sample Program Output: The following sample output from running the provided test case will also demonstrate the essential idea of how to use a linear array in a circular manner. Starting from an empty queue, front = -1, rear = -1, size = 0, capacity = 3 The queue has: Adding 8 to the rear, front = 0, rear - 0, size = 1, capacity - 3 The queue has: 8 Adding 61 to the rear, front = 0, rear = 1, size = 2, capacity = 3 The queue has: 8 61 Adding 16 to the rear, front = 0, rear = 2, size = 3, capacity = 3 The queue has: 8 61 16 Adding 34 to the rear, front = 0, rear = 2, size = 3, capacity - 3 The queue has: 8 61 16 Adding 58 to the rear, front = 0, rear = 2, size = 3, capacity = 3 The queue has: 8 61 16 Making the queue empty, front = -1, rear = -1, size = 0, capacity = 3 The queue has: Adding 42 to the rear, front = 0, rear = 0, size = 1, capacity = 3 The queue has: 42 Adding 53 to the rear, front = 0, rear = 1, size = 2, capacity = 3 The queue has: 42 53 Adding 4 to the rear, front - 0, rear - 2, size - 3, capacity - 3 The queue has: 42 53 4 Adding 36 to the rear, front = 0, rear = 2, size = 3, capacity = 3 The queue has: 42 53 4 Adding 49 to the rear, front = 0, rear = 2, size = 3, capacity = 3 The queue has: 42 53 4 Removing 42 from the front, front = 1, rear = 2, size = 2, capacity = 3 The queue has: 53 4 Removing 53 from the front, front = 2, rear = 2, size = 1, capacity = 3 The queue has: 4 #ifndef QUEUE_H #define QUEUE_H typedef struct Queue { int front; //the array index of the front element int rear; //the array index of the rear element int size; //the number of elements in the queue int capacity; //the capacity of the queue int *array; //the pointer to the circular buffer } Queue; //create an empty queue with an array of the desired capacity Queue *createQueue(int capacity); //destroy the queue Queue * destroyQueue (Queue *9); //return 1 if the queue is empty, otherwise int isEmpty(Queue *q); //make the queue empty void makeEmpty(Queue *q); //return 1 if the queue is full, o otherwise int isFull(Queue *q); //add a new element to the rear of the queue void enqueue (Queue *q, int data); //remove and return the front element from the queue int dequeue (Queue *q); //print the queue elements void printQueue (Queue *q); #endif #include #include #include "queue.h" int main() { Queue *q; int i, temp; q = createQueue (3); printf(" Starting from an empty queue, front = %d, rear = %d, size = %d, capacity = %d ", q->front, q->rear, q->size, q->capacity); printf("The queue has: "); printQueue (9); printf(" "); srand(time(NULL)); for (i = 0; i front, q->rear, q->size, q->capacity); printf("The queue has: "); printQueue(q); printf(" "); if (i == 4) { makeEmpty(); printf(" Making the queue empty, front = %d, rear = %d, size = %d, capacity = %d ", q->front, q->rear, q->size, q->capacity); printf("The queue has: "); printQueue (9); printf(" "); } } for (i = 0; i front, q->rear, q->size); printf("The queue has: "); printQueue (9); printf(" "); for (i = 0; i front, q->rear, q->size, q->capacity); printf("The queue has: "); printQueue (9); printf(" "); } }
