the third one in Biweekly Contest 40.
Difficulty : Medium
Related Topics : Linked List、Design、Dequeue
Design a queue that supports
push
andpop
operations in the front, middle, and back.Implement the
FrontMiddleBack
class:
FrontMiddleBack()
Initializes the queue.void pushFront(int val)
Addsval
to the front of the queue.void pushMiddle(int val)
Addsval
to the middle of the queue.void pushBack(int val)
Addsval
to the back of the queue.int popFront()
Removes the front element of the queue and returns it. If the queue is empty, return-1
.int popMiddle()
Removes the middle element of the queue and returns it. If the queue is empty, return-1
.int popBack()
Removes the back element of the queue and returns it. If the queue is empty, return-1
.Notice that when there are two middle position choices, the operation is performed on the frontmost middle position choice. For example:
- Pushing
6
into the middle of[1, 2, 3, 4, 5]
results in[1, 2, 6, 3, 4, 5]
.- Popping the middle from
[1, 2, 3, 4, 5, 6]
returns3
and results in[1, 2, 4, 5, 6]
.Input: ["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"] [[], [1], [2], [3], [4], [], [], [], [], []] Output: [null, null, null, null, null, 1, 3, 4, 2, -1] Explanation: 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(); // return 1 -> [4, 3, 2] q.popMiddle(); // return 3 -> [4, 2] q.popMiddle(); // return 4 -> [2] q.popBack(); // return 2 -> [] q.popFront(); // return -1 -> [] (The queue is empty)
1 <= val <= 10^9
- At most
1000
calls will be made topushFront
,pushMiddle
,pushBack
,popFront
,popMiddle
, andpopBack
.
- mine
- Java
Runtime: 7 ms, faster than 100.00%, Memory Usage: 39.5 MB, less than 100.00% of Java online submissions
class FrontMiddleBackQueue { List<Integer> list; public FrontMiddleBackQueue() { list = new ArrayList<>(); } public void pushFront(int val) { list.add(0, val); } public void pushMiddle(int val) { int size = list.size(); list.add(size/ 2 , val); } public void pushBack(int val) { list.add(val); } public int popFront() { if(list.size() == 0) return -1; return list.remove(0); } public int popMiddle() { int size = list.size(); if(size == 0) return -1; int index = 0; if(size % 2 == 0 && size > 0){ index = (size - 1) / 2; }else{ index = size / 2; } return list.remove(index); } public int popBack() { if(list.size() == 0) return -1; return list.remove(list.size() - 1); } }
- Java
- the most votes
Runtime: 7 ms, faster than 100.00%, Memory Usage: 39.5 MB, less than 100.00% of Java online submissions
class FrontMiddleBackQueue { LinkedList<Integer> left, right; int size; public FrontMiddleBackQueue() { left = new LinkedList<>(); right = new LinkedList<>(); size = 0; } public void pushFront(int val) { left.addFirst(val); if (left.size() > right.size()) { right.addFirst(left.removeLast()); } size++; } public void pushMiddle(int val) { if (left.size() == right.size()) { right.addFirst(val); } else { left.addLast(val); } size++; } public void pushBack(int val) { if (left.size() < right.size()) { left.addLast(right.removeFirst()); } right.addLast(val); size++; } public int popFront() { if (size == 0) { return -1; } if (left.size() < right.size()) { left.addLast(right.removeFirst()); } int val = left.removeFirst(); size--; return val; } public int popMiddle() { if (size == 0) { return -1; } int val; if (left.size() == right.size()) { val = left.removeLast(); } else { val = right.removeFirst(); } size--; return val; } public int popBack() { if (size == 0) { return -1; } int val = right.removeLast(); if (left.size() > right.size()) { right.addFirst(left.removeLast()); } size--; return val; } }