42-设计前中后队列

自己的做法

算法思想

使用链表来设计队列，两个指针front和tail分别指向队列头部和尾部，size表示队列长度。

并且front指向的也是链表的头节点。

初始队列为空时，front和tail都指向同一个节点，该节点不是队列元素。

则各操作实现：

添加到队列前面：直接添加即可，特殊情况：当队列为空时，设置tail指向新添加的节点。

添加到队列尾部：直接添加，然后tail向后走一步。

添加到队列中间：需要找到待添加位置的前一个节点，从front节点向后走 (size) / 2 步，即可找到该节点，添加即 可。同样注意特殊情况：即队列为空时，修改tail指针。

从队头弹出：直接弹出，同样注意特殊情况：当弹出后队列为空时，修改tail指针指向front

从队尾弹出：从front开始遍历，直到找到tail的前一个节点，弹出即可。

从队中间弹出：要找到待弹出节点的前一个节点，从front节点开始走 (size - 1) / 2 步，就是该节点。然后弹出。

注意弹出后队列为空的情况。

算法实现

class FrontMiddleBackQueue {
private:
    ListNode * tail = nullptr;
    ListNode * front = nullptr;
    int size;

    ListNode * getInsertNode() {
        int step = size / 2;
        ListNode * node = front;
        for(int i = 0; i < step; i++) {
            node = node->next;
        }
        return node;
    }

    ListNode * getDeleteNode() {
        int step = (size - 1) / 2;
        ListNode * node = front;
        for(int i = 0; i < step; i++) {
            node = node->next;
        }
        return node;
    }

public:
    FrontMiddleBackQueue() {
        ListNode * node = new ListNode();
        tail = node;
        front = node;
        size = 0;
    }

    void pushFront(int val) {
        ListNode * node = new ListNode(val);
        node->next = front->next;
        front->next = node;
        size++;
        if(front == tail) {
            tail = node;
        }

    }

    void pushMiddle(int val) {

        ListNode * node = new ListNode(val);
        ListNode * pre = getInsertNode();
        node->next = pre->next;
        pre->next = node;
        if(front == tail) {
            tail = node;
        }
        size++;
    }

    void pushBack(int val) {
        ListNode * node = new ListNode(val);
        tail->next = node;
        tail = node;
        size++;
    }

    int popFront() {
        if(front == tail) {
            return -1;
        }
        ListNode * node = front->next;
        front->next = node->next;
        size--;
        if(size == 0) {
            tail = front;
        }
        return node->val;
    }

    int popMiddle() {
        if(front == tail) {
            return -1;
        }
        ListNode * pre = getDeleteNode();
        ListNode * node = pre->next;
        pre->next = node->next;
        size--;
        if(size == 0) {
            tail = front;
        }
        return node->val;
    }

    int popBack() {
        if(front == tail) {
            return -1;
        }
        ListNode * pre = front;
        while (pre->next != tail) {
            pre = pre->next;
        }
        tail = pre;
        pre = pre->next;
        tail->next = nullptr;
        size--;
        return pre->val;
    }
};

性能分析

时间复杂度：

​ 队头添加、队尾添加、队头删除都是$O(1)$。

​ 队中添加和删除、队尾删除时$O(n)$。

空间复杂度：都为$O(1)$。