03.05. Sort of Stacks

Description

Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty. When the stack is empty, peek should return -1.

Example1:


 Input:

["SortedStack", "push", "push", "peek", "pop", "peek"]

[[], [1], [2], [], [], []]

 Output:

[null,null,null,1,null,2]

Example2:


 Input:

["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]

[[], [], [], [1], [], []]

 Output:

[null,null,null,null,null,true]

Note:

The total number of elements in the stack is within the range [0, 5000].

Solutions

Solution 1: Stack + Auxiliary Stack

We define a stack $stk$ for storing elements.

In the push operation, we define an auxiliary stack $t$ for storing elements in $stk$ that are smaller than the current element. We pop all elements smaller than the current element from $stk$ and store them in $t$, then push the current element into $stk$, and finally pop all elements from $t$ and push them back into $stk$. The time complexity is $O(n)$.

In the pop operation, we just need to check if $stk$ is empty. If it's not, we pop the top element. The time complexity is $O(1)$.

In the peek operation, we just need to check if $stk$ is empty. If it is, we return -1, otherwise, we return the top element. The time complexity is $O(1)$.

In the isEmpty operation, we just need to check if $stk$ is empty. The time complexity is $O(1)$.

The space complexity is $O(n)$, where $n$ is the number of elements in the stack.