queue with 1 stack

Using recursion and backtracking, i.e. using the method call stack as the "other" stack to hold on to the elements.

// O(n)
enqueue(x):
    if stack.isEmpty():
        stack.push(x)
        return
    temp = stack.pop()
    enqueue(x)
    stack.push(temp)

// O(1)
x dequeue():
    return stack.pop()

// O(1)
enqueue(x):
    stack.push(x)

// O(n)
x dequeue():
    temp = stack.pop()
    if stack.isEmpty():
        x = temp
    else:
        x = dequeue()
        stack.push(temp)
    return x

[Hat tip to SO]