1670. Design Front Middle Back Queue #

Problem #

Design a queue that supports push and pop operations in the front, middle, and back.

Implement the FrontMiddleBack class:

• FrontMiddleBack() Initializes the queue.
• void pushFront(int val) Adds val to the front of the queue.
• void pushMiddle(int val) Adds val to the middle of the queue.
• void pushBack(int val) Adds val 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] returns 3 and results in [1, 2, 4, 5, 6].

Example 1:

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)

Constraints:

• 1 <= val <= 109
• At most 1000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.

Problem Summary #

Please design a queue that supports push and pop operations at the front, middle, and back positions.

Please implement the FrontMiddleBack class:

• FrontMiddleBack() initializes the queue.
• void pushFront(int val) adds val to the very front of the queue.
• void pushMiddle(int val) adds val to the exact middle of the queue.
• void pushBack(int val) adds val to the very back of the queue.
• int popFront() removes the frontmost element from the queue and returns its value. If the queue is empty before deletion, return -1.
• int popMiddle() removes the middle element from the queue and returns its value. If the queue is empty before deletion, return -1.
• int popBack() removes the backmost element from the queue and returns its value. If the queue is empty before deletion, return -1.

Please note that when there are two middle positions, choose the frontmost position to operate on. For example:

• Adding 6 to the middle position of [1, 2, 3, 4, 5] results in the array [1, 2, 6, 3, 4, 5].
• Popping an element from the middle position of [1, 2, 3, 4, 5, 6] returns 3, and the array becomes [1, 2, 4, 5, 6].

Solution Approach #

• This is an easy problem. By using Go’s native doubly linked list implementation, list, this “front-middle-back queue” can be implemented easily.
• See the code for the specific implementation, and see the test file for several special test cases.

Code #

package leetcode

import (
	"container/list"
)

type FrontMiddleBackQueue struct {
	list   *list.List
	middle *list.Element
}

func Constructor() FrontMiddleBackQueue {
	return FrontMiddleBackQueue{list: list.New()}
}

func (this *FrontMiddleBackQueue) PushFront(val int) {
	e := this.list.PushFront(val)
	if this.middle == nil {
		this.middle = e
	} else if this.list.Len()%2 == 0 && this.middle.Prev() != nil {
		this.middle = this.middle.Prev()
	}
}

func (this *FrontMiddleBackQueue) PushMiddle(val int) {
	if this.middle == nil {
		this.PushFront(val)
	} else {
		if this.list.Len()%2 != 0 {
			this.middle = this.list.InsertBefore(val, this.middle)
		} else {
			this.middle = this.list.InsertAfter(val, this.middle)
		}
	}
}

func (this *FrontMiddleBackQueue) PushBack(val int) {
	e := this.list.PushBack(val)
	if this.middle == nil {
		this.middle = e
	} else if this.list.Len()%2 != 0 && this.middle.Next() != nil {
		this.middle = this.middle.Next()
	}
}

func (this *FrontMiddleBackQueue) PopFront() int {
	if this.list.Len() == 0 {
		return -1
	}
	e := this.list.Front()
	if this.list.Len() == 1 {
		this.middle = nil
	} else if this.list.Len()%2 == 0 && this.middle.Next() != nil {
		this.middle = this.middle.Next()
	}
	return this.list.Remove(e).(int)
}

func (this *FrontMiddleBackQueue) PopMiddle() int {
	if this.middle == nil {
		return -1
	}
	e := this.middle
	if this.list.Len()%2 != 0 {
		this.middle = e.Prev()
	} else {
		this.middle = e.Next()
	}
	return this.list.Remove(e).(int)
}

func (this *FrontMiddleBackQueue) PopBack() int {
	if this.list.Len() == 0 {
		return -1
	}
	e := this.list.Back()
	if this.list.Len() == 1 {
		this.middle = nil
	} else if this.list.Len()%2 != 0 && this.middle.Prev() != nil {
		this.middle = this.middle.Prev()
	}
	return this.list.Remove(e).(int)
}

/**
 * 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();
 */