Is there a "queue" in MATLAB?

Question

I want to convert a recursive function to a iterative one. What I normally do is, I initialize a queue, put the first job into queue. Then in a while loop I consume jobs from queue and add new ones to the queue. If my recursive function calls itself multiple times (e.g walking a tree with many branches) multiple jobs are added. Pseudo code:

queue = new Queue();
queue.put(param);
result = 0;

while (!queue.isEmpty()) {
    param = queue.remove();
    // process param and obtain new param(s)
    // change result
    queue.add(param1);
    queue.add(param2);
}

return result;

I cannot find any queue like structure in MATLAB though. I can use vector to simulate queue where adding 3 to queue is like:

a = [a 3]

and removing element is

val = a(1);
a(1) = [];

If I got the MATLAB way right, this method will be a performance killer.

Is there a sane way to use a queue in MATLAB?

What about other data structures?

Solution 1

If you insist on using proper data structures, you can use Java from inside MATLAB:

import java.util.LinkedList
q = LinkedList();
q.add('item1');
q.add(2);
q.add([3 3 3]);
item = q.remove();
q.add('item4');

Solution 2

Ok, here's a quick-and-dirty, barely tested implementation using a MATLAB handle class. If you're only storing scalar numeric values, you could use a double array for "elements" rather than a cell array. No idea about performance.

classdef Queue < handle
    properties ( Access = private )
        elements
        nextInsert
        nextRemove
    end

    properties ( Dependent = true )
        NumElements
    end

    methods
        function obj = Queue
            obj.elements = cell(1, 10);
            obj.nextInsert = 1;
            obj.nextRemove = 1;
        end
        function add( obj, el )
            if obj.nextInsert == length( obj.elements )
                obj.elements = [ obj.elements, cell( 1, length( obj.elements ) ) ];
            end
            obj.elements{obj.nextInsert} = el;
            obj.nextInsert = obj.nextInsert + 1;
        end
        function el = remove( obj )
            if obj.isEmpty()
                error( 'Queue is empty' );
            end
            el = obj.elements{ obj.nextRemove };
            obj.elements{ obj.nextRemove } = [];
            obj.nextRemove = obj.nextRemove + 1;
            % Trim "elements"
            if obj.nextRemove > ( length( obj.elements ) / 2 )
                ntrim = fix( length( obj.elements ) / 2 );
                obj.elements = obj.elements( (ntrim+1):end );
                obj.nextInsert = obj.nextInsert - ntrim;
                obj.nextRemove = obj.nextRemove - ntrim;
            end
        end
        function tf = isEmpty( obj )
            tf = ( obj.nextRemove >= obj.nextInsert );
        end
        function n = get.NumElements( obj )
            n = obj.nextInsert - obj.nextRemove;
        end
    end
end

Solution 3

1. Is a recursive solution really so bad? (always examine your design first).
2. File Exchange is your friend. (steal with pride!)
3. Why bother with the trouble of a proper Queue or a class - fake it a bit. Keep it simple:

q = {};
head = 1;
q{head} = param;
result = 0;
while (head<=numel(q))

    %process param{head} and obtain new param(s)
    head = head + 1;
    %change result
    q{end+1} = param1;
    q{end+1} = param2;
end %loop over q
return result;
 

If the performance suffers from adding at the end too much - add in chunks:

chunkSize = 100;
chunk = cell(1, chunkSize);
q = chunk;
head = 1;
nextLoc = 2;
q{head} = param;
result = 0;
while (head<endLoc)        
    %process param{head} and obtain new param(s)
    head = head + 1;
    %change result
    if nextLoc > numel(q);
        q = [q chunk];
    end
    q{nextLoc} = param1;
    nextLoc = nextLoc + 1;
    q{end+1} = param2;
    nextLoc = nextLoc + 1;
end %loop over q
 return result;

A class is certainly more elegant and reusable - but fit the tool to the task.

Solution 4

I had a need for queue like data structure as well.

Fortunately I had a limited number of elements (n).

They all get into queue at some point but only once.

If you situation is similar you can adapt the simple algorithm using fixed size array and 2 indices.

queue  = zeros( n, 1 );
firstq = 1;
lastq  = 1;

while( lastq >= firstq && firstq <= n )
    i = queue( firstq );    % pull first element from the queue
                            % you do not physically remove it from an array,
                            % thus saving time on memory access
    firstq = firstq + 1;

    % % % % % % % % % % % % % WORKER PART HERE
    % do stuff

    %
    % % % % % % % % % % % % % % % % % % % % %

    queue( lastq ) = j;     % push element to the end of the queue
    lastq = lastq + 1;      % increment index

end;

Solution 5

If you can do with a FIFO queue of predefined size without the need for simple direct access, you can simply use the modulo operator and some counter variable:

myQueueSize = 25;                  % Define queue size
myQueue = zeros(1,myQueueSize);    % Initialize queue

k = 1                              % Counter variable
while 1                            
    % Do something, and then
    % Store some number into the queue in a FIFO manner
    myQueue(mod(k, myQueueSize)+1) = someNumberToQueue;

    k= k+1;                       % Iterate counter
end

This approach is super simple, but has the downside of not being as easily accessed as your typical queue. In other words, the newest element will always be element k, not element 1 etc.. For some applications, such as FIFO data storage for statistical operations, this is not necessarily a problem.

View more solutions

Comments

[Marc]

Why not stay with a recursive function?

[ldasilva]

@Marc: I usually reach max depth for recursion. When I increase max depth MATLAB crashes.

[ldasilva]

Well, I don't insist, I am trying to find my way through MATLAB. Maybe I do not need queue at all to solve my problem, maybe there is a MATLAB way to do this.

[High Performance Mark]

+1: That's certainly the advanced way to go. If this is too advanced, just use a vector with head and tail pointers as @Edric does.

[Marc]

Doubling the size of the queue when full could lead to matlab memory exhaustion quickly, because of Matlab Heap fragmentation. Nice thing about a class is that you can change that to be a constant-size add.

[Mikhail Poda]

yes, recursive solution tends to be worse in most scenarios stackoverflow.com/questions/4137905/…. But the definitive answer can be only given comparing performance of all approaches. Still +1 for keeping the solution simple!

[Giuliano]

+1 Would this be the best? Maybe... Anyway it's simple and has its elegancy.

[tmandry]

For Octave compatibility (if you have the java package installed,) just replace the first 2 lines with q = javaObject('java.util.LinkedList').

[Amro]

@tmandry: thanks, javaObject actually works in both MATLAB and Octave

[Cramer]

If speed is a requirement, for some reason Matlab is MUCH faster if you call add(a, 'item1') and remove(q) and the like

[Amro]

@Cramer: I agree that function notation is sometimes faster than dot notation, this has to do with the way MATLAB dispatches and calls methods: mathworks.com/help/matlab/matlab_prog/… , mathworks.com/help/matlab/matlab_oop/… . See this for an actual comparison of the the versions (among other things): stackoverflow.com/a/1745686/97160

[Alec Jacobson]

Wrapping this in a class seems like a good idea, but would probably hurt performance

[Amro]

The File Exchange contains community-contributed code, not official MathWorks solutions (could be misunderstood from your statement above)

[Pepe Mandioca]

Apparently this is the way to go for performance in pure matlab, since both queue(1)=[] and queue=queue(2:end) perform poorly