Sort a stack using only one other stack and no other data structures.

sortStack.ts

/*
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.
*/

function sortStack<T>(mainStack: MyStack<T>): MyStack<T> {
  const tempStack = new MyStack<T>()
  while (!mainStack.isEmpty()) {
    const node = mainStack.pop()
    while (!tempStack.isEmpty() && node.data < tempStack.peek().data) {
      mainStack.push(tempStack.pop().data)
    }
    tempStack.push(node.data)
  }

  while (!tempStack.isEmpty()) {
    mainStack.push(tempStack.pop().data)
  }

  return tempStack
}


const stack = new MyStack()

stack.push(3)
stack.push(8)
stack.push(3)
stack.push(2)
stack.push(1)
sortStack(stack)
while (!stack.isEmpty()) {
  console.log(stack.pop().data)
}