快捷搜索:  汽车  科技

如何用两个队列模拟实现一个栈(如何用栈实现队列)

如何用两个队列模拟实现一个栈(如何用栈实现队列)入队:队列的特点是先入先出,出入元素是在不同的两端(队头和队尾):栈的特点是先入后出,出入元素都是在同一端(栈顶):入栈:出栈:

点击上方关注,每天学习一个java知识点

原创: 小灰 程序员小灰

如何用两个队列模拟实现一个栈(如何用栈实现队列)(1)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(2)

————— 第二天 —————

如何用两个队列模拟实现一个栈(如何用栈实现队列)(3)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(4)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(5)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(6)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(7)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(8)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(9)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(10)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(11)

————————————

如何用两个队列模拟实现一个栈(如何用栈实现队列)(12)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(13)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(14)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(15)

栈的特点是先入后出,出入元素都是在同一端(栈顶):

入栈:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(16)

出栈:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(17)

队列的特点是先入先出,出入元素是在不同的两端(队头和队尾):

入队:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(18)

出队:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(19)

既然我们拥有两个栈,那么我们可以让其中一个栈作为队列的入口,负责插入新元素;另一个栈作为队列的出口,负责移除老元素。

如何用两个队列模拟实现一个栈(如何用栈实现队列)(20)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(21)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(22)

队列的主要操作无非有两个:入队和出队。

在模拟入队操作时,每一个新元素都被压入到栈A当中。

让元素1 “入队”:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(23)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(24)

让元素2 “入队”:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(25)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(26)

让元素3 “入队”:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(27)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(28)

这时候,我们希望最先“入队”的元素1“出队”,需要怎么做呢?

让栈A中的所有元素按顺序出栈,再按照出栈顺序压入栈B。这样一来,元素从栈A弹出并压入栈B的顺序是3 2 1,和当初进入栈A的顺序1 2 3是相反的:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(29)

此时让元素1 “出队”,也就是让元素1从栈B弹出:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(30)

让元素2 “出队”:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(31)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(32)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(33)

让元素4 “入队”:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(34)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(35)

此时的出队操作仍然从栈B弹出元素。

让元素3 “出队”:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(36)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(37)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(38)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(39)

让元素4 “出队”:

如何用两个队列模拟实现一个栈(如何用栈实现队列)(40)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(41)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(42)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(43)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(44)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(45)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(46)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(47)

如何用两个队列模拟实现一个栈(如何用栈实现队列)(48)

猜您喜欢: