3

Does anyone know if there is a way to create a queue of some sort for arduino?

My project consists of simulating multiple traffic lights with crossing pedestrians on an Arduino breadboard. Since I need to assume the situation where on all sides are cars waiting + pedestrians having pressed the button, I needed to figure out a way to store these inputs into an array of some sort.

However, the problem with array I believe is that it doesn't allow me to shift the data to the left, so that the next one will be selected in the queue. Deleting the data inside an array would only merely make it null, which doesn't work.

Greatly appreciated if someone can help me by pointing to the right direction.

  • 3
    This is a pure programming question: the answers would be no different if you were running the same code on a PC instead of an Arduino. You need to ask this on stackoverflow.com. (Well, actually you need to search there for the no doubt many existing questions asking things similar to this. :-)) – Curt J. Sampson Apr 4 '17 at 0:21
  • Oh, so things purely related to Arduino should be posted here, while anything related to coding itself should be done in stackoverflow. Alright, i guess I finally know how this works, time to re-post this in the right place. :) – Tsubakura Apr 4 '17 at 0:31
  • you can't shift array to left but you can move your pointer to right it will work similarly. for eg. your array array=[1,2,3,4,5,\0], you can denote any array element by array[i] and you can increment value of i by i++. – Tanmay Yerunkar Apr 4 '17 at 0:44
  • 1
    Actually, coding related specifically to the Arduino (e.g., "I have a problem when using this Arduino library") should be posted here. But what you've described is a generic programming problem. A good rule of thumb is to think, "would this application work just as well on a PC as on an Arduino, and the code I'm asking about be unchanged or almost unchanged?" – Curt J. Sampson Apr 4 '17 at 0:58
  • Hmm, I guess it then belongs in here? I mean, when it comes to other programming languages like Java, I would have no problem creating an ArrayList instead to do the job. I was actually unsure as to how to do this in arduino, hence why I thought about adding this here instead. I wasn't really used to a different language and the low amount of available memory. xD – Tsubakura Apr 4 '17 at 1:19
2

I wrote a simple queue library some weeks ago, you can find it in the arduino library manager, or here: Queue

I think you need FIFO implementation, but LIFO is also implemented in the lib & possibility to overwrite previous records when full.
It can handle any structure or data type (as long as it's size is fixed for memory allocation), defining a number of records in the queue, then you're good to go.

2 methods are implemented to interact with the queue, push() & pull(). I'll probably add a peek() later on if needed.

I also noticed this other FIFO only queue lib in the library manager when I commited mine: MD_CirQueue

Hope this can help!

1

Regarding how to “create a queue of some sort for Arduino”, about the first thing to settle is how many items may need to be queued. On a typical personal computer with gigabytes of RAM, queue size often is not much of an issue ... one just allocates a few more megabytes whenever necessary. On an typical Arduino, however, with a few kilobytes or few tens of kilobytes of RAM, use of dynamic (heap) allocation is risky unless you carefully analyze possible execution paths.

If you are ok with a fixed queue size, the next issue is what kind of queue, eg FIFO, LIFO, priority, etc. The question's concern about a “shift the data to the left, so that the next one will be selected in the queue” issue suggests a FIFO (first in first out) queue is desired. For this, a circular buffer or circular queue is a relatively-low-overhead method often used. Using terms from the wikipedia article, Start and End pointers are maintained, marking next-data-out and last-data-in positions. Via modular arithmetic or if tests, each of these pointers wraps to array front whenever it goes past the array end. The queue is empty if Start == End (modulo N, if queue size is N) and full if Start == End+1.

If an interrupt-driven process can modify pointers asynchronously to the main thread of execution, then synchronization methods need to be used to ensure atomic updates of pointers. (This is true for all kinds of queues, not just circular ones.)

If instead of a FIFO queue you need a priority queue, a binary heap is easy to implement. Usually Fibonacci heaps and binomial heaps are not worth the extra trouble of implementing, except when you need efficient heap merging or secondary operations like decreasing keys of elements. The Summary of running times section of wikipedia's binomial heap article shows the complexity of different operations across different heap structures. Note that with Arduino RAM being so limited, a complexity difference like Θ(log n) vs Θ(1) is negligible; simplicity of code, leading to a compact implementation, is more important.

Note, also see QueueList Library For Arduino at arduino.cc. This library apparently uses dynamic allocation. It provides methods push(), pop(), peek() et al. Also see QueueArray Library For Arduino at arduino.cc, which provides the same methods as QueueList, plus enqueue and dequeue() as synonyms for push() and pop(). Where QueueList uses lists to build its data structures, QueueArray uses arrays.

OsWrap at arduino.cc is a heavy package (eg 15KB flash, 1.5KB RAM) that supports various message and priority queue structures.

Depending on your rationale for using a queue, Task Scheduler Library may also be of interest.

As noted in Mikael Patel's comments above, Cosa platform software includes a Queue class, which is a “Template class for ring-buffer for queueing data elements”, with usage of the class illustrated in an Event class, which in turn is used in a Job class.

0

I had an arduino project that I needed to build a queue for.

You can download the source code and copy into a file called Queue.h next to your arduino project.ino file.

Here is a simple interactive example (with the Serial monitor) to see how its used, make sure you set the baud rate to 115200 and No new line.

#include "Queue.h":

Queue<char> queue(10);

void setup() {
  Serial.begin(115200);
}

void loop() {
  while(Serial.available()) {
    queue.push(Serial.read());
  }

  Serial.print(millis() / 1000);
  Serial.print(": ");
  int count = queue.count();
  if (count > 0) {
    Serial.print("Found ");
    Serial.print(count);
    Serial.print(" items.. '");
    Serial.print(queue.pop());
    Serial.print("' is the oldest. Next is.. '");
    Serial.print(queue.peek());
    Serial.println("'.");
  } else {
    Serial.println("Nothing to process..."); 
  }
  delay(2000);
}

Not the answer you're looking for? Browse other questions tagged or ask your own question.