MATLAB中是否有“队列”？

Question

我想把一个递归函数转换成迭代函数。 我通常的做法是初始化一个队列，将第一个任务放入队列中。然后在while循环中，我从队列中获取任务并将新任务添加到队列中。如果我的递归函数多次调用自身（例如遍历具有许多分支的树），则会添加多个任务。 伪代码：

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;

虽然在MATLAB中找不到任何类似队列的结构，但我可以使用向量来模拟队列，其中将3添加到队列的方式如下：

a = [a 3]

删除元素是

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

如果我理解 MATLAB 的方式正确的话，这种方法将成为性能杀手。

在 MATLAB 中是否有一种合理的方法来使用队列？

其他数据结构呢？

- nimcap

---

为什么不使用递归函数呢？ - Marc

@Marc：我通常会达到递归的最大深度。当我增加最大深度时，MATLAB 会崩溃。 - nimcap

Answer 1

如果您坚持使用适当的数据结构，您可以在MATLAB内部使用Java:

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

- Amro

---

好的，我不坚持，我正在尝试通过MATLAB找到解决方法。也许我根本不需要队列来解决我的问题，也许有一种MATLAB的方法可以做到这一点。 - nimcap

+1 这是否是最好的选择？也许吧...无论如何，它简单而优雅。 - Giuliano

为了兼容Octave（如果您已安装Java包），只需将前两行替换为q = javaObject('java.util.LinkedList')。 - tmandry

@tmandry：谢谢，javaObject实际上在MATLAB和Octave中都适用。 - Amro

如果速度是一个要求，出于某种原因，如果您调用add（a，“item1”）和remove（q）等函数，Matlab会快得多。 - Cramer

@Cramer：我同意函数符号有时比点符号更快，这与MATLAB分派和调用方法的方式有关：http://www.mathworks.com/help/matlab/matlab_prog/calling-object-methods.html，http://www.mathworks.com/help/matlab/matlab_oop/ordinary-methods.html#brd2n2o-2。请参见此处以进行版本实际比较（以及其他内容）：https://dev59.com/ynI-5IYBdhLWcg3wwLS3#1745686 - Amro

Answer 2

好的，这里是一个使用MATLAB句柄类的快速且未经过充分测试的实现。如果您只存储标量数值，则可以使用双精度数组作为“元素”，而不是单元数组。关于性能方面我没有什么想法。

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

- Edric

---

+1：这绝对是高级的方式。如果这太高级了，就像@Edric一样使用一个带有头和尾指针的向量。 - High Performance Mark

当队列满时，将其大小加倍可能会很快导致Matlab内存耗尽，因为由于Matlab堆碎片化。类的好处是您可以更改其为恒定大小添加。 - Marc

显然，这是在纯Matlab中提高性能的方法，因为queue(1)=[]和queue=queue(2:end)两者都表现不佳。参考链接 - Pepe Mandioca

Answer 3

1. 递归解决方案真的很糟吗？（始终首先检查设计）。
2. 文件交换是您的朋友。（自豪地窃取！）
3. 为什么要费心使用适当的队列或类 - 有点虚假。保持简单：

q = {};
head = 1;
q{head} = param;
result = 0;
while (head<=numel(q))<br>
    %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;
 

如果在结尾添加太多内容导致性能下降 - 可以分批添加：

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;

类显然更加优雅和可重用 - 但需要根据任务选择适合的工具。

- Marc

---

是的，在大多数情况下，递归解决方案往往更糟糕。但是，只有比较所有方法的性能才能得出最终答案。仍然要给您点赞，因为保持解决方案简单！ - Mikhail Poda

将这个内容封装在一个类中似乎是个好主意，但可能会影响性能。 - Alec Jacobson

Answer 4

我需要一种类似于队列的数据结构。

幸运的是，我的元素数量非常有限(n)。

它们在某个时刻都进入队列中，但只会进入一次。

如果你的情况相似，你可以使用固定大小数组和2个索引来适应这个简单算法。

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;

- Antonm

Answer 5

如果您可以使用预定义大小的FIFO队列而不需要简单的直接访问，那么您可以简单地使用取模运算符和一些计数器变量：

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

这种方法非常简单，但它的缺点是不像您通常使用的队列那样易于访问。换句话说，最新的元素始终是元素k，而不是元素1等。对于某些应用程序，例如用于统计操作的FIFO数据存储，这并不一定是问题。

- Tormod Haugene

Answer 6

使用此代码，将其保存为m文件，并使用函数q.pop()等。 这是经过一些修改的原始代码：

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)
    capacity    % ص»µؤبفء؟£¬µ±بفء؟²»¹»ت±£¬بفء؟ہ©³نخھ2±¶،£
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

参考资料： Matlab中的列表、队列和栈结构

- moksef

---

“文件交换”（http://www.mathworks.com/matlabcentral/linkexchange/）包含社区贡献的代码，而非 MathWorks 官方解决方案（这可能会被误解为您上述声明的意思）。 - Amro

Answer 7

在需要仅存储向量（或标量）的队列的情况下，可以使用矩阵和circshift()函数来实现具有固定长度的基本队列，这并不困难。

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

推送：

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

弹出：

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

- Paul Wintz