java实现-剑指offer-面试题7:用两个栈实现队列

题目:用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。

思路:

栈的特点是后进先出,队列的特点是先进先出。

对于队列的插入功能,栈的压栈操作即可模拟。所以重点在于怎样用栈来模拟队列的删除元素操作,即保证先进入队列的元素先删除。

最直观的办法,就是用stack1来添加元素,需要删除元素的时候,将stack1的元素都弹出,依次压入stack2,这样再从stack2弹出,顺序就如同队列一样是先进先出了。

需要考虑的关键点就在于,当stack2不为空时,删除操作直接从stack2弹出元素即可;当stack2为空时,需要判断stack1里是否有元素,有的话则先把stack1的元素全部压入stack2才可以继续进行弹出操作。

以下面为例:

添加元素:1 2 3  -- stack1元素从栈顶开始为3 2 1,stack2为空

删除元素:1 2  --将stack1元素全部弹出压入stack2,stack1为空,stack2从栈顶开始元素为1 2 3,弹出1 2,剩下元素3

添加元素:4 5  --stack1依次压入4 5,且只含这两个元素,stack2还是3

 删除元素:3 4 --先查看stack2不为空,弹出元素3,然后判断stack1不为空,将元素弹出压入stack2,再弹出4即可,此时stack1为空,stack2剩下元素5

最后的代码如下

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 栈 栈的英文单词是Stack,它代表一种特殊的线性表,这种线性表只能在固定一端(通常认为是线性表的尾端)进行插入,...
    Jack921阅读 5,424评论 0 5
  • 题目描述:用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 分析:一个队列包含...
    levinhax阅读 12,382评论 0 4
  • 1.栈 1.1.栈的定义 栈(stack)是限定仅在表尾(栈顶 top)进行插入和删除操作的后进先出的线性表。 p...
    JonyFang阅读 5,248评论 0 21
  • 本文内容取自于小甲鱼的数据结构与算法。http://www.jianshu.com/p/230e6fde9c75 ...
    阿阿阿阿毛阅读 8,043评论 0 7
  • 一直以来,我都很少使用也避免使用到树和图,总觉得它们神秘而又复杂,但是树在一些运算和查找中也不可避免的要使用到,那...
    24K男阅读 11,707评论 5 14