Using two stacks to realize the function of one queue?

This question is often given when learning data structures for beginners , I never expected to enter the society , I found that many large factories like to use various data structures to enable you to implement another data structure . Just understand the characteristics of stacks and queues , To realize the function of queue , That is, the composite use of stack functions , There are two stacks that can be combined twice to implement queues .

features

Stack ：FILO First in, then out .

queue ：FIFO fifo

Ideas

Use two stacks s1 and s2 When simulating a queue ,s1 As input stack , Stack elements one by one , This simulates the queueing of queue elements .

When you need to get out of the team , Stack s1 Step back and push into the stack one by one s2 in ,s1 The first element in the stack , stay s2 At the top of the stack .

s2 Backstack , It is equivalent to leaving the queue , First in, first out .

obviously , Only stack s2 Empty and s1 Also empty , The queue is empty .

Code

Suppose two stacks A and B, And all are empty .

It can be thought of as a stack A To provide the function of queuing , Stack B Provide the function of queue .

Queue entry ： Push A

Outgoing queue ：

1 If the stack B Not empty , Pop up the stack directly B The data of .

2 If the stack B It's empty

     2.1 if A Not empty , Then pop up the stack in turn A The data of , Put in the stack B in , Then pop up the stack B The data of .

     2.1 if A It's empty , Then the queue is empty .

Critical code