文章目录队列和栈的区别一.用队列模拟成功栈1.1入栈1.2出栈1.3前往栈顶元素1.4判别栈能否为空二.用栈模拟成功队列2.1入队2.2出队2.3peek2.4判别队列能否为空三.完整代码3.1队列模拟成功栈3.2栈模拟成功队列队列和栈的区别一.用队列模拟成功栈如上便是须要用队列来成功栈的四个基本操作,咱们试想,成功这些栈的操作,一个...。
文章目录
-
队列和栈的区别
-
一.用队列模拟成功栈
-
- 1.1入栈
- 1.2出栈
- 1.3前往栈顶元素
- 1.4判别栈能否为空
-
二.用栈模拟成功队列
-
- 2.1 入队
- 2.2出队
- 2.3peek
- 2.4判别队列能否为空
-
三.完整代码
-
- 3.1 队列模拟成功栈
- 3.2栈模拟成功队列
-
队列和栈的区别
一.用队列模拟成功栈
如上便是须要用队列来成功栈的四个基本操作。
咱们试想,成功这些栈的操作,一个队列可以成功吗?
显然无法以,咱们经常使用两个队列来成功栈的模拟
1.1入栈
当咱们要放入18 25 35 48 这一串数字入栈时,先放入18 25 35(放入时选用的队列是不为空的队列),模拟入队以及入栈时的状况,如下图
public void pushint x ifemptyqueue1offerxreturnifqueue1isEmptyqueue1offerxelse queue2offerx
1.2出栈
此时假设咱们要将35出栈时,又该如何操作呢?此时咱们就须要用到第二个队列,将队列一的前size-1个元素(也就是18 25)从队列一中出队,放入队列二中。此时队列一中的元素为35,队列二的元素为18 25 如下图。
现在栈成功时,咱们此时要将48入栈时,又该放入哪个栈中呢?咱们思考栈的特点(先入后出),咱们将再入栈的元素放到不为空的队列中。
public int pop if<img alt="栈和队列的交互成功" loading="lazy" src="https://pic1.zhimg.com/v2-a5b561a79e7040bda0de1e9453ad9a33_b.jpg"></img>emptyreturn 1ifqueue1isEmptyint size queue1sizefor int i 0 i size1 i queue2offerqueue1pollreturn queue1pollelse int size queue2sizefor int i 0 i size1 i queue1offerqueue2pollreturn queue2poll
1.3前往栈顶元素
在成功pop的基础上,咱们将声明一个变量temp来贮存每无所谓移除的元素。
public int top ifemptyreturn 1if queue1isEmptyint temp 1int size queue1sizefor int i 0 i size i temp queue1pollqueue2offertempreturn tempelse int size queue2sizeint temp 1for int i 0 i size i temp queue2pollqueue1offertempreturn temp
1.4判别栈能否为空
当队列一和队列二都为空时,此时栈就为空。
public boolean empty return queue1isEmptyqueue2isEmpty
二.用栈模拟成功队列
2.1 入队
咱们将一切入队的元素都放入栈一中,如下图
public void pushint x stack1pushx
2.2出队
要出栈时,假设栈二不为空,就出栈二中的元素,假设栈二为空,将栈一中的一切元素一次性性的所有push到栈二中,此时就将入栈的元素所有倒转上来了,(例如入栈时在栈中的入栈顺序依次排序为18 25 35,栈二中此时的元素入栈顺序是35 25 18,出栈时就先出18,就成功了转换)如下图
public int pop ifemptyreturn 1if stack2isEmptywhile stack1isEmptystack2pushstack1popreturn stack2pop
2.3peek
peek只是将出队时的pop换成peek,就可以成功要求。
public int peek ifemptyreturn 1if stack2isEmptywhile stack1isEmptystack2pushstack1popreturn stack2peek
2.4判别队列能否为空
假设栈一和栈二都为空时,那么队列就为空。
public boolean empty return stack1isEmpty stack2isEmpty
三.完整代码
3.1 队列模拟成功栈
class MyStack QueueInteger queue1 QueueInteger queue2 public MyStack queue1 new LinkedListqueue2 new LinkedListpublic void pushint x ifemptyqueue1offerxreturnifqueue1isEmptyqueue1offerxelse queue2offerxpublic int pop ifemptyreturn 1ifqueue1isEmptyint size queue1sizefor int i 0 i size1 i queue2offerqueue1pollreturn queue1pollelse int size queue2sizefor int i 0 i size1 i queue1offerqueue2pollreturn queue2pollpublic int top ifemptyreturn 1if queue1isEmptyint temp 1int size queue1sizefor int i 0 i size i temp queue1pollqueue2offertempreturn tempelse int size queue2sizeint temp 1for int i 0 i size i temp queue2pollqueue1offertempreturn temppublic boolean empty return queue1isEmptyqueue2isEmpty
3.2栈模拟成功队列
class MyQueue public StackInteger stack1 public StackInteger stack2public MyQueue stack1 new Stackstack2 new Stackpublic void pushint x stack1pushxpublic int pop ifemptyreturn 1if stack2isEmptywhile stack1isEmptystack2pushstack1popreturn stack2poppublic int peek ifemptyreturn 1if stack2isEmptywhile stack1isEmptystack2pushstack1popreturn stack2peekpublic boolean empty return stack1isEmpty stack2isEmpty
客服邮箱:kefu@itcaiji.cn
版权声明:未标注转载均为本站原创,转载时请以链接形式注明文章出处。如有侵权、不妥之处,请联系站长删除。敬请谅解!