# Implementing a queue in matlab

## weblog/

Here's a basic queue in MATLAB you could save in `queue_array.m`

``````% http://www.cs.bu.edu/teaching/c/queue/array/types.html
% Extending handle is very important!!
% See http://stackoverflow.com/a/13867697/148668
classdef queue_array < handle
properties ( Access = public )
elems = zeros(1,1);
first = 0;
last = 0;
end
methods
function this = Queue()
end
function push(this,elem)
this.last = this.last+1;
if this.last > numel(this.elems)
elems = [elems;zeros(numel(elems),1)];
end
this.elems(this.last) = elem;
end
function ret = empty(this)
ret = this.last-this.first == 0;
end
function elem = front(this)
if this.empty()
error('Empty Queue');
end
elem = this.elems(this.first+1);
end
function pop(this)
this.first = this.first + 1;
if (this.last-this.first)<0.25*numel(this.elems)
this.elems = this.elems(this.first+1:this.last);
this.first = 0;
this.last = numel(this.elems);
end
end
end
end
``````

It implements `push`,`pop`,`front` and `empty`. It does some resizing to amortize the costs, but you could also just preallocate with a certain size `n`.

However, using this as a class is going to be slow. Instead, you should use this as a reference and include the variables `elems`, `first`, `last` in your scope, removing all the `this.`s. This will be much faster (like 250x times faster).

It wouldn't be to much work to make this a circular implementation which would then probably reallocate and copy less often. But if you can put an upper bound on the number of pushes then just use that as your initial size (assuming it fits into memory).

Comparing pushing to the back and appending to a matlab array (`elems(end+1) = elem`) this is equivalent: amortized constant with occasional expensive reallocates.

Comparing to popping from front and slicing out the back of a matlab array (`elems = elems(2:end)`) this is much faster.

This is really less a lesson about implementing a queue and more an assertion that `elems = elems(2:end)` causes a lot of reallocation and should be avoided. Things are off the charts worse if you use `A(1) = []`. Here's a comparison for popping 10,000 elements: