codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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; }
Private
[
?
]
Run code
Submit