# Is there a "queue" in MATLAB?

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
}

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?

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

```import java.util.LinkedList
item = q.remove();
```

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
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
```

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 = {};
result = 0;
%process param{head} and obtain new param(s)
%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;
nextLoc = 2;
result = 0;
%process param{head} and obtain new param(s)
%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.

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

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.

Use this code, save the code as a m file, and use the functions such q.pop() etc. this is the original code with some modifications:

```properties (Access = private)
buffer      % a cell, to maintain the data
beg         % the start position of the queue
rear        % the end position of the queue
% the actually data is buffer(beg:rear-1)
end

properties (Access = public)
end

methods
function obj = CQueue(c) % ³ُت¼»¯
if nargin >= 1 && iscell(c)
obj.buffer = [c(:); cell(numel(c), 1)];
obj.beg = 1;
obj.rear = numel(c) + 1;
obj.capacity = 2*numel(c);
elseif nargin >= 1
obj.buffer = cell(100, 1);
obj.buffer{1} = c;
obj.beg = 1;
obj.rear = 2;
obj.capacity = 100;
else
obj.buffer = cell(100, 1);
obj.capacity = 100;
obj.beg = 1;
obj.rear = 1;
end
end

function s = size(obj) % ¶سءذ³¤¶ب
if obj.rear >= obj.beg
s = obj.rear - obj.beg;
else
s = obj.rear - obj.beg + obj.capacity;
end
end

function b = isempty(obj)   % return true when the queue is empty
b = ~logical(obj.size());
end

function s = empty(obj) % clear all the data in the queue
s = obj.size();
obj.beg = 1;
obj.rear = 1;
end

function push(obj, el) % ر¹بëذآشھثطµ½¶سخ²
if obj.size >= obj.capacity - 1
sz = obj.size();
if obj.rear >= obj.beg
obj.buffer(1:sz) = obj.buffer(obj.beg:obj.rear-1);
else
obj.buffer(1:sz) = obj.buffer([obj.beg:obj.capacity 1:obj.rear-1]);
end
obj.buffer(sz+1:obj.capacity*2) = cell(obj.capacity*2-sz, 1);
obj.capacity = numel(obj.buffer);
obj.beg = 1;
obj.rear = sz+1;
end
obj.buffer{obj.rear} = el;
obj.rear = mod(obj.rear, obj.capacity) + 1;
end

function el = front(obj) % ·µ»ط¶ست×شھثط
if obj.rear ~= obj.beg
el = obj.buffer{obj.beg};
else
el = [];
warning('CQueue:NO_DATA', 'try to get data from an empty queue');
end
end

function el = back(obj) % ·µ»ط¶سخ²شھثط

if obj.rear == obj.beg
el = [];
warning('CQueue:NO_DATA', 'try to get data from an empty queue');
else
if obj.rear == 1
el = obj.buffer{obj.capacity};
else
el = obj.buffer{obj.rear - 1};
end
end

end

function el = pop(obj) % µ¯³ِ¶ست×شھثط
if obj.rear == obj.beg
error('CQueue:NO_Data', 'Trying to pop an empty queue');
else
el = obj.buffer{obj.beg};
obj.beg = obj.beg + 1;
if obj.beg > obj.capacity, obj.beg = 1; end
end
end

function remove(obj) % اه؟ص¶سءذ
obj.beg = 1;
obj.rear = 1;
end

function display(obj) % دشت¾¶سءذ
if obj.size()
if obj.beg <= obj.rear
for i = obj.beg : obj.rear-1
disp([num2str(i - obj.beg + 1) '-th element of the stack:']);
disp(obj.buffer{i});
end
else
for i = obj.beg : obj.capacity
disp([num2str(i - obj.beg + 1) '-th element of the stack:']);
disp(obj.buffer{i});
end
for i = 1 : obj.rear-1
disp([num2str(i + obj.capacity - obj.beg + 1) '-th element of the stack:']);
disp(obj.buffer{i});
end
end
else
disp('The queue is empty');
end
end

function c = content(obj) % ب،³ِ¶سءذشھثط
if obj.rear >= obj.beg
c = obj.buffer(obj.beg:obj.rear-1);
else
c = obj.buffer([obj.beg:obj.capacity 1:obj.rear-1]);
end
end
end end
```

Reference: list, queue, stack Structures in Matlab

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;
```

In the case where you need a queue only to store vectors (or scalars), then it is not difficult to use a matrix along with the circshift() function to implement a basic queue with a fixed length.

```% Set the parameters of our queue
n = 4; % length of each vector in queue
max_length = 5;

% Initialize a queue of length of nx1 vectors
queue = NaN*zeros(n, max_length);
queue_length = 0;
```

To push:

```queue = circshift(queue, 1, 2); % Move each column to the right
queue(:,1) = rand(n, 1); % Add new vector to queue
queue_length = min(max_length, queue_length + 1);
```

To pop:

```result = queue(:,last)
queue(:, last) = NaN;
queue_length = max(1, queue_length - 1);
```