Assignment 4: A general queue structure
| Grade: | Only compulsory for grade 4 and 5. |
| Purpose: | Learn how to use dynamic memory and linked structures. separate compilation. |
| Preparations: |
Net lessons 3, 4, 5. |
| Examination: | Mail the solution no later than December 14, 2020. |
void *.
Thus, it is up to the user of the queue to keep track of what is stored.
Required operations
This table specifies the required operations together with their names and datatypes.| Operation | Explanation |
|---|---|
| Queue newQueue() | Creates a new queue object and returns a reference to it. |
| void enqueue(Queue q, QueueData item) | Put an element in the queue. |
| QueueData dequeue(Queue q) |
Removes and returns the first element from the queue.
Returns NULL if the queue is empty.
|
| QueueData first(Queue q) |
Returns the first element but leaves it in the queue.
Returns NULL if the queue is empty.
|
| int qLength(Queue q) | Returns the number of elements in the queue. |
| void qitReset(Queue q) | Positions the iterator to the first element in the queue. |
| int qitMore(Queue q) | Returns 0 if all elements have been returned by the iterator, else 1. |
| QueueData qitNext(Queue q) | Returns the current element and advances to the next. |
Requirements
- It should be possible to enter any type of records in the queue.
- It should be possible to have several queues, possibly with with different types of values in the same program.
- There should be no explicit upper limit of the number of elements in a queue.
- It should be possible to use the queues without knowledge of the internal representation.
- All operations shall be implemented as functions/subroutines.
-
The operations
encode,decodeandqLengthshould run in constant time, i.e. must be independent of the length of the queue. - The specified names of functions and datatypes must be used - otherwise our test programs will not work.
Declaration file
The declaration file is given:
/* queue.h
The queue is implemented as a linked list where the data
field in the queue element is a pointer to an unspecified type.
*/
#ifndef __queue__
#define __queue__
typedef void *QueueData;
typedef
struct queueElem {
QueueData item;
struct queueElem *next;
} queueElem, *link;
typedef struct QueueRecord {
// To be choosen by the student.
} QueueRecord, *Queue;
Queue newQueue();
void enqueue(Queue q, QueueData it);
QueueData dequeue(Queue q);
QueueData first(Queue q);
int qLength(Queue q);
void qitReset(Queue q);
int qitMore(Queue q);
QueueData qitNext(Queue q);
#endif
This file should be used. The only part that may and must be changed
is the contents of the QueueRecord.Copy the file from this link
Notes on the iterator
An iterator is a mechanism that makes it possible to iterate over elements in a structure without knowing the internals of the structure.
In this assignment it is enough to have an internal pointer to a
current element.. The function qitReset sets the
current pointer to the first element,
qitMore tests if the current pointer has passed the end of the queue and
qitNext is used to advance the current pointer and
return the value stored in the previous current node.
See the demonstration program!
A demonstration program
#include <stdio.h>
#include "queue.h"
int main() {
Queue q = newQueue();
enqueue(q, "Salut");
enqueue(q, "vieille");
enqueue(q, "taupe!");
printf("Queue contents: ");
qitReset(q);
while(qitMore(q)) {
printf("\"%s\" ", (char *)qitNext(q));
if(qitMore(q)) {
printf(", ");
}
}
printf("\n\nDequeu until queue empty\n");
while (qLength(q)>0){
printf(" %s\n", (char *)dequeue(q));
}
printf("\nA queue with integers\n");
int a[] ={1, 2, 3, 4};
enqueue(q, &a[0]);
enqueue(q, &a[1]);
enqueue(q, &a[2]);
printf("\n\nDequeu until queue empty\n");
while(qLength(q)>0) {
printf("% d\n", *(int *)dequeue(q));
}
}
Copy the demonstration program from this link
This shows how the program is run and what the output should be:
$ gcc -o queueDemo queue.c queueDemo.c
$ ./queueDemo
Queue contents: "Salut" , "vieille" , "taupe!"
Dequeue until queue empty
Salut
vieille
taupe!
A queue with integers
Dequeue until queue empty
1
2
3
$
