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