循环双端队列
令front指向队头,rear指向队尾,那么有
- 判空:
front == rear
- 判满:
(rear + 1) % size == front
因为这个判满的条件,长度为10的数组,我们最多利用到9个空间,所以要开多一个空间。
class MyCircularDeque
{
public:
int size;
int front, rear;
int q[1005];
MyCircularDeque(int k)
{
size = k + 1;
rear = 0;
front = 0;
}
bool insertFront(int value)
{
if (isFull())
return false;
front = (front - 1 + size) % size;
q[front] = value;
return true;
}
bool insertLast(int value)
{
if (isFull())
return false;
q[rear] = value;
rear = (rear + 1) % size;
return true;
}
bool deleteFront()
{
if (isEmpty())
return false;
front = (front + 1) % size;
return true;
}
bool deleteLast()
{
if (isEmpty())
return false;
rear = (rear - 1 + size) % size;
return true;
}
int getFront()
{
if (isEmpty())
return -1;
return q[front];
}
int getRear()
{
if (isEmpty())
return -1;
return q[(rear - 1 + size) % size];
}
bool isEmpty()
{
return front == rear;
}
bool isFull()
{
return (rear + 1) % size == front;
}
};