Using an array as a queue

Question

I recently created a state machine for my latest Arduino project. It is a simple LED control, but it has many different modes and functions. I created a template for my state machine so I can use it in the future, but I am looking to take it to the next level. Here is a copy of the current template for reference:

/*Setup Variables here*/
int nextState;
int currState;
/*Fill enum with all case names*/
enum cases{
 init;
 idle;
 case1;
 case2;
 leave;
};
/*Begin Program*/
void setup(){
 Serial.begin(9600);
 currState = init;
}
void loop(){
 switch(currState){
 case init:
 /*Prepare program here*/
 nextState = idle;
 break;
 case idle:
 if (input1){
 nextState = case1;
 }else if (input2){
 nextState = case2;
 }else{
 nextState = idle;
 } 
 case case1:
 //Code for case1 here
 break;
 case case2:
 //Code for case2 here
 break;
 }
 currState = nextState;
}

I am trying to make a Queued State Machine (QSM). This means that instead of a single variable nextState, I can add several states to be executed. Is the best way to do this an array? I have not found much in my research about how to add and remove elements easily, so if this is the best way, could you point me towards a good tutorial on these types of array functions?

Thanks in advanced for all the help!

• Chris Stratton: You can use an array as a queue, if you use resetting indicies (or pointers) to circularize it, but if you end up with more than one thread (anything in an interrupt) be careful of consistency. You could also I guess do it using a linked list, but that's a heavyweight solution for a chip with such limited resources.

Answer 1

Have an array with fixed size, and have two indexes. One pointing to the first/current item in the queue, the other to the last item in the queue.

(It actually better/easier to have the second index point to where the next item has to be written)

To add an item to the queue:

1. Check that that the queue isn't full (second index is the same as the first)
2. If not write to second index.
3. Increment second index, and modulo array/queue size, so it wraps around.

To read from the queue

1. Read value at the first index
2. Increment first index, modulo array/queue size

• Duncan C: What Gerben says. This is the exact way to do it, and is explained clearly and simply. (Voted)