Medium

题目描述

设计一个支持在前端、中间和后端进行推入和弹出操作的队列。

实现 FrontMiddleBackQueue 类：

  • FrontMiddleBackQueue() 初始化队列。
  • 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次，我们可以考虑两种解法：

解法一：双端队列（推荐） 使用两个双端队列 left 和 right 来维护队列的前半部分和后半部分。通过维护两个队列的平衡，使得 right 的长度始终等于 left 的长度或者比 left 多1个元素。这样中间位置就始终在 right 的前端。

平衡规则：

  • 当 left.size() > right.size() 时，将 left 的最后一个元素移到 right 的前端
  • 当 right.size() > left.size() + 1 时，将 right 的第一个元素移到 left 的后端

解法二：简单数组 使用一个动态数组直接存储所有元素，通过计算索引来确定中间位置。虽然插入和删除的时间复杂度较高，但由于数据规模小，也是可行的。

两种解法中，双端队列解法更优雅且具有更好的时间复杂度，因此推荐使用。

代码实现

class FrontMiddleBackQueue {
private:
    deque<int> left, right;
    
    void balance() {
        if (left.size() > right.size()) {
            right.push_front(left.back());
            left.pop_back();
        } else if (right.size() > left.size() + 1) {
            left.push_back(right.front());
            right.pop_front();
        }
    }
    
public:
    FrontMiddleBackQueue() {
        
    }
    
    void pushFront(int val) {
        left.push_front(val);
        balance();
    }
    
    void pushMiddle(int val) {
        if (left.size() == right.size()) {
            right.push_front(val);
        } else {
            left.push_back(right.front());
            right.pop_front();
            right.push_front(val);
        }
    }
    
    void pushBack(int val) {
        right.push_back(val);
        balance();
    }
    
    int popFront() {
        if (left.empty() && right.empty()) return -1;
        int val;
        if (left.empty()) {
            val = right.front();
            right.pop_front();
        } else {
            val = left.front();
            left.pop_front();
            balance();
        }
        return val;
    }
    
    int popMiddle() {
        if (left.empty() && right.empty()) return -1;
        int val = right.front();
        right.pop_front();
        balance();
        return val;
    }
    
    int popBack() {
        if (left.empty() && right.empty()) return -1;
        int val = right.back();
        right.pop_back();
        balance();
        return val;
    }
};

from collections import deque

class FrontMiddleBackQueue:

    def __init__(self):
        self.left = deque()
        self.right = deque()
    
    def _balance(self):
        if len(self.left) > len(self.right):
            self.right.appendleft(self.left.pop())
        elif len(self.right) > len(self.left) + 1:
            self.left.append(self.right.popleft())

    def pushFront(self, val: int) -> None:
        self.left.appendleft(val)
        self._balance()

    def pushMiddle(self, val: int) -> None:
        if len(self.left) == len(self.right):
            self.right.appendleft(val)
        else:
            self.left.append(self.right.popleft())
            self.right.appendleft(val)

    def pushBack(self, val: int) -> None:
        self.right.append(val)
        self._balance()

    def popFront(self) -> int:
        if not self.left and not self.right:
            return -1
        if not self.left:
            return self.right.popleft()
        val = self.left.popleft()
        self._balance()
        return val

    def popMiddle(self) -> int:
        if not self.left and not self.right:
            return -1
        val = self.right.popleft()
        self._balance()
        return val

    def popBack(self) -> int:
        if not self.left and not self.right:
            return -1
        val = self.right.pop()
        self._balance()
        return val

public class FrontMiddleBackQueue {
    private LinkedList<int> left;
    private LinkedList<int> right;

    public FrontMiddleBackQueue() {
        left = new LinkedList<int>();
        right = new LinkedList<int>();
    }
    
    private void Balance() {
        if (left.Count > right.Count) {
            right.AddFirst(left.Last.Value);
            left.RemoveLast();
        } else if (right.Count > left.Count + 1) {
            left.AddLast(right.First.Value);
            right.RemoveFirst();
        }
    }
    
    public void PushFront(int val) {
        left.AddFirst(val);
        Balance();
    }
    
    public void PushMiddle(int val) {
        if (left.Count == right.Count) {
            right.AddFirst(val);
        } else {
            left.AddLast(right.First.Value);
            right.RemoveFirst();
            right.AddFirst(val);
        }
    }
    
    public void PushBack(int val) {
        right.AddLast(val);
        Balance();
    }
    
    public int PopFront() {
        if (left.Count == 0 && right.Count == 0) return -1;
        int val;
        if (left.Count == 0) {
            val = right.First.Value;
            right.RemoveFirst();
        } else {
            val = left.First.Value;
            left.RemoveFirst();
            Balance();
        }
        return val;
    }
    
    public int PopMiddle() {
        if (left.Count == 0 && right.Count == 0) return -1;
        int val = right.First.Value;
        right.RemoveFirst();
        Balance();
        return val;
    }
    
    public int PopBack() {
        if (left.Count == 0 && right.Count == 0) return -1;
        int val = right.Last.Value;
        right.RemoveLast();
        Balance();
        return val;
    }
}

var FrontMiddleBackQueue = function() {
    this.queue = [];
};

FrontMiddleBackQueue.prototype.pushFront = function(val) {
    this.queue.unshift(val);
};

FrontMiddleBackQueue.prototype.pushMiddle = function(val) {
    const mid = Math.floor(this.queue.length / 2);
    this.queue.splice(mid, 0, val);
};

FrontMiddleBackQueue.prototype.pushBack = function(val) {
    this.queue.push(val);
};

FrontMiddleBackQueue.prototype.popFront = function() {
    return this.queue.length === 0 ? -1 : this.queue.shift();
};

FrontMiddleBackQueue.prototype.popMiddle = function() {
    if (this.queue.length === 0) return -1;
    const mid = Math.floor((this.queue.length - 1) / 2);
    return this.queue.splice(mid, 1)[0];
};

FrontMiddleBackQueue.prototype.popBack = function() {
    return this.queue.length === 0 ? -1 : this.queue.pop();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
pushFrontO(1)O(1)
pushMiddleO(1)O(1)
pushBackO(1)O(1)
popFrontO(1)O(1)
popMiddleO(1)O(1)
popBackO(1)O(1)
总空间复杂度-O(n)

其中 n 是队列中元素的总数。双端队列解法的所有操作都能在常数时间内完成。

相关题目