einararnason / arduinoqueue

A lightweight linked list type queue implementation, meant for microcontrollers.

ArduinoQueue

A lightweight linked list type queue implementation, meant for microcontrollers. Written as a C++ template class.

Constructors

Creates a queue up to <maximum_number_of_items> items:

ArduinoQueue<T> intQueue(maximum_number_of_items);

Creates a queue up to <maximum_size_in_bytes> bytes:

ArduinoQueue<T> intQueue(0, maximum_size_in_bytes);

Creates a queue up to <maximum_number_of_items> items or <maximum_size_in_bytes> bytes, whatever comes first:

ArduinoQueue<T> intQueue(maximum_number_of_items, maximum_size_in_bytes);

How to use

Include the header file on your code:

#include <ArduinoQueue.h>

Then create the queue according to your needs, examples:

• To create a queue of int, capable of holding 20 items:

ArduinoQueue<int> intQueue(20);

• To create a queue of int, capable of holding 20 items or a maximum size of 10 bytes (whatever comes first):

ArduinoQueue<int> intQueue(20, 10);

• To create a queue of your defined structure, capable of holding 50 items:

struct car {
    char brand[10];
    char model[10];
    int nr_doors;
};
ArduinoQueue<car> myCarsQueue(50);

Finally use the following functions:

intQueue.enqueue(1);    // Adds number 1 to the queue
intQueue.enqueue(123);    // Adds number 123 to the queue
int number = intQueue.dequeue();    // Will return number 1 and remove it from the queue
int number = intQueue.getHead();    // Will return number 123 but leave it still in the queue
int number = intQueue.dequeue();    // Will return number 123 and remove it from the queue

You can use also the following functions to get more queue properties:

bool state = intQueue.isEmpty();    // Returns true if the queue is empty, false otherwise
bool state = intQueue.isFull();    // Returns true if the queue is full, false otherwise
unsigned int n = intQueue.itemCount();    // Returns the number of items currently on the queue
unsigned int n = intQueue.itemSize();    // Returns the size of the item being stored (bytes)
unsigned int n = intQueue.maxQueueSize();    // Returns the maximum possible size of the queue (items)*
unsigned int n = intQueue.maxMemorySize();    // Returns the maximum possible size of the queue (bytes)*

Thread safety

This library is not thread safe. Mutexes are often hardware specific on the way they are optimized to operate. So for the sake of performance and portability, it is left out.

Memory safety

The memory for the queue nodes are dynamically allocated. Note that while the Queue class cleans up the nodes in memory after destructor or dequeue is called, it keeps a copy of the item being queued. So for example if you are queuing pointers, you will need to keep track of the memory behind them.

Performance

CPU: Intel i7-6500U
RAM: DDR4L

Benchmark result (1000 samples):
Enqueued 1000000 ints in average 0.018749799 seconds
Dequeued 1000000 ints in average 0.016496857 seconds
Allocated 15.2588 MB (16 bytes per item)

arduinoqueue's Issues

Already exist queue.h in ESP8266

queue.h already exists in compiler sys includes on ESP8266.
changed cpp/h names and updated examples

getHead() and getTail() : r/w-versions ?

Hi Einar,

thanks a lot for your library!

I suggest to make the getHead() and getTail() functions return references or pointers.
e.g:

T & getHead() {
    if ((count == 0) || (head == nullptr)) {
      T tmp;    
      return &tmp;
    }

    T & item = head->item;
    return item;
  }

In my program I que up outgoing MIDI-messages and have to mark them first as acknowledged and later as answerded before i deque them.
So I need write access to the queued top message in the queue.
If i set the acknowledged flag in my message object at the queue's head i only modify the copy, not the message itself.

I had already changed it inside my installed library file - but the latest update changed it back.
So i would prefer it to be contained in the regular library - could be useful for others as well.
The pointer-version would also make the case with empty queue more consistent by returning a nullptr:

T * getHead() {
    if ((count == 0) || (head == nullptr)) {
          return nullptr;
    }

    return &(head->item);
  }

These different versions could of course co-exist in the library so the user can choose the right one for his use case.

Greetz,
Martin

Compatible with "char"?

Hi all,

Can I use this queue library with char variables instead of int variable?

Thanks,

Zeb

Feature Request: reading the _tail->item

Hi,

Could you please add a feature that is similar to the front() function, but for reading the _tail-> item?

Something like this:
T tail() {
if ((_items_cnt == 0) || (_head == nullptr)) {
return T();
}
T item = _tail->item;
return item;
}

Many thanks

PS: maybe renaming the front() to head() could also be useful for the sake of consistency. :)

Multi-Threading

Thanks very much Einar for such great library!

I have a question please:

Is this Thread-Safe? i.e. changes in the queue are visible to all threads in a multi-threading environment?

Error Version Library Manager

Hi,

the version you download with "Library Manager" is not the same as this one

b.

performance & memory comparisons?

Hi there, firstly thanks for creating this library and making it public.

For one of my projects for an ESP8266 I need to make extensive use of queues (FIFO) for incoming and outgoing buffers. Now that the latest Arduino libraries for the ESP supports some of the C+11 stl libraries I switched from my homegrown solution to comparing std::queue, std::deque and std::list.

I was wondering whether you had done any comparisons yourself, on speed or heap consumption?

Question: What did I misunderstand?

Hello, 😊
I'm fairly new to programming and the only experience I have with it is through Arduino IDE.

My project consists of 6 LED's, 6 push-buttons working as initiators for the LED's and again 6 push-buttons that should reset the LED's to a LOW state. I use Arduino Mega 2560.

I want the first button pushed to be nr. 1 in a queue. If I push button nr. 5, it'll be nr. 1. in the queue. If push button nr. 5 is nr. 1 in the queue, that corresponding LED would be lit.

Then if I push-button nr. 3, that button would be nr. 2 in the queue. But if I push the reset button nr. 5, it would push nr. 5 out, at turn of the corresponding LED. Which would again put button nr. 5 as nr. 1 in the queue.

What have I misunderstood?

Thank you very much beforehand!

This is my code, which unfortunately dosen't work:

`#include "ArduinoQueue.h"

#define resetButton1 13
#define resetButton2 12
#define resetButton3 11
#define resetButton4 10
#define resetButton5 9
#define resetButton6 8

#define led1 23
#define led2 25
#define led3 27
#define led4 29
#define led5 31
#define led6 33

#define externalButton1 54
#define externalButton2 55
#define externalButton3 56
#define externalButton4 57
#define externalButton5 58
#define externalButton6 59

int extState1;
int extState2;
int extState3;
int extState4;
int extState5;
int extState6;

int resState1;
int resState2;
int resState3;
int resState4;
int resState5;
int resState6;

ArduinoQueue intQueue(6);

int dq = intQueue.dequeue();
int qFront = intQueue.front();

void setup()
{
pinMode(resetButton1, INPUT);
pinMode(resetButton2, INPUT);
pinMode(resetButton3, INPUT);
pinMode(resetButton4, INPUT);
pinMode(resetButton5, INPUT);
pinMode(resetButton6, INPUT);

pinMode(led1, OUTPUT);
pinMode(led2, OUTPUT);
pinMode(led3, OUTPUT);
pinMode(led4, OUTPUT);
pinMode(led5, OUTPUT);
pinMode(led6, OUTPUT);

pinMode(externalButton1, INPUT);
pinMode(externalButton2, INPUT);
pinMode(externalButton3, INPUT);
pinMode(externalButton4, INPUT);
pinMode(externalButton5, INPUT);
pinMode(externalButton6, INPUT);

}

void loop()
{
extState1 = analogRead(externalButton1);
extState2 = analogRead(externalButton2);
extState3 = analogRead(externalButton3);
extState4 = analogRead(externalButton4);
extState5 = analogRead(externalButton5);
extState6 = analogRead(externalButton6);

resState1 = digitalRead(resetButton1);
resState2 = digitalRead(resetButton2);
resState3 = digitalRead(resetButton3);
resState4 = digitalRead(resetButton4);
resState5 = digitalRead(resetButton5);
resState6 = digitalRead(resetButton6);

// I have analogRead > 850 because these push-buttons are connected to the
// analog pins of the Arduino

if (extState1 > 850)
{
intQueue.enqueue(1);
}
if (extState2 > 850)
{
intQueue.enqueue(2);
}
if (extState3 > 850)
{
intQueue.enqueue(3);
}
if (extState4 > 850)
{
intQueue.enqueue(4);
}
if (extState5 > 850)
{
intQueue.enqueue(5);
}
if (extState6 > 850)
{
intQueue.enqueue(6);
}

if (resState1 == HIGH)
{
dq = 1;
}
if (resState2 == HIGH)
{
dq = 2;
}
if (resState3 == HIGH)
{
dq = 3;
}
if (resState4 == HIGH)
{
dq = 4;
}
if (resState5 == HIGH)
{
dq = 5;
}
if (resState6 == HIGH)
{
dq = 6;
}

if (qFront == 1)
{
digitalWrite(led1, HIGH);
}
if (qFront == 2)
{
digitalWrite(led2, HIGH);
}
if (qFront == 3)
{
digitalWrite(led3, HIGH);
}
if (qFront == 4)
{
digitalWrite(led4, HIGH);
}
if (qFront == 5)
{
digitalWrite(led5, HIGH);
}
if (qFront == 6)
{
digitalWrite(led6, HIGH);
}
else
{
digitalWrite(led1, LOW);
digitalWrite(led2, LOW);
digitalWrite(led3, LOW);
digitalWrite(led4, LOW);
digitalWrite(led5, LOW);
digitalWrite(led6, LOW);
}
}`

ArduinoQueue.h: No such file or directory

Arduino IDE v1.8.13
ArduinoQueue v1.2.3

$ cd ~
$ find . -name ArduinoQueue.h
./Arduino/libraries/ArduinoQueue/ArduinoQueue.h

Opened the example intQueueItemsSize and compiled:

Queue.h: No such file or directory

Why you want to include Queue.h?
Should not be: `#include ArduinoQueue.h"?