数组实现的循环队列

队列是一种常见的数据结构,是一个特殊的有序表,起插入操作都在表的一端进行,而删除操作都在表的另外一端进行,所以队列也称先进先出(FIFO)表。可以基于链表实现也可以基于数组实现。我们现在讲基于数组实现,队列的结构如下:

[cpp]
struct Queue {
T *queue; /* 存储用的数组 */
int capacity; /* 存放个数 */
int front ; /* 指向队首 */
int rear; /* 指向队尾 */
};
[/cpp]

基于数组实现的线性队列很好实现,但这种顺序存储表示存在缺陷,很显然,随着时间的推移,队列逐渐右移。这意味着队列尾下标最终等于MAX_QUEUE_SIZE – 1,说明队列已满,此时需要把整个队列向左移动,使得第一个元素再次位于queue[0],切front = -1,同时还要重新计算rear,使其处在正确的位置上。数组的移动开销很大,特别是当队列中包含大量元素时。

如果将数组queue[MAX_QUEUE_SIZE ]看成是循环的,那么我得到一种更有效的存储表示。这就是循环队列了。

由于必须班长下标front和rear能够循环移动,所以实现循环队列的插入和删除操作要稍微困难些,通常利用模运算可以达到此目的,在插入操作是,队尾下标的循环移动实现语句为:

rear  = (rear + 1)%MAX_QUEUE_SIZE ;

注意在插入时,首先循环移动rear,然后将元素存入队列queue[rear],类似的,在删除过程中,首先用下面语句循环移动front:

front= (front+ 1)%MAX_QUEUE_SIZE ;

然后再删除元素。

下面我们给出c++的实现:

[cpp]
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>

/*
* 功能:数组实现的循环队列,C++实现,供学习
*/

using namespace std;

template <typename T>
class CircleQueue {
private:
T *queue; /* 存储用的数组 */
int capacity; /* 存放个数 */
int front ; /* 指向队首 */
int rear; /* 指向队尾 */
public:
CircleQueue( int a ); /* 无参构造 */
CircleQueue(); /*有参构造 */
~CircleQueue(); /* 析构 */
bool isEmpty(); /* 判断空 */

int getSize(); /* 返回个数 */

bool push( T a ); /* 入队 */

T pop(); /* 出队 */

};

template<typename T>
CircleQueue<T>::CircleQueue( int a ) : front ( 0 ),
rear( 0 ), capacity( a ), queue( NULL )
{
queue = new T[capacity];
}
template<typename T>
CircleQueue<T>::CircleQueue() : CircleQueue( 10 )
{
};
template<typename T>
CircleQueue<T>::~CircleQueue()
{
delete[] queue;
}
template<typename T>
bool CircleQueue<T>::isEmpty()
{
if ( front == rear )
return(true);
else
return(false);
}
template<typename T>
int CircleQueue<T>::getSize()
{
return( (rear – front + capacity) % capacity);
}
template<typename T>
bool CircleQueue<T>::push( T a )
{
if ( (rear + 1) % capacity == front )
{
cout<<"queue is full"<<endl;
return(false);
}

queue[rear] = a;
rear = (rear + 1) % capacity;
return(true);
}
template<typename T>
T CircleQueue<T>::pop()
{
if ( rear == front)
{
cout<<"queue is empty"<<endl;
return NULL;
}

T elem;
elem = queue[front];
front = (front + 1) % capacity;
return elem;
}

int main()
{
CircleQueue<string> queue( 6 );
queue.push( "one" );
queue.push( "two" );
queue.push( "three" );
queue.push( "four" );
queue.push( "five" );
queue.push( "six" );//报满
cout << "队列长度" << queue.getSize() << endl;
while ( !queue.isEmpty() )
{
cout << queue.pop() << endl;
}
getchar();
return(0);
}
[/cpp]

运行输出:

queue is full
队列长度5
one
two
three
four
five

cocos2d-x 3.7 实现图片按钮 过滤点击透明区域 在lua中使用

首先在widget头文件添加:
[cpp]
virtual bool AlphaTouchCheck(const Vec2 &point);
virtual bool getAlphaTouchEnable();
virtual void setAlphaTouchEnable(bool isAlphaTouch);
bool _isAlphaTouchEnable = true;
[/cpp]
在widget cpp文件中简单实现
[cpp]
bool Widget::AlphaTouchCheck(const Vec2 &point)
{
return true;
}

bool Widget::getAlphaTouchEnable()
{
return _isAlphaTouchEnable;
}

void Widget::setAlphaTouchEnable(bool isAlphaTouch)
{
_isAlphaTouchEnable = isAlphaTouch;
}
[/cpp]
widget中的判断先默认返回true

把开启的开关放在widget中,方便以后layout 和 imageview的不规则点击。开关默认关闭

接下来就是imageview中重载AlphaTouchCheck 函数
[cpp]
bool ImageView::AlphaTouchCheck(const Vec2& point)
{
if (getAlphaTouchEnable())
{
Image* normalImage = new Image();
normalImage->initWithImageFile(_normalImageString);
auto data = normalImage->getData();
if (data == NULL)
{
return true;
}
auto locationInNode = this->convertToNodeSpace(point);
//图片的0,0 是左上角 所以要和触摸点的Y转换一下 也就是“(normalImage->getHeight() – (int)(locationInNode.y) – 1)”
//该data值是把二维数组展开成一个一维数组, 因为每个像素值由RGBA组成, 所以每隔4个char为一个RGBA, 并且像素以横向排列
int pa = 4 * ((normalImage->getHeight() – (int)(locationInNode.y) – 1) * normalImage->getWidth() + (int)(locationInNode.x)) + 3;
unsigned int ap = data[pa];
if (ap < 20)
{
CC_SAFE_DELETE(normalImage);
return false;
}
else
{
CC_SAFE_DELETE(normalImage);
return true;
}
}
return true;
}
[/cpp]

std::string _normalImageString 是记录创建时候的图片名。

编译工程
接下来在lua中使用
[lua]
imageButton:addTouchEventListener(function(sender, type)
if type == ccui.TouchEventType.began then
self.beginPos = gFun.scene.getMousePos();
self.effect = true;
if imageButton:AlphaTouchCheck(gFun.scene.getMousePos()) then –传入鼠标点击位置
imageButton:setScale(0.95);
end
elseif type == ccui.TouchEventType.moved then
if getDistance(self.beginPos, gFun.scene.getMousePos()) > 20 then –判断是不是有滑动
self.effect = false;
end
elseif type == ccui.TouchEventType.canceled then

imageButton:setScale(1);
elseif type == ccui.TouchEventType.ended then
if not self.effect then return end

imageButton:setScale(1);
if imageButton:AlphaTouchCheck(gFun.scene.getMousePos()) then –传入鼠标点击位置
–do something;
end
end
end
)

[/lua]