Stack with Constant-Time Middle Queries
Problem statement
Process a sequence of stack operations. Each operation is ["push", value], ["pop"], ["top"], or ["middle"]. Values are signed decimal integers encoded as strings.
Return one string for every non-push operation. For an empty stack, return EMPTY. For an even-sized stack, middle returns the lower middle element, the one closer to the bottom. Every operation must run in constant time; preallocated array storage is allowed.
Function
processMiddleStack(operations: String[][]) → String[]Examples
Example 1
operations = [["push","1"],["push","2"],["push","3"],["middle"],["top"],["pop"],["middle"]]return = ["2","3","3","1"]The lower middle of three values is 2; after popping 3, the lower middle of [1,2] is 1.
Example 2
operations = [["top"],["middle"],["pop"]]return = ["EMPTY","EMPTY","EMPTY"]All three queries use the empty sentinel.
Example 3
operations = [["push","-4"],["middle"],["pop"]]return = ["-4","-4"]A one-element stack has the same top and middle.
Constraints
1 ≤ operations.length ≤ 100000.- Every operation has one of the four documented forms.
- Push values are integers in
[-10^9, 10^9]. - The output contains one entry for every non-push operation.