With O(1) dequeue(), which is same as pythonquick's answer:
// time: O(n), space: O(n)
enqueue(x):
if stack.isEmpty():
stack.push(x)
return
temp = stack.pop()
enqueue(x)
stack.push(temp)
// time: O(1)
x dequeue():
return stack.pop()
With O(1) enqueue() (this is not mentioned in this post so this answer), which also uses backtracking to bubble up and return the bottommost item.
// O(1)
enqueue(x):
stack.push(x)
// time: O(n), space: O(n)
x dequeue():
temp = stack.pop()
if stack.isEmpty():
x = temp
else:
x = dequeue()
stack.push(temp)
return x
Obviously, it's a good coding exercise as it inefficient but elegant nevertheless.