剑指Offer--用两个栈实现队列

问题描述:用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

解题思路:这道题的意图是要求我们操作这两个“先进后出”的栈实现一个“先进先出”的队列。以实例分析,将a  b  c三个字符依次插入stack1,则在stack1中有{a,b,c},其中c位于栈顶,是最后插入的元素。如要实现“先入先出”,则a应该首先弹出,但是在stack1中首先弹出的是c,此时只要想办法将a移到栈顶位置即可,题目中要求两个栈实现一个队列,那么我们就可以把stack1中的元素依次弹出,然后压入到stack2中(stack2为空),Stack2中有{c,b,a},其中a位于栈顶,首先弹出的元素就是a。然后需要弹出元素b,在stack2中b元素位于栈顶,直接弹出即可。

总结:当stack2不为空时,在stack2中的栈顶元素是最先进入的元素,可以弹出。

 

代码:

 

原文地址:https://www.cnblogs.com/xiaoxli/p/9392934.html