$$\huge\color{red}{设计循环双端队列\space|\space STL模拟}$$
题意不再赘述,本题已经说明得很清楚了。
思路
我们发现所有的函数都需要一个公用的“队列”,如果我们直接用$STL$的队列会比较吃亏,所以我们不妨用另一个十分好用的$STL$:vector
。
vector
相信学过图论的同学都非常熟悉,这个东西非常的好用。
其实这道题目非常简单,开一个vector
然后模拟加入、删除的操作即可。
代码
class MyCircularDeque {
public:
vector<int> q;
int hh=0,tt=0;
MyCircularDeque(int k) {
q.resize(k+1);
}
int pos(int x){
return (x+q.size())%q.size();
}
bool insertFront(int value){
if (isFull())
return false;
hh=pos(hh-1);
q[hh]=value;
return true;
}
bool insertLast(int value){
if (isFull())
return false;
q[tt]=value;
tt=pos(tt+1);
return true;
}
bool deleteFront(){
if (isEmpty())
return false;
hh=pos(hh+1);
return true;
}
bool deleteLast(){
if (isEmpty())
return false;
tt=pos(tt-1);
return true;
}
int getFront(){
if (isEmpty())
return -1;
return q[hh];
}
int getRear(){
if (isEmpty())
return -1;
return q[pos(tt-1)];
}
bool isEmpty(){
return hh==tt;
}
bool isFull(){
return tt==pos(hh-1);
}
};
作者:陆修远
链接:https://www.acwing.com/activity/content/code/content/4096814/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。