题目描述
请你设计一个队列,支持在前,中,后三个位置的 push
和 pop
操作。
请你完成FrontMiddleBack
类:
FrontMiddleBack()
初始化队列。
void pushFront(int val)
将val
添加到队列的 最前面
。
void pushMiddle(int val)
将val
添加到队列的 正中间
。
void pushBack(int val)
将val
添加到队里的 最后面
。
int popFront()
将 最前面 的元素从队列中删除并返回值,如果删除之前队列为空,那么返回 -1
。
int popMiddle()
将 正中间
的元素从队列中删除并返回值,如果删除之前队列为空,那么返回 -1
。
int popBack()
将 最后面
的元素从队列中删除并返回值,如果删除之前队列为空,那么返回 -1
。
请注意当有两个
中间位置的时候,选择靠前面的位置进行操作。比方说:
将 6
添加到[1, 2, 3, 4, 5]
的中间位置,结果数组为[1, 2,
6
, 3, 4, 5]
。
从[1, 2, 3, 4, 5, 6]
的中间位置弹出元素,返回3
,数组变为[1, 2, 4, 5, 6]
。
样例
示例1
输入:
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
输出:
[null, null, null, null, null, 1, 3, 4, 2, -1]
解释:
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1); // [1]
q.pushBack(2); // [1, 2]
q.pushMiddle(3); // [1, 3, 2]
q.pushMiddle(4); // [1, 4, 3, 2]
q.popFront(); // 返回 1 -> [4, 3, 2]
q.popMiddle(); // 返回 3 -> [4, 2]
q.popMiddle(); // 返回 4 -> [2]
q.popBack(); // 返回 2 -> []
q.popFront(); // 返回 -1 -> [] (队列为空)
提示
1 <= val <= 10^9
- 最多调用
1000
次pushFront
,pushMiddle
,pushBack
,popFront
,popMiddle
和popBack
。
注意
- 由于此题的数据范围仅有
1000
次调用, 因此我这里给出了$O(n^2)$的代码很短能在考试快速AC的写法。 - 如果读者需要了解效率更优的
双向链表
和/或两个双端队列
的,$O(n)$解法,可以参照 @WZC的题解
算法1
(暴力模拟) $O(n^2)$
- 由于此题的数据范围仅有
1000
次调用, 因此我们考虑最简单的暴力模拟即可 - 使用一个
vector
存储当前数据结构中的所有数,那么我们可以利用vector
提供的insert
,push_back
,erase
等操作实现题目要求的API Java
中的List
接口亦有add(E)
,add(index, E)
,remove(index)
等对应的API- 对于找中点操作而言,由于题目要求当有两个正中间位置的数的时候,取前面一个,因此对于
popMiddle
我们的中点坐标为(v.size() - 1) / 2
, 而对于pushMiddle
而言,我们的目标位置应该在v.size() / 2
。
时间复杂度
n
次操作,每次最坏需要将整个数组中的所有元素挪一个位置- 故总的时间复杂度为$O(n^2)$
参考文献
C++ 代码
class FrontMiddleBackQueue {
public:
vector<int> v;
FrontMiddleBackQueue() {
}
void pushFront(int val) {
v.insert(v.begin(), val);
}
void pushMiddle(int val) {
int idx = (v.size()) / 2;
v.insert(v.begin() + idx, val);
}
void pushBack(int val) {
v.push_back(val);
}
int popFront() {
if(v.size() == 0) return -1;
int t = v.front();
v.erase(v.begin());
return t;
}
int popMiddle() {
if(v.size() == 0) return -1;
int t = v[(v.size() - 1) / 2];
v.erase(v.begin() + (v.size() - 1) / 2);
return t;
}
int popBack() {
if(v.size() == 0) return -1;
int t = v.back();
v.pop_back();
return t;
}
};
/**
* Your FrontMiddleBackQueue object will be instantiated and called as such:
* FrontMiddleBackQueue* obj = new FrontMiddleBackQueue();
* obj->pushFront(val);
* obj->pushMiddle(val);
* obj->pushBack(val);
* int param_4 = obj->popFront();
* int param_5 = obj->popMiddle();
* int param_6 = obj->popBack();
*/