Circular Queue

/* circular_queue_example_03.c */

/* by Andrew A.*/

/* Last edit: Wed 15 Aug 19:43:12 ACST 2018 */

/* A slightly less simple demonstration of a circular queue */

/*

This version has been modified to allow a buffer, based on a

circular-queue, or "queue-array", to contain more than one item

in each list-item.

This is achieved by defining the queue_item as a struct{},

rather than a single number.

*/

/* We can define the maximum length of the queue*/

#define MAX_LENGTH 2

/* You may want to increase MAX_LENGTH, quite a bit... */

/* We are free to define the items that will be in a queue_item */

typedef struct

{

int thing1;

int thing2;

} queue_item;

/* For information about "things" see:

http://seuss.wikia.com/wiki/Thing_One_and_Thing_Two?file=Thing1-and-thing2.jpg */

/* An easy solution, to the access problem, is to make the queue global */

/* This will be a First-In First-Out (FIFO) queue*/

queue_item queue_store[MAX_LENGTH]; /* Defines the memory-space to be used by the queue */

int next_sub = 0 ; /* The subscript at which we should store the next item*/

int n_items = 0 ; /* There are initially no items in the queue*/

#include

/* function prototypes */

int add_list_item(queue_item);

void print_list_items(void);

int dispatch_list_item(queue_item *);

int get_queue_item(queue_item* );

/* build up a circular queue, using entries from stdin() */

int main()

{

queue_item input_value ; /* reserved for input values */

int error_code = 0; /* used for return-values, error codes */

queue_item output_value; /* reserved for output values */

int max_n_items = 0; /* used to invert the sequence of values for trace-printing */

int ret_val = 0; /* Used as a return value from get_queue_item() */

/* initialise the temporary storage values */

input_value.thing1 = 0;

input_value.thing2 = 0;

output_value.thing1 = 0;

output_value.thing2 = 0;

ret_val = get_queue_item( &input_value); /* Get the data for the next queue item */

/* Insert some items */

while((ret_val > 0) & (n_items

{

error_code = add_list_item(input_value);

print_list_items(); /* trace print the list */

ret_val = get_queue_item( &input_value); /* Get the data for the next queue item */

}

printf(" ");

/* Dispatch the items in the queue */

printf("Dispatch of the items in the queue: ");

max_n_items = n_items ;

printf("{ ");

while(n_items>0)

{

printf(" item number %d is ",(max_n_items-n_items+1));

error_code = dispatch_list_item(&output_value);

printf(" (%d,%d) , ", output_value.thing1, output_value.thing2 );

}

printf(" } ");

/* and we are done */

return 0;

}

/* end of main() */

/* //////////////////////////////////////////////////////////// */

/* insert an item into the queue */

/* This could be a First-In First-Out (FIFO) queue*/

int add_list_item(queue_item input_value)

{

if (n_items

{

queue_store[next_sub].thing1 = input_value.thing1;

queue_store[next_sub].thing2 = input_value.thing2;

next_sub = (next_sub+1) % MAX_LENGTH ; /* increment the next_sub subscript*/

n_items++ ;

return 0 ; /* normal completion */

}

else

return 1 ; /* return an error code, the queue is full*/

}

/* list all the items in the queue*/

void print_list_items(void)

{

int k;

int sub ;

printf("The list is: {");

for (k=1; k

{

sub = (next_sub+(MAX_LENGTH-k)) % MAX_LENGTH ;

printf(" (%d,%d) ", (queue_store[ sub ]).thing1, (queue_store[ sub ]).thing2 );

}

printf("} ");

}

/* dispatch an item from the queue on an FIFO basis*/

int dispatch_list_item(queue_item *output_value)

/* the return value is an error-code */

/* output_value is referenced by address, after the fashion of scanf() */

{

int sub;

if (n_items > 0 )

{

/* There is at least one item in the queue */

/* access the item at the top or "head" of the queue*/

sub = (next_sub+(MAX_LENGTH-n_items))%MAX_LENGTH ;

(*output_value).thing1 = queue_store[sub].thing1;

(*output_value).thing2 = queue_store[sub].thing2;

n_items-- ; /* decrement the next_sub subscript*/

return 0 ; /* normal completion */

}

else

return 1 ; /* return an error code, the queue is full*/

}

/* Get the data for a single queue item and assemble it into a queue item */

int get_queue_item(queue_item* input_value)

{

int error_code = 0;

int thingy1, thingy2;

printf(" Please enter a positive integer, for thing1: ");

error_code = scanf("%d", &thingy1 );

/* later on this might be a PID using getpid() */

printf("Please enter a positive integer, for thing2: ");

error_code = scanf("%d", &thingy2 );

/* later on, this might be an elapsed time, e_time*/

/* Allocated the values, input from scanf(), to the return value,

pointed to by input_value*/

(*input_value).thing1 = thingy1;

(*input_value).thing2 = thingy2;

/* return the value of the smallest argument */

if(thingy1>thingy2)

return thingy2;

else

return thingy1;

}

/*

A sample output:

> ./circular_queue_example_03

Please enter a positive integer, for thing1: 3

Please enter a positive integer, for thing2: 5

The list is: { (3,5) }

Please enter a positive integer, for thing1: 7

Please enter a positive integer, for thing2: 9

The list is: { (7,9) (3,5) }

Please enter a positive integer, for thing1: 0

Please enter a positive integer, for thing2: 0

Dispatch of the items in the queue

{

item number 1 is (3,5) ,

item number 2 is (7,9) ,

}

>

*/

4 Temporary storage of data, in a buffer Buffers are typically used when there is a temporary difference between the rate at which data is received and the rate at which it can be processed. If events arrive at random then they can arrive in bursts, and the time between events can be shorter than the time that is taken to dispatch the events. Some sort of temporary structure is needed to store the data, in a temporary structure, so that it is not list. These structures are called "buffers". We will be using a First-In First-Out (FIFO) queue to buffer the events. 4.1 circular_queue_example_02.c Compile and run the example program, circular_queue_example_02.c. When it is running you should enter a sequence of positive integers. As the numbers are entered at the console, they are entered into the circular buffer. If a zero, or negative number is entered then entry will cease, and the events will all be dispatched, in order. If the capacity of the buffer is exceeded then entry will cease, and the events will all be dispatched, in order. There are a couple of questions to consider