#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
// -------- Vorgegeben Anfang-----------
typedef int Queueelement;
typedef struct {
/* the space to store the queue elements */
Queueelement *queuespace;
/* points to entry into which element is to be enqueud */
unsigned long enqueueindex,
/* last element of queue */
dequeueindex,
/* size of the queue (max no_of_elements)*/
queuesize,
/* no of elements between
enqueueindex+1 and dequeindex */
no_of_elements;
} Queue;
/*
The following function delivers an empty queue with a reservoir of
size elements to be stored in the queue. The reservoir can, if
necessary, be enlarged.
*/
Queue *queue_new(unsigned long queuesize);
/* The following function returns true iff the queue is empty. */
bool queue_is_empty(const Queue *q);
/* The following function resizes the queue by doubling the space reservoir */
void queue_double_size(Queue *q);
/* The following function adds an element elem to the end of the queue. */
void queue_enqueue(Queue *q, Queueelement elem);
/* The following function removes the element elem from the start of the queue.
*/
Queueelement queue_dequeue(Queue *q);
/* print the contents of <*q> on screen */
void queue_print(const Queue *q);
/* The following function frees the space required for the queue. */
void queue_delete(Queue *q);
// --------- Vorgegeben Ende ---------
/*
The following function delivers an empty queue with a reservoir of
size elements to be stored in the queue. The reservoir can, if
necessary, be enlarged.
*/
Queue *queue_new(unsigned long queuesize) {
Queue *q;
q = (Queue *) malloc(sizeof(*q));
assert(queuesize > 0);
q->no_of_elements = 0;
q->queuesize = queuesize;
q->enqueueindex = queuesize - 1;
q->dequeueindex = queuesize - 1;
return q;
}
/* The following function returns true if the queue is empty. */
bool queue_is_empty(const Queue *q)
{
// Ueberpruefen, ob q existiert
assert(q);
// Wenn keine Elemente im Queue vorhanden sind, muss dennoch ueberprueft werden
// ob der Enqueueindex und der Dequeueindex beide 0 sind
if (q->no_of_elements == 0)
{
assert((q->enqueueindex == 0) && (q->dequeueindex == 0));
return true;
}
return false;
}
/* The following function resizes the queue by doubling the space reservoir */
void queue_double_size(Queue *q)
{
// Vorhandener Speicher des Queues wird verdoppelt
q = (Queue *) realloc (*q, sizeof(q*)*2);
// Zu beachten ist, dass die Elemente nach hinten verschoben werden muessen
// damit keine "Loch" entsteht
}
/* The following function adds an element elem to the end of the queue. */
void queue_enqueue(Queue *q, Queueelement elem) {
// Falls die Anzahl der Elemente der Groesse des Queues entspricht
// wird die Queuegroesse um die doppelte groesse erweitert
/*
if (q->no_of_elements == q->queuesize) {
queue_double_size(q);
}
*/
q->queuespace[q->enqueueindex] = elem;
if (q->enqueueindex > 0)
{
// Den Enqueueindex vermindern, damit der richtige Index angezeigt wird
q->enqueueindex--;
}
else
{
// Wenn enqueueindex <= 0 dann ist der enqueueindex = queuesize-1
// also die hinterste Stelle
q->enqueueindex = q->queuesize - 1;
}
// erhoeht die Anzahl der Elemente um 1
q->no_of_elements++;
//printf("Enqueueindex: %d", q->enqueueindex);
}
/* The following function removes the element elem from the start of the queue.
*/
Queueelement queue_dequeue(Queue *q) {
// Es muss ueberprueft werden, ob Elemente vorhanden sind.
assert(q->no_of_elements > 0);
Queueelement elem;
// FIFO charakter daher muss das zuerst abgelegte Element aus dem
// Queue entfernt werden
elem = q->queuespace[q->dequeueindex];
if (q->dequeueindex > 0) {
q->dequeueindex--;
}
// Wenn der dequeueindex <= 0 ist, musst der dequeueindex auf queuesize-1 gesetzt werden
else {
q->dequeueindex = q->queuesize - 1;
}
// Verminderung der Anzahl der Elemente um 1
q->no_of_elements--;
return elem;
}
/* print the contents of <*q> on screen */
void queue_print(const Queue *q)
{
int i;
for(i = q->enqueueindex+1; i <= q->dequeueindex; i++)
{
//printf("%d", i);
printf("%d \n", q->queuespace[i]);
}
}
/* The following function frees the space required for the queue. */
void queue_delete(Queue *q) {
// Speicher, dass durch die queuespace beansprucht wurde, wird freigegeben
free(q->queuespace);
// Speicher, dass fuer das Queue benoetigt wurde, wird freigegeben.
free(q);
}
int main()
{
Queue *queue;
queue = queue_new(5);
queue_enqueue(queue, 0);
queue_enqueue(queue, 3);
queue_enqueue(queue, 2);
queue_print(queue);
return 0;
}