Homework SourseNow you are asked to do the followings 1 Add void ReverseQue
Now, you are asked to do the followings: 1. Add void ReverseQueue(queueADT queue); prototype into queue.h interface: 2. Implement this function under both array and list representations. That is, add its implementation into both qarray.c and qlist.c files When Implementing this function, make sure that you will use the original memory cells and do not allocate any additional storage (of course you can use local variables) 3. Modify qtest.c client/driver program so that a user can reverse the existing queue by calling the above function that is just added to the interface. 4. Finally say make and compile qtest.c with new qarray.c and qlist.c. Then test both arrayqtest and list-qtest programs....
---------qarray.c------------
/*
* File: qarray.c
* --------------
* This file implements the queue.h abstraction using an array.
*/
#include <stdio.h>
#include \"genlib.h\"
#include \"queue.h\"
/*
* Constants:
* ----------
* MaxQueueSize -- Maximum number of elements in the queue
* QueueArraySize -- Size of the internal array
*/
#define MaxQueueSize 100
#define QueueArraySize (MaxQueueSize + 1)
/*
* Type: queueCDT
* --------------
* This type defines the concrete representation of a queue.
* This implementation uses a ring buffer to implement the
* queue. The next item to be dequeued is found at the array
* element indexed by head. The tail index indicates the next
* free position. When head and tail are equal, the queue is
* empty. The head and tail indices each move from the end of
* the array back to the beginning, giving rise to the name
* \"ring buffer.\" The functions use modular arithmetic to
* implement this wrap-around behavior.
*/
struct queueCDT {
queueElementT elements[QueueArraySize];
int head;
int tail;
};
/* Exported entries */
queueADT NewQueue(void)
{
queueADT queue;
queue = New(queueADT);
queue->head = queue->tail = 0;
return (queue);
}
void FreeQueue(queueADT queue)
{
FreeBlock(queue);
}
void Enqueue(queueADT queue, queueElementT element)
{
if (QueueIsFull(queue)) Error(\"Enqueue: queue is full\");
queue->elements[queue->tail] = element;
queue->tail = (queue->tail + 1) % QueueArraySize;
}
queueElementT Dequeue(queueADT queue)
{
queueElementT result;
if (QueueIsEmpty(queue)) Error(\"Dequeue: queue is empty\");
result = queue->elements[queue->head];
queue->head = (queue->head + 1) % QueueArraySize;
return (result);
}
bool QueueIsEmpty(queueADT queue)
{
return (queue->head == queue->tail);
}
bool QueueIsFull(queueADT queue)
{
return ((queue->tail + 1) % QueueArraySize == queue->head);
}
/*
* Implementation note: QueueLength
* --------------------------------
* This function determines the number of elements by computing
* (tail - head) % size. The size of the queue is added in at
* the beginning to ensure that the left operand to % is always
* positive.
*/
int QueueLength(queueADT queue)
{
return ((QueueArraySize + queue->tail - queue->head)
% QueueArraySize);
}
queueElementT GetQueueElement(queueADT queue, int index)
{
if (index < 0 || index >= QueueLength(queue)) {
Error(\"Queue element is out of range\");
}
return (queue->elements[(queue->head + index)
% QueueArraySize]);
}
--------------qlist.c------------
/*
* File: qlist.c
* -------------
* This file implements the queue.h abstraction using a linked
* list of cells.
*/
#include <stdio.h>
#include \"genlib.h\"
#include \"queue.h\"
/*
* Type: cellT
* -----------
* This type defines the cells used for the linked list that
* stores the items in the queue.
*/
typedef struct cellT {
queueElementT value;
struct cellT *link;
} cellT;
/*
* Type: queueCDT
* --------------
* This type defines the concrete representation of a queue.
* In this representation, the queue is a linked list of cells.
* The next item to be dequeued is found at the cell addressed
* by the head field. The tail field points to the last element
* in the queue, which allows Enqueue to operate in constant time.
* The empty queue is indicated by a NULL head pointer.
*/
struct queueCDT {
cellT *head;
cellT *tail;
};
/* Exported entries */
queueADT NewQueue(void)
{
queueADT queue;
queue = New(queueADT);
queue->head = NULL;
return (queue);
}
void FreeQueue(queueADT queue)
{
cellT *cp, *next;
cp = queue->head;
while (cp != NULL) {
next = cp->link;
FreeBlock(cp);
cp = next;
}
FreeBlock(queue);
}
void Enqueue(queueADT queue, queueElementT element)
{
cellT *cp;
cp = New(cellT *);
cp->value = element;
cp->link = NULL;
if (queue->head == NULL) {
queue->head = cp;
} else {
queue->tail->link = cp;
}
queue->tail = cp;
}
queueElementT Dequeue(queueADT queue)
{
queueElementT result;
cellT *cp;
cp = queue->head;
if (cp == NULL) {
Error(\"Dequeue: queue is empty\");
}
result = cp->value;
queue->head = cp->link;
FreeBlock(cp);
return (result);
}
bool QueueIsEmpty(queueADT queue)
{
return (queue->head == NULL);
}
bool QueueIsFull(queueADT queue)
{
return (FALSE);
}
int QueueLength(queueADT queue)
{
int n;
cellT *cp;
n = 0;
for (cp = queue->head; cp != NULL; cp = cp->link) n++;
return (n);
}
queueElementT GetQueueElement(queueADT queue, int index)
{
int i;
cellT *cp;
if (index < 0 || index >= QueueLength(queue)) {
Error(\"Queue element is out of range\");
}
cp = queue->head;
for (i = 0; i < index; i++) cp = cp->link;
return (cp->value);
}
-------qtest.c--------
/*
* File: qtest.c
* -------------
* This program tests the queue package by allowing the user to
* keep track of a waiting list. The commands are listed in the
* function GiveInstructions.
*/
#include <stdio.h>
#include \"genlib.h\"
#include \"simpio.h\"
#include \"strlib.h\"
#include \"scanadt.h\"
#include \"queue.h\"
/* Private function prototypes */
static void GiveInstructions(void);
static void DisplayQueue(queueADT queue);
/* Main program */
main()
{
queueADT queue;
scannerADT scanner;
string line, cmd, value;
GiveInstructions();
scanner = NewScanner();
SetScannerSpaceOption(scanner, IgnoreSpaces);
queue = NewQueue();
while (TRUE) {
printf(\":\");
line = GetLine();
SetScannerString(scanner, line);
cmd = ConvertToLowerCase(ReadToken(scanner));
if (StringEqual(cmd, \"enqueue\")) {
value = ReadToken(scanner);
Enqueue(queue, value);
} else if (StringEqual(cmd, \"dequeue\")) {
printf(\"%s\ \", Dequeue(queue));
} else if (StringEqual(cmd, \"display\")) {
DisplayQueue(queue);
} else if (StringEqual(cmd, \"quit\")) {
break;
} else {
printf(\"Unrecognized command: %s\ \", line);
}
}
FreeQueue(queue);
FreeScanner(scanner);
}
/*
* Function: GiveInstructions
* Usage: GiveInstructions();
* --------------------------
* This function displays a message to the user showing
* what options are available in the test program.
*/
static void GiveInstructions(void)
{
printf(\"Enter commands in the following forms:\ \");
printf(\" enqueue x -- Enqueue the token x\ \");
printf(\" dequeue -- Dequeue the value at the head of the queue\ \");
printf(\" display -- Display the contents of the queue\ \");
printf(\" quit -- Exit from the program\ \");
}
/*
* Function: DisplayQueue
* Usage: DisplayQueue(queue);
* ---------------------------
* This function displays the contents of a string queue on
* a single line.
*/
static void DisplayQueue(queueADT queue)
{
int i, len;
len = QueueLength(queue);
if (len == 0) {
printf(\"Queue is empty.\");
} else {
printf(\"Queue contains: \");
for (i = 0; i < len; i++) {
if (i > 0) printf(\", \");
printf(\"%s\", GetQueueElement(queue, i));
}
}
printf(\"\ \");
}
/*
* File: queue.h
* -------------
* This interface defines an abstraction for queues. In any
* single application that uses this interface, the values in
* the queue are constrained to a single type, although it
* is easy to change that type by changing the definition of
* queueElementT in this interface.
*/
#ifndef _queue_h
#define _queue_h
#include \"genlib.h\"
/*
* Type: queueElementT
* -------------------
* The type queueElementT is used in this interface to indicate
* the type of values that can be stored in the queue. Here the
* queue is used to store values of type void *, but that can
* be changed by editing this definition line.
*/
typedef void *queueElementT;
/*
* Type: queueADT
* --------------
* The queueADT type is defined as a pointer to its concrete
* counterpart, which is available only to the implementation,
* not to clients.
*/
typedef struct queueCDT *queueADT;
/*
* Function: NewQueue
* Usage: queue = NewQueue();
* --------------------------
* This function allocates and returns an empty queue.
*/
queueADT NewQueue(void);
/*
* Function: FreeQueue
* Usage: FreeQueue(queue);
* ------------------------
* This function frees the storage associated with queue.
*/
void FreeQueue(queueADT queue);
/*
* Function: Enqueue
* Usage: Enqueue(queue, element);
* -------------------------------
* This function adds element to the end of the queue.
*/
void Enqueue(queueADT queue, queueElementT element);
/*
* Function: Dequeue
* Usage: element = Dequeue(queue);
* --------------------------------
* This function removes the data value at the head of the queue
* and returns it to the client. If the queue is empty, Dequeue
* calls Error with an appropriate message.
*/
queueElementT Dequeue(queueADT queue);
/*
* Functions: QueueIsEmpty, QueueIsFull
* Usage: if (QueueIsEmpty(queue)) . . .
* if (QueueIsFull(queue)) . . .
* -------------------------------------
* These functions test whether the queue is empty or full.
*/
bool QueueIsEmpty(queueADT queue);
bool QueueIsFull(queueADT queue);
void ReverseQueue(queueADT queue);
/*
* Function: QueueLength
* Usage: n = QueueLength(queue);
* ------------------------------
* This function returns the number of elements in the queue.
*/
int QueueLength(queueADT queue);
/*
* Function: GetQueueElement
* Usage: element = GetQueueElement(queue, index);
* -----------------------------------------------
* This function returns the element at the specified index in the
* queue, where the head of the queue is defined as index 0. For
* example, calling GetQueueElement(queue, 0) returns the initial
* element from the queue without removing it. If the caller tries
* to select an element that is out of range, GetQueueElement calls
* Error. Note: This function is not a fundamental queue operation
* and is instead provided mainly to facilitate debugging.
*/
queueElementT GetQueueElement(queueADT queue, int index);
#endif
Solution
/*** 1. Add void ReverseQueue(queueADT queue); prototype into queue.h interface*/
/*
* File: queue.h
* -------------
* This interface defines an abstraction for queues. In any
* single application that uses this interface, the values in
* the queue are constrained to a single type, although it
* is easy to change that type by changing the definition of
* queueElementT in this interface.
*/
#ifndef _queue_h
#define _queue_h
#include \"genlib.h\"
/*
* Type: queueElementT
* -------------------
* The type queueElementT is used in this interface to indicate
* the type of values that can be stored in the queue. Here the
* queue is used to store values of type void *, but that can
* be changed by editing this definition line.
*/
typedef void *queueElementT;
/*
* Type: queueADT
* --------------
* The queueADT type is defined as a pointer to its concrete
* counterpart, which is available only to the implementation,
* not to clients.
*/
typedef struct queueCDT *queueADT;
/*
* Function: NewQueue
* Usage: queue = NewQueue();
* --------------------------
* This function allocates and returns an empty queue.
*/
queueADT NewQueue(void);
/*
* Function: FreeQueue
* Usage: FreeQueue(queue);
* ------------------------
* This function frees the storage associated with queue.
*/
void FreeQueue(queueADT queue);
/*
* Function: Enqueue
* Usage: Enqueue(queue, element);
* -------------------------------
* This function adds element to the end of the queue.
*/
void Enqueue(queueADT queue, queueElementT element);
/*
* Function: Dequeue
* Usage: element = Dequeue(queue);
* --------------------------------
* This function removes the data value at the head of the queue
* and returns it to the client. If the queue is empty, Dequeue
* calls Error with an appropriate message.
*/
queueElementT Dequeue(queueADT queue);
/*
* Functions: QueueIsEmpty, QueueIsFull
* Usage: if (QueueIsEmpty(queue)) . . .
* if (QueueIsFull(queue)) . . .
* -------------------------------------
* These functions test whether the queue is empty or full.
*/
bool QueueIsEmpty(queueADT queue);
bool QueueIsFull(queueADT queue);
/*
* Function: QueueLength
* Usage: n = QueueLength(queue);
* ------------------------------
* This function returns the number of elements in the queue.
*/
int QueueLength(queueADT queue);
/*
* Function: GetQueueElement
* Usage: element = GetQueueElement(queue, index);
* -----------------------------------------------
* This function returns the element at the specified index in the
* queue, where the head of the queue is defined as index 0. For
* example, calling GetQueueElement(queue, 0) returns the initial
* element from the queue without removing it. If the caller tries
* to select an element that is out of range, GetQueueElement calls
* Error. Note: This function is not a fundamental queue operation
* and is instead provided mainly to facilitate debugging.
*/
queueElementT GetQueueElement(queueADT queue, int index);
/*
* Function: ReverseQueue
* Usage: element = ReverseQueue(queue);
* ------------------------------
* This function reverse order of the elements in the queue, where
* the head of queue becomes the tail of queue and similarly,
* tail of the queue becomes the head of the queue.
*/
void ReverseQueue(queueADT queue);
#endif
/*** 2. Implement this function(void ReverseQueue(queueADT queue)) under both array and list representations. */
--------------qlist.c------------
/*
* File: qlist.c
* -------------
* This file implements the queue.h abstraction using a linked
* list of cells.
*/
#include <stdio.h>
#include \"genlib.h\"
#include \"queue.h\"
/*
* Type: cellT
* -----------
* This type defines the cells used for the linked list that
* stores the items in the queue.
*/
typedef struct cellT {
queueElementT value;
struct cellT *link;
} cellT;
/*
* Type: queueCDT
* --------------
* This type defines the concrete representation of a queue.
* In this representation, the queue is a linked list of cells.
* The next item to be dequeued is found at the cell addressed
* by the head field. The tail field points to the last element
* in the queue, which allows Enqueue to operate in constant time.
* The empty queue is indicated by a NULL head pointer.
*/
struct queueCDT {
cellT *head;
cellT *tail;
};
/* Exported entries */
queueADT NewQueue(void)
{
queueADT queue;
queue = New(queueADT);
queue->head = NULL;
return (queue);
}
void FreeQueue(queueADT queue)
{
cellT *cp, *next;
cp = queue->head;
while (cp != NULL) {
next = cp->link;
FreeBlock(cp);
cp = next;
}
FreeBlock(queue);
}
void Enqueue(queueADT queue, queueElementT element)
{
cellT *cp;
cp = New(cellT *);
cp->value = element;
cp->link = NULL;
if (queue->head == NULL) {
queue->head = cp;
} else {
queue->tail->link = cp;
}
queue->tail = cp;
}
queueElementT Dequeue(queueADT queue)
{
queueElementT result;
cellT *cp;
cp = queue->head;
if (cp == NULL) {
Error(\"Dequeue: queue is empty\");
}
result = cp->value;
queue->head = cp->link;
FreeBlock(cp);
return (result);
}
bool QueueIsEmpty(queueADT queue)
{
return (queue->head == NULL);
}
bool QueueIsFull(queueADT queue)
{
return (FALSE);
}
int QueueLength(queueADT queue)
{
int n;
cellT *cp;
n = 0;
for (cp = queue->head; cp != NULL; cp = cp->link) n++;
return (n);
}
queueElementT GetQueueElement(queueADT queue, int index)
{
int i;
cellT *cp;
if (index < 0 || index >= QueueLength(queue)) {
Error(\"Queue element is out of range\");
}
cp = queue->head;
for (i = 0; i < index; i++) cp = cp->link;
return (cp->value);
}
void ReverseQueue(queueADT queue)
{
int length= QueueLength(queue);
cellT*temp;
for(int decre=length;decre>=1;decre--)
{
temp=queue->head;
for(int inc=1;inc>decre;inc++)
{
temp=temp->next;
}
printf(temp->value);
}
}
---------qarray.c------------
/*
* File: qarray.c
* --------------
* This file implements the queue.h abstraction using an array.
*/
#include <stdio.h>
#include \"genlib.h\"
#include \"queue.h\"
/*
* Constants:
* ----------
* MaxQueueSize -- Maximum number of elements in the queue
* QueueArraySize -- Size of the internal array
*/
#define MaxQueueSize 100
#define QueueArraySize (MaxQueueSize + 1)
/*
* Type: queueCDT
* --------------
* This type defines the concrete representation of a queue.
* This implementation uses a ring buffer to implement the
* queue. The next item to be dequeued is found at the array
* element indexed by head. The tail index indicates the next
* free position. When head and tail are equal, the queue is
* empty. The head and tail indices each move from the end of
* the array back to the beginning, giving rise to the name
* \"ring buffer.\" The functions use modular arithmetic to
* implement this wrap-around behavior.
*/
struct queueCDT {
queueElementT elements[QueueArraySize];
int head;
int tail;
};
/* Exported entries */
queueADT NewQueue(void)
{
queueADT queue;
queue = New(queueADT);
queue->head = queue->tail = 0;
return (queue);
}
void FreeQueue(queueADT queue)
{
FreeBlock(queue);
}
void Enqueue(queueADT queue, queueElementT element)
{
if (QueueIsFull(queue)) Error(\"Enqueue: queue is full\");
queue->elements[queue->tail] = element;
queue->tail = (queue->tail + 1) % QueueArraySize;
}
queueElementT Dequeue(queueADT queue)
{
queueElementT result;
if (QueueIsEmpty(queue)) Error(\"Dequeue: queue is empty\");
result = queue->elements[queue->head];
queue->head = (queue->head + 1) % QueueArraySize;
return (result);
}
bool QueueIsEmpty(queueADT queue)
{
return (queue->head == queue->tail);
}
bool QueueIsFull(queueADT queue)
{
return ((queue->tail + 1) % QueueArraySize == queue->head);
}
/*
* Implementation note: QueueLength
* --------------------------------
* This function determines the number of elements by computing
* (tail - head) % size. The size of the queue is added in at
* the beginning to ensure that the left operand to % is always
* positive.
*/
int QueueLength(queueADT queue)
{
return ((QueueArraySize + queue->tail - queue->head)
% QueueArraySize);
}
queueElementT GetQueueElement(queueADT queue, int index)
{
if (index < 0 || index >= QueueLength(queue)) {
Error(\"Queue element is out of range\");
}
return (queue->elements[(queue->head + index)
% QueueArraySize]);
}
void ReverseQueue(queueADT queue)
{ int firstelement=queue->head;
queueADT temp;
if (QueueIsEmpty(queue)) Error(\"Queue: queue is empty\");
else{
int length=QueueLength(queue);
for (i = len; i>0; i--) {
if (i > 0) printf(\", \");
printf(\"%s\", GetQueueElement(queue, i));
}
}
}
}
/*** 3. Modify qtest.c client/driver program so that a user can reverse the existing queue
by calling the above function that is just added to the interface. */
-------qtest.c--------
/*
* File: qtest.c
* -------------
* This program tests the queue package by allowing the user to
* keep track of a waiting list. The commands are listed in the
* function GiveInstructions.
*/
#include <stdio.h>
#include \"genlib.h\"
#include \"simpio.h\"
#include \"strlib.h\"
#include \"scanadt.h\"
#include \"queue.h\"
/* Private function prototypes */
static void GiveInstructions(void);
static void DisplayQueue(queueADT queue);
/* Main program */
main()
{
queueADT queue;
scannerADT scanner;
string line, cmd, value;
GiveInstructions();
scanner = NewScanner();
SetScannerSpaceOption(scanner, IgnoreSpaces);
queue = NewQueue();
while (TRUE) {
printf(\":\");
line = GetLine();
SetScannerString(scanner, line);
cmd = ConvertToLowerCase(ReadToken(scanner));
if (StringEqual(cmd, \"enqueue\")) {
value = ReadToken(scanner);
Enqueue(queue, value);
} else if (StringEqual(cmd, \"dequeue\")) {
printf(\"%s\ \", Dequeue(queue));
} else if (StringEqual(cmd, \"display\")) {
DisplayQueue(queue);
} else if (StringEqual(cmd, \"quit\")) {
break;
}else if(StringEqual(cmd,\"reversequeue\")){
ReverseQueue(queue);
}
else {
printf(\"Unrecognized command: %s\ \", line);
}
}
FreeQueue(queue);
FreeScanner(scanner);
}
