Matlab deque实现

柳梦璃

车辆工程

一直以来数据结构这块是MATLAB的弱项，虽然其不支持指针，但是一些比较简单的数据结果还是能胜任的。

之前的工作中，有需要将C++代码移植到MATLAB上的需求，其中就使用到了deque，由于当时时间比较紧迫就没有多考虑，使用ring buffer实现了，但回来仔细想想，其实MATLAB也可以支持动态数组，所以也尝试一下使用动态数组来实现deque。代码比较简单，直接贴出，使用类来实现的。

classdef Deque < handle
    properties (Constant)
        MaxQueueSize = 1000
    properties
    methods
        function obj = Deque()
            coder.inline('never')
            obj.data = [];
            obj.size = 0;
        function pushBack(this,u)
            coder.inline('never')
            this.data = [this.data u];
            this.size = this.size+1;
        function pushFront(this,u)
            coder.inline('never')
            this.data = [u this.data];
            this.size = this.size+1;
        function [err,y] = popBack(this)
            coder.inline('never')
            err = true;
            y = 0;
            if this.size <= 0
                return;
            y = this.data(end);
            this.data = this.data(1:end-1);
            this.size = this.size-1;
            err = false;
        function [err,y] = popFront(this)
            coder.inline('never')
            err = true;
            y = 0;
            if this.size <= 0
                return;
            y = this.data(1);
            this.data = this.data(2:end);
            this.size = this.size-1;
            err = false;
        function y = isEmpty(this)
            coder.inline('never')
            y = (this.size == 0);
        function clearData(this)
            coder.inline('never')
            this.data = [];
            this.size = 0;

测试代码也贴出

function xDeque()
q = Deque();
for i = 1:Deque.MaxQueueSize
    q.pushBack(1);
for i = 1:100
    [err,y] = q.popFront();
for i = 1:100
    q.pushFront(2);
q.clearData();
y = q.isEmpty();
for i = 1:Deque.MaxQueueSize
    q.pushFront(3);
for i = 1:100
    [err,y] = q.popBack();
for i = 1:100
    q.pushBack(4);
q.clearData();
end

代码非常直接，直接使用MATLAB的index特性，也非常直观。coder.inline('never')保证每一个method都能被生成一个函数而不是内联函数，但是这会报错，错误如下，但是此时可变大小已经打开。

        function obj = Deque()
            coder.inline('never')
            data = [];
            coder.varsize('data',[1,Deque.MaxQueueSize])
            obj.data = data;
            obj.size = 0;
        end

通过上面的代码指定data为可变大小，最大大小为Deque.MaxQueueSize。可以稍微看一下MATLAB生成的代码其实是重新分配空间然后重新拷贝，这其实不太好。

void Deque_pushFront(Deque *this, double u)
  emxArray_real_T *b_u;
  int i5;
  int loop_ub;
  emxInit_real_T(&b_u, 2);
  i5 = b_u->size[0] * b_u->size[1];
  b_u->size[0] = 1;
  b_u->size[1] = 1 + this->data->size[1];
  emxEnsureCapacity_real_T(b_u, i5);
  b_u->data[0] = u;
  loop_ub = this->data->size[1];
  for (i5 = 0; i5 < loop_ub; i5++) {
    b_u->data[i5 + 1] = this->data->data[i5];
  i5 = this->data->size[0] * this->data->size[1];
  this->data->size[0] = 1;
  this->data->size[1] = b_u->size[1];
  emxEnsureCapacity_real_T(this->data, i5);
  loop_ub = b_u->size[0] * b_u->size[1];
  for (i5 = 0; i5 < loop_ub; i5++) {
    this->data->data[i5] = b_u->data[i5];
  emxFree_real_T(&b_u);
  this->size++;
}

这里也放一下使用ring buffer完成同样功能的代码，不需要动态分配空间。特别说明一下，obj.head =1;obj.tail = lDeque.MaxQueueSize; 这两行代码给head和tail初值，这样做可以保证对空的deque中push front和push back能做到和非空时候一样，无需特殊处理空deque的情况。如果deque的size非0，head指向第一个元素tail指向最后一个元素。

classdef lDeque < handle
    properties (Constant)
        MaxQueueSize = 1000
    properties
    methods
        function obj = lDeque()
            coder.inline('never')
            obj.data = zeros(1,lDeque.MaxQueueSize);
            obj.head = 1;
            obj.tail = lDeque.MaxQueueSize;
            obj.size = 0;
        function err = pushBack(this,u)
            coder.inline('never')
            err = true;
            if this.size == lDeque.MaxQueueSize
                return
            xtail = this.tail+1;
            if xtail > lDeque.MaxQueueSize
                xtail = xtail-lDeque.MaxQueueSize;
            this.data(xtail) = u;
            this.tail = xtail;
            this.size = this.size+1;
            err = false;
        function err = pushFront(this,u)
            coder.inline('never')
            err = true;
            if this.size == lDeque.MaxQueueSize
                return
            xhead = this.head-1;
            if xhead < 1
                xhead = xhead+lDeque.MaxQueueSize;
            this.data(xhead) = u;
            this.head = xhead;
            this.size = this.size+1;
            err = false;
        function [err,y] = popBack(this)
            coder.inline('never')
            err = true;
            y = 0;
            if this.size <= 0
                return
            elseif this.size == 1
                y = this.data(this.tail);
                this.clearData();
                xtail = this.tail;
                y = this.data(xtail);
                xtail = xtail-1;
                if xtail < 1
                    xtail = xtail+lDeque.MaxQueueSize;
                this.tail = xtail;
                this.size = this.size-1;
            err = false;
        function [err,y] = popFront(this)
            coder.inline('never')
            err = true;
            y = 0;
            if this.size <= 0
                return
            elseif this.size == 1
                y = this.data(this.head);
                this.clearData();
                xhead = this.head;
                y = this.data(xhead);
                xhead = xhead+1;
                if xhead > lDeque.MaxQueueSize
                    xhead = xhead-lDeque.MaxQueueSize;
                this.head = xhead;
                this.size = this.size-1;
            err = false;
        function y = isEmpty(this)
            y = (this.size == 0);
        function clearData(this)
            coder.inline('never')
            this.data = zeros(1,lDeque.MaxQueueSize);
            this.head = 1;
            this.tail = lDeque.MaxQueueSize;
            this.size = 0;
end

通过ring buffer的方式生成的代码非常简洁，执行效率也很高，下面附上push front的代码，请读者和使用动态数组的方式对比一下。

void lDeque_pushFront(lDeque *this, double u)
  double xhead;
  if (!(this->size == 1000.0)) {
    xhead = this->head - 1.0;
    if (xhead < 1.0) {
      xhead += 1000.0;