Design a Stack with O(1) Push, Pop, GetMiddle, and GetTop

Problem Statement

Design a stack data structure that supports the following operations, all in O(1) time:

1. push(val) — Push an element onto the stack
2. pop() — Remove and return the top element
3. getTop() — Return the top element without removing it
4. getMiddle() — Return the middle element without removing it

If the stack has an even number of elements, return the lower-middle (floor).

Constraints

• All operations must be O(1) time
• At most 10^5 operations
• getMiddle() and pop() on an empty stack should return -1 or throw

Example

push(1)  → stack: [1]           → middle: 1
push(2)  → stack: [1, 2]        → middle: 1
push(3)  → stack: [1, 2, 3]     → middle: 2
push(4)  → stack: [1, 2, 3, 4]  → middle: 2
pop()    → returns 4, stack: [1, 2, 3] → middle: 2
pop()    → returns 3, stack: [1, 2]    → middle: 1

What the Interviewer Expects

1. Why a regular array/stack doesn't work — getMiddle is O(n) with a plain array if you need to also support O(1) pop.
2. Doubly Linked List + middle pointer — the key insight. Maintain a pointer to the middle node and update it on every push/pop.
3. Middle pointer movement logic:
   • On push: if new size is odd, move middle forward
   • On pop: if new size is even, move middle backward
4. Edge cases — empty stack, single element, two elements.

Follow-ups

1. What if you also need deleteMiddle() in O(1)? How does the approach change?
2. Can you implement this using two stacks instead of a linked list?
3. What if "middle" is defined as upper-middle for even-length stacks? What changes?
4. How would you make this thread-safe?