wolffd@0: classdef CQueue < handle
wolffd@0: % CQueue define a queue data strcuture
wolffd@0: % 
wolffd@0: % It likes java.util.Queue, however, it could use CQueue.content() to
wolffd@0: % return all the data (in cells) of the Queue, and it is a litter faster
wolffd@0: % than java's Queue.
wolffd@0: % 
wolffd@0: %   q = CQueue(c); c is a cells, and could be omitted
wolffd@0: %   s.size() return the numble of element
wolffd@0: %   s.isempty() return true when the queue is empty
wolffd@0: %   s.empty() delete all the elements in the queue.
wolffd@0: %   s.push(el) push el to the top of qeueu
wolffd@0: %   s.pop() pop out the the beginning of queue, and return the element
wolffd@0: %   s.front() return the the the beginning element of the qeueu
wolffd@0: %   s.back() return the the the rear element of the qeueu
wolffd@0: %   s.remove() remove all data from the queue
wolffd@0: %   s.content() return all the data of the queue (in the form of a
wolffd@0: %   cells with size [s.size(), 1]
wolffd@0: %   
wolffd@0: % See also CList, CStack
wolffd@0: % Copyright: zhang@zhiqiang.org, 2010.
wolffd@0: % url: http://zhiqiang.org/blog/it/matlab-data-structures.html
wolffd@0: 
wolffd@0:     properties (Access = private)
wolffd@0:         buffer      % a cell, to maintain the data
wolffd@0:         beg         % the start position of the queue
wolffd@0:         rear        % the end position of the queue
wolffd@0:                     % the actually data is buffer(beg:rear-1)
wolffd@0:     end
wolffd@0:     
wolffd@0:     properties (Access = public)
wolffd@0:         capacity    % 栈的容量，当容量不够时，容量扩充为2倍。
wolffd@0:     end
wolffd@0:     
wolffd@0:     methods
wolffd@0:         function obj = CQueue(c) % 初始化
wolffd@0:             if nargin >= 1 && iscell(c)
wolffd@0:                 obj.buffer = [c(:); cell(numel(c), 1)];
wolffd@0:                 obj.beg = 1;
wolffd@0:                 obj.rear = numel(c) + 1;
wolffd@0:                 obj.capacity = 2*numel(c);
wolffd@0:             elseif nargin >= 1
wolffd@0:                 obj.buffer = cell(100, 1);
wolffd@0:                 obj.buffer{1} = c;
wolffd@0:                 obj.beg = 1;
wolffd@0:                 obj.rear = 2;
wolffd@0:                 obj.capacity = 100;                
wolffd@0:             else
wolffd@0:                 obj.buffer = cell(100, 1);
wolffd@0:                 obj.capacity = 100;
wolffd@0:                 obj.beg = 1;
wolffd@0:                 obj.rear = 1;
wolffd@0:             end
wolffd@0:         end
wolffd@0:         
wolffd@0:         function s = size(obj) % 队列长度
wolffd@0:             if obj.rear >= obj.beg
wolffd@0:                 s = obj.rear - obj.beg;
wolffd@0:             else
wolffd@0:                 s = obj.rear - obj.beg + obj.capacity;
wolffd@0:             end
wolffd@0:         end
wolffd@0:         
wolffd@0:         function b = isempty(obj)   % return true when the queue is empty
wolffd@0:             b = ~logical(obj.size());
wolffd@0:         end
wolffd@0:         
wolffd@0:         function s = empty(obj) % clear all the data in the queue
wolffd@0:             s = obj.size();
wolffd@0:             obj.beg = 1;
wolffd@0:             obj.rear = 1;
wolffd@0:         end
wolffd@0:         
wolffd@0:         function push(obj, el) % 压入新元素到队尾
wolffd@0:             if obj.size >= obj.capacity - 1
wolffd@0:                 sz = obj.size();
wolffd@0:                 if obj.rear >= obj.front
wolffd@0:                     obj.buffer(1:sz) = obj.buffer(obj.beg:obj.rear-1);                    
wolffd@0:                 else
wolffd@0:                     obj.buffer(1:sz) = obj.buffer([obj.beg:obj.capacity 1:obj.rear-1]);
wolffd@0:                 end
wolffd@0:                 obj.buffer(sz+1:obj.capacity*2) = cell(obj.capacity*2-sz, 1);
wolffd@0:                 obj.capacity = numel(obj.buffer);
wolffd@0:                 obj.beg = 1;
wolffd@0:                 obj.rear = sz+1;
wolffd@0:             end
wolffd@0:             obj.buffer{obj.rear} = el;
wolffd@0:             obj.rear = mod(obj.rear, obj.capacity) + 1;
wolffd@0:         end
wolffd@0:         
wolffd@0:         function el = front(obj) % 返回队首元素
wolffd@0:             if obj.rear ~= obj.beg
wolffd@0:                 el = obj.buffer{obj.beg};
wolffd@0:             else
wolffd@0:                 el = [];
wolffd@0:                 warning('CQueue:NO_DATA', 'try to get data from an empty queue');
wolffd@0:             end
wolffd@0:         end
wolffd@0:         
wolffd@0:         function el = back(obj) % 返回队尾元素            
wolffd@0:             
wolffd@0:            if obj.rear == obj.beg
wolffd@0:                el = [];
wolffd@0:                warning('CQueue:NO_DATA', 'try to get data from an empty queue');
wolffd@0:            else
wolffd@0:                if obj.rear == 1
wolffd@0:                    el = obj.buffer{obj.capacity};
wolffd@0:                else
wolffd@0:                    el = obj.buffer{obj.rear - 1};
wolffd@0:                end
wolffd@0:             end
wolffd@0:             
wolffd@0:         end
wolffd@0:         
wolffd@0:         function el = pop(obj) % 弹出队首元素
wolffd@0:             if obj.rear == obj.beg
wolffd@0:                 error('CQueue:NO_Data', 'Trying to pop an empty queue');
wolffd@0:             else
wolffd@0:                 el = obj.buffer{obj.beg};
wolffd@0:                 obj.beg = obj.beg + 1;
wolffd@0:                 if obj.beg > obj.capacity, obj.beg = 1; end
wolffd@0:             end             
wolffd@0:         end
wolffd@0:         
wolffd@0:         function remove(obj) % 清空队列
wolffd@0:             obj.beg = 1;
wolffd@0:             obj.rear = 1;
wolffd@0:         end
wolffd@0:         
wolffd@0:         function display(obj) % 显示队列
wolffd@0:             if obj.size()
wolffd@0:                 if obj.beg <= obj.rear 
wolffd@0:                     for i = obj.beg : obj.rear-1
wolffd@0:                         disp([num2str(i - obj.beg + 1) '-th element of the stack:']);
wolffd@0:                         disp(obj.buffer{i});
wolffd@0:                     end
wolffd@0:                 else
wolffd@0:                     for i = obj.beg : obj.capacity
wolffd@0:                         disp([num2str(i - obj.beg + 1) '-th element of the stack:']);
wolffd@0:                         disp(obj.buffer{i});
wolffd@0:                     end     
wolffd@0:                     for i = 1 : obj.rear-1
wolffd@0:                         disp([num2str(i + obj.capacity - obj.beg + 1) '-th element of the stack:']);
wolffd@0:                         disp(obj.buffer{i});
wolffd@0:                     end
wolffd@0:                 end
wolffd@0:             else
wolffd@0:                 disp('The queue is empty');
wolffd@0:             end
wolffd@0:         end
wolffd@0:         
wolffd@0:         function c = content(obj) % 取出队列元素
wolffd@0:             if obj.rear >= obj.beg
wolffd@0:                 c = obj.buffer(obj.beg:obj.rear-1);                    
wolffd@0:             else
wolffd@0:                 c = obj.buffer([obj.beg:obj.capacity 1:obj.rear-1]);
wolffd@0:             end
wolffd@0:         end
wolffd@0:     end
wolffd@0: end