关于一个循环行列的面试题

关于一个循环队列的面试题

今天去某互联网公司面试，也许由于状态不好，反正当时被一个循环队列卡住了，可惜刚走出公司大门不久我就想明白了，这里把具体代码贴出来，哎，有时候，你就该出去走走，脱离那个让你一直绕不出来的环境，因为一直陷在里面可能已经大的思路方向就错了，就像我当时在一个错误的思路上纠结不出来结果一样，come out and another method will jump up from your mind;

就是数组实现一个循环队列

为了尽快测试自己的实现思路，所以代码风格以越简单为好，直接在类里面写了 因为我想立刻赶快证明我的思路是正确的 立刻！！

class CircleQue{
public:
int push(char* p, int n)//把p[0]~p[n-1]压入队尾 返回实际压入的个数 ，能压入多少个就压入多少个
{
if(tail - head == size)
return 0;
if(tail + n - head > size)//没法完全装下
{
n = size + head - tail;
tail += n;
}else
{
tail += n;
}


if((tail - n) % size < tail % size)//没有跨过边界 可以直接拷贝数据
{
memcpy(buf + (tail - n) % size, p, n);
}else//跨过边界了 需要两次拷贝
{
memcpy(buf + (tail - n) % size, p, size - (tail - n) % size);
if(tail % size != 0)
memcpy(buf, p, tail % size);
}
if(head > size && tail > size)
{
head -= size;
tail -= size;
}
return n;
}


int pop(char*p, int n)//从队列头部返回数据到p[0]-p[n]的数组中去，能去多少个就取出多少个，返回最终能够取出的个数
{
if(tail - head == 0)
return 0;
if(head + n > tail)//不够弹的
{
n = tail - head;
head = tail;
}else
{
head += n;
}


if((head - n) % size < head % size)//没有跨过边界 可以直接拷贝数据
{
memcpy(p, buf + (head - n) % size, n);
memset(buf + (head - n) % size, 0, n);
}else//跨过边界了 需要两次拷贝
{
memcpy(p, buf + (head - n) % size, size - (head - n) % size);
memset(buf + (head - n) % size, 0, size - (head - n) % size);//只是为了调试时方便看到数据变化，与算法本身无关
if(head % size != 0)
{
memcpy(p, buf, head % size);
memset(buf, 0, head % size);
}
}
if(head > size && tail > size)
{
head -= size;
tail -= size;
}
return n;
}
CircleQue()
{
head = 0;
tail = 0;
size = 5;
buf = new char[size];
memset(buf, 0, size);
}
private:
int size;
char* buf;
int head;
int tail;
};

//测试代码 可以单步调试看 head tail 以及buf内容变化

int main()

{

CircleQue q;
char buf[10] = {0};
int n = q.push("123", 3);
n = q.pop(buf, 1);
n = q.push("45", 2);
n = q.pop(buf, 3);
n = q.push("678", 3);
n = q.pop(buf, 2);
n = q.pop(buf, 3);

       return 0;

}