LeetCode 641 设计循环双端队列
所需变量:
hh
:队列头所在元素位置
tt
:队列尾所在元素的下一个位置(在尾部新加数据应该所处的位置)
sz
:队列中元素的个数
n
:队列最大长度
deque
:长度为n的数组
函数实现方法:
MyCircularDeque(int k)
:
初始化参数:hh=0,tt=0,sz=0,n = k, deque=vector[HTML_REMOVED](n)boolean insertFront()
:- 如果队列满了,返回false
- 如果队列没满,先将头向前移动一位(hh = hh - 1 == -1 ? n - 1 : hh - 1),然后将value放入deque[hh],sz++,返回true
boolean insertLast()
:- 如果队列满了,返回false
- 如果队列没满,将value放入deque[tt],然后tt = tt + 1 == n ? 0 : tt + 1,sz++,返回true
boolean deleteFront()
:- 如果队列为空,返回false
- 如果队列不空,hh = hh + 1 == n ? 0, hh + 1,sz–,返回true
boolean deleteLast()
:- 如果队列为空,返回false
- 如果队列不空,tt = tt - 1 == -1 ? n - 1 : tt - 1,sz–,返回true
int getFront()
:返回 sz == 0 ? -1 : deque[hh]int getRear()
:返回 sz == 0 ? -1 : deque[(tt - 1 + n) % n]boolean isEmpty()
:返回 sz == 0boolean isFull()
:返回 sz == n
代码
class MyCircularDeque {
public:
int hh, tt, sz, n;
vector<int> deque;
MyCircularDeque(int k) {
deque.resize(k);
n = k;
hh = tt = sz = 0;
}
bool insertFront(int value) {
if(sz == n) return false;
hh = hh - 1 == -1 ? n - 1 : hh - 1;
deque[hh] = value;
sz ++;
return true;
}
bool insertLast(int value) {
if(sz == n) return false;
deque[tt ++] = value;
tt = tt == n ? 0 : tt;
sz ++;
return true;
}
bool deleteFront() {
if(sz == 0) return false;
sz --;
hh = hh + 1 == n ? 0 : hh + 1;
return true;
}
bool deleteLast() {
if(sz == 0) return false;
sz --;
tt = tt - 1 == -1 ? n - 1 : tt - 1;
return true;
}
int getFront() {
return sz == 0 ? -1 : deque[hh];
}
int getRear() {
return sz == 0 ? -1 : deque[(tt - 1 + n) % n];
}
bool isEmpty() {
return sz == 0;
}
bool isFull() {
return sz == n;
}
};
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque* obj = new MyCircularDeque(k);
* bool param_1 = obj->insertFront(value);
* bool param_2 = obj->insertLast(value);
* bool param_3 = obj->deleteFront();
* bool param_4 = obj->deleteLast();
* int param_5 = obj->getFront();
* int param_6 = obj->getRear();
* bool param_7 = obj->isEmpty();
* bool param_8 = obj->isFull();
*/