641. Design Circular Deque
1,题目要求
Design your implementation of the circular double-ended queue (deque).
Your implementation should support following operations:
MyCircularDeque(k): Constructor, set the size of the deque to be k.
insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.
insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.
deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.
deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.
getFront(): Gets the front item from the Deque. If the deque is empty, return -1.
getRear(): Gets the last item from Deque. If the deque is empty, return -1.
isEmpty(): Checks whether Deque is empty or not.
isFull(): Checks whether Deque is full or not.
实现一个双向循环队列。
2,题目思路
很麻烦,首先,STL中是有双向队列deque的,但是如果直接用肯定是不行的了,因此需要定义额外的容器来实现这个循环的双向队列。
因此,对于这道题,定义了一个vector,来作为存储这个循环双向队列的容器。其次,对于循环队列,在添加元素时所用的则是mod,来进行循环的实现。
另外,循环队列的实现,有两种方式,一种是k个元素,而另外一种则是额外开辟新的空间,即k+1个空间存储k个元素,这个额外的空间作为队列为空还是为满的一个判断条件。
3,程序源码
class MyCircularDeque {
public:
/** Initialize your data structure here. Set the size of the deque to be k. */
MyCircularDeque(int k) {
array.resize(k+1, 0);
size = k + 1;
front = 0, back = 1;
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
bool insertFront(int value) {
if(isFull())
return false;
array[front] = value;
front = (front + size -1) % size;
return true;
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
bool insertLast(int value) {
if(isFull())
return false;
array[back] = value;
back = (back + 1) % size;
return true;
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
bool deleteFront() {
if(isEmpty())
return false;
front = (front + 1) % size;
return true;
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
bool deleteLast() {
if(isEmpty())
return false;
back = (back + size - 1) % size;
return true;
}
/** Get the front item from the deque. */
int getFront() {
if(isEmpty())
return -1;
return array[(front + 1) % size];
}
/** Get the last item from the deque. */
int getRear() {
if(isEmpty())
return -1;
return array[(back + size -1) % size];
}
/** Checks whether the circular deque is empty or not. */
bool isEmpty() {
return (front+1)%size == back;
}
/** Checks whether the circular deque is full or not. */
bool isFull() {
return front == back;
}
private:
vector<int> array;
int front, back;
int size;
};
上一篇: Leecode 641.设计循环双端队列