Design a stack that supports accessing both its top and middle elements without traversing the stored values.

Every supported operation must run in constant time.

Class

MiddleStack

Constructor

MiddleStack

MiddleStack()

• Creates an empty stack.

Methods

push

void push(int value)

• Adds value to the top of the stack.

pop

int pop()

• Removes and returns the top element of the stack.

getMiddle

int getMiddle()

• Returns the middle element without removing it.

getTop

int getTop()

• Returns the top element without removing it.

Rules

• The stack follows last-in, first-out order.
• If the stack contains n elements, positions are counted from the bottom starting at 1.
• The middle element is at position floor(n / 2) + 1 from the bottom.
• Therefore, when the stack has an even number of elements, the middle element closer to the top is returned.
• Calling getMiddle or getTop does not modify the stack.
• Duplicate values are allowed.

Constraints

• -1,000,000,000 ≤ value ≤ 1,000,000,000
• At most 100,000 method calls will be made.
• The stack will contain at most 100,000 elements.
• pop, getMiddle, and getTop will be called only when the stack is not empty.

Expected Efficiency

• push, pop, getMiddle, and getTop must each run in O(1) time.
• The stack may use O(n) space for n stored elements.

Example 1

MiddleStack()

push(value = 8)

push(value = 3)

push(value = 14)

push(value = 6)

The stack from bottom to top is now [8, 3, 14, 6].

getTop() returns 6.

getMiddle() returns 14.

pop() returns 6.

The stack from bottom to top is now [8, 3, 14].

getMiddle() returns 3.

getTop() returns 14.

Example 2

MiddleStack()

push(value = -7)

push(value = 12)

The stack from bottom to top is now [-7, 12].

getMiddle() returns 12 because it is the middle element closer to the top.

pop() returns 12.

getTop() returns -7.

getMiddle() returns -7.