The queue can be implemented with two stacks. Always push into one stack A and pop from the other stack B. When B is empty and still need a pop, move all the elements from A to B. The amortized time complexity is still O(1).