上次编辑到这里，代码来自缓存 点击恢复默认模板
class FrontMiddleBackQueue {
public:
FrontMiddleBackQueue() {
}
void pushFront(int val) {
}
void pushMiddle(int val) {
}
void pushBack(int val) {
}
int popFront() {
}
int popMiddle() {
}
int popBack() {
}
};
/**
* 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();
*/
java 解法, 执行用时: 6 ms, 内存消耗: 43.3 MB, 提交时间: 2023-11-28 07:02:41
class FrontMiddleBackQueue {
Deque<Integer> left;
Deque<Integer> right;
public FrontMiddleBackQueue() {
left = new ArrayDeque<>();
right = new ArrayDeque<>();
}
public void pushFront(int val) {
left.addFirst(val);
reBalance();
}
public void pushMiddle(int val) {
if (left.size() == right.size()) {
right.addFirst(val);
} else {
left.addLast(val);
}
}
public void pushBack(int val) {
right.addLast(val);
reBalance();
}
public int popFront() {
Integer integer = left.pollFirst();
if (integer == null) {
integer = right.pollFirst();
return integer == null ? -1 : integer;
} else {
reBalance();
return integer;
}
}
public int popMiddle() {
if (left.size() == right.size()) {
Integer integer = left.pollLast();
return integer == null ? -1 : integer;
} else {
return right.pollFirst();
}
}
public int popBack() {
Integer integer = right.pollLast();
reBalance();
return integer == null ? -1 : integer;
}
public void reBalance() {
if (left.size() > right.size()) {
right.addFirst(left.pollLast());
} else if (right.size() == left.size() + 2) {
left.addLast(right.pollFirst());
}
}
}
/**
* 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();
*/
golang 解法, 执行用时: 20 ms, 内存消耗: 7.4 MB, 提交时间: 2023-11-28 07:01:18
type FrontMiddleBackQueue struct{}
var a []int
func Constructor() (_ FrontMiddleBackQueue) {
a = nil
return
}
func (FrontMiddleBackQueue) PushFront(v int) {
a = append([]int{v}, a...)
}
func (FrontMiddleBackQueue) PushMiddle(v int) {
p := len(a) / 2
a = append(a[:p], append([]int{v}, a[p:]...)...)
}
func (FrontMiddleBackQueue) PushBack(v int) {
a = append(a, v)
}
func (FrontMiddleBackQueue) PopFront() (ans int) {
if len(a) == 0 {
return -1
}
ans = a[0]
a = a[1:]
return
}
func (FrontMiddleBackQueue) PopMiddle() (ans int) {
if len(a) == 0 {
return -1
}
p := (len(a) - 1) / 2
ans = a[p]
a = append(a[:p], a[p+1:]...)
return
}
func (FrontMiddleBackQueue) PopBack() (ans int) {
if len(a) == 0 {
return -1
}
ans = a[len(a)-1]
a = a[:len(a)-1]
return
}
/**
* Your FrontMiddleBackQueue object will be instantiated and called as such:
* obj := Constructor();
* obj.PushFront(val);
* obj.PushMiddle(val);
* obj.PushBack(val);
* param_4 := obj.PopFront();
* param_5 := obj.PopMiddle();
* param_6 := obj.PopBack();
*/
python3 解法, 执行用时: 84 ms, 内存消耗: 15.8 MB, 提交时间: 2023-01-11 09:58:42
class LinkedListNode:
def __init__(self, val: int):
self.val = val
self.prev = None
self.succ = None
class LinkedList:
def __init__(self):
self.head = LinkedListNode(42)
self.tail = LinkedListNode(42)
self.head.succ = self.tail
self.tail.prev = self.head
self.size = 2
def __str__(self):
ret = list()
cur = self.head
while cur:
ret.append(cur.val)
cur = cur.succ
return str(ret)
def insert(self, it: LinkedListNode, val: int):
self.size += 1
node = LinkedListNode(val)
it.prev.succ = node
node.prev = it.prev
it.prev = node
node.succ = it
def erase(self, it: LinkedListNode) -> LinkedListNode:
self.size -= 1
ret = it.succ
it.prev.succ = it.succ
it.succ.prev = it.prev
return ret
def advance(self, it: LinkedListNode, dt: int) -> LinkedListNode:
if dt > 0:
for _ in range(dt):
it = it.succ
elif dt < 0:
for _ in range(-dt):
it = it.prev
return it
class FrontMiddleBackQueue:
def __init__(self):
self.q = LinkedList()
self.it = self.q.head
self.ptrpos = 0
def pushFront(self, val: int) -> None:
# 指针不指向哑头节点
if self.ptrpos != 0:
self.ptrpos += 1
self.q.insert(self.q.head.succ, val)
def pushMiddle(self, val: int) -> None:
pos = self.q.size // 2
# 均摊 O(1)
self.it = self.q.advance(self.it, pos - self.ptrpos)
self.q.insert(self.it, val)
self.ptrpos = pos + 1
def pushBack(self, val: int) -> None:
# 指针指向哑尾节点
if self.ptrpos == self.q.size - 1:
self.ptrpos += 1
self.q.insert(self.q.tail, val)
def popFront(self) -> int:
if self.q.size == 2:
return -1
ret = self.q.head.succ.val
if self.ptrpos == 1:
self.it = self.q.erase(self.it)
else:
self.q.erase(self.q.head.succ)
# 指针不指向哑头节点
if self.ptrpos != 0:
self.ptrpos -= 1
return ret
def popMiddle(self) -> int:
if self.q.size == 2:
return -1
pos = (self.q.size - 1) // 2
# 均摊 O(1)
self.it = self.q.advance(self.it, pos - self.ptrpos)
ret = self.it.val
self.it = self.q.erase(self.it)
self.ptrpos = pos
return ret
def popBack(self) -> int:
if self.q.size == 2:
return -1
ret = self.q.tail.prev.val
if self.ptrpos == self.q.size - 2:
self.it = self.q.erase(self.it)
else:
self.q.erase(self.q.tail.prev)
# 指针指向哑尾节点
if self.ptrpos == self.q.size:
self.ptrpos -= 1
return ret
# Your FrontMiddleBackQueue object will be instantiated and called as such:
# obj = FrontMiddleBackQueue()
# obj.pushFront(val)
# obj.pushMiddle(val)
# obj.pushBack(val)
# param_4 = obj.popFront()
# param_5 = obj.popMiddle()
# param_6 = obj.popBack()
cpp 解法, 执行用时: 28 ms, 内存消耗: 19.8 MB, 提交时间: 2023-01-11 09:57:39
class FrontMiddleBackQueue {
private:
list<int> q;
// 指向正中间的指针
list<int>::iterator it;
// 指针目前位于第几个元素
int ptrpos;
public:
FrontMiddleBackQueue(): q{initializer_list<int>{42, 42}}, it{q.begin()}, ptrpos{0} {}
void pushFront(int val) {
// 指针不指向哑头节点
if (ptrpos != 0) {
++ptrpos;
}
q.insert(next(q.begin()), val);
}
void pushMiddle(int val) {
int pos = q.size() / 2;
// 均摊 O(1)
advance(it, pos - ptrpos);
q.insert(it, val);
ptrpos = pos + 1;
}
void pushBack(int val) {
// 指针指向哑尾节点
if (ptrpos == q.size() - 1) {
++ptrpos;
}
q.insert(prev(q.end()), val);
}
int popFront() {
if (q.size() == 2) {
return -1;
}
int ret = *next(q.begin());
if (ptrpos == 1) {
it = q.erase(it);
}
else {
q.erase(next(q.begin()));
// 指针不指向哑头节点
if (ptrpos != 0) {
--ptrpos;
}
}
return ret;
}
int popMiddle() {
if (q.size() == 2) {
return -1;
}
int pos = (q.size() - 1) / 2;
// 均摊 O(1)
advance(it, pos - ptrpos);
int ret = *it;
it = q.erase(it);
ptrpos = pos;
return ret;
}
int popBack() {
if (q.size() == 2) {
return -1;
}
int ret = *prev(prev(q.end()));
if (ptrpos == q.size() - 2) {
it = q.erase(it);
}
else {
q.erase(prev(prev(q.end())));
// 指针指向哑尾节点
if (ptrpos == q.size()) {
--ptrpos;
}
}
return ret;
}
};
/**
* 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();
*/
cpp 解法, 执行用时: 36 ms, 内存消耗: 19.5 MB, 提交时间: 2023-01-11 09:57:00
class FrontMiddleBackQueue {
private:
vector<int> q;
public:
FrontMiddleBackQueue() {}
void pushFront(int val) {
q.insert(q.begin(), val);
}
void pushMiddle(int val) {
// 注意正确计算位置
int pos = q.size() / 2;
q.insert(q.begin() + pos, val);
}
void pushBack(int val) {
q.push_back(val);
}
int popFront() {
if (q.empty()) {
return -1;
}
int ret = q[0];
q.erase(q.begin());
return ret;
}
int popMiddle() {
if (q.empty()) {
return -1;
}
// 注意正确计算位置
int pos = (q.size() - 1) / 2;
int ret = q[pos];
q.erase(q.begin() + pos);
return ret;
}
int popBack() {
if (q.empty()) {
return -1;
}
int ret = q.back();
q.pop_back();
return ret;
}
};
/**
* 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();
*/
python3 解法, 执行用时: 76 ms, 内存消耗: 15.6 MB, 提交时间: 2023-01-11 09:56:23
class FrontMiddleBackQueue:
def __init__(self):
self.q = list()
def pushFront(self, val: int) -> None:
self.q[0:0] = [val]
def pushMiddle(self, val: int) -> None:
# 注意正确计算位置
pos = len(self.q) // 2
self.q[pos:pos] = [val]
def pushBack(self, val: int) -> None:
self.q.append(val)
def popFront(self) -> int:
if not self.q:
return -1
ret = self.q[0]
self.q[0:1] = []
return ret
def popMiddle(self) -> int:
if not self.q:
return -1
# 注意正确计算位置
pos = (len(self.q) - 1) // 2
ret = self.q[pos]
self.q[pos:pos+1] = []
return ret
def popBack(self) -> int:
if not self.q:
return -1
return self.q.pop()
# Your FrontMiddleBackQueue object will be instantiated and called as such:
# obj = FrontMiddleBackQueue()
# obj.pushFront(val)
# obj.pushMiddle(val)
# obj.pushBack(val)
# param_4 = obj.popFront()
# param_5 = obj.popMiddle()
# param_6 = obj.popBack()