LeetCode进阶232、225-队列和栈

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

勘误

上一篇订阅号的推文LeetCode进阶103-蛇形打印二叉树(今日头条面试题)最后一种方法BFS-非递归的编码实践部分因为失误复制粘贴错了,由于微信公众平台支持修改字符上限为20,无法修改,需要查看正确编码解法的话请点击查看原文链接,原文挂在掘金上并已做修正。

概要

队列结构满足FIFO(first in first out)特点,与栈的FILO(first in last out)恰好相反。实际栈和队列之间可以相互模拟,即使用栈模拟队列或者使用队列模拟栈。

队列

232. 用栈实现队列

使用栈实现队列的下列操作:

push(x) -- 将一个元素放入队列的尾部。

pop() -- 从队列首部移除元素。

peek() -- 返回队列首部的元素。

empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();

queue.push(1);

queue.push(2);

queue.peek(); // 返回 1

queue.pop(); // 返回 1

queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。

分析&&思路

要使用栈来模拟队列,根据栈的先进后出的特点(后进先出)会使得元素倒序,不难联想到使用两个栈。第一个栈使得顺序变成倒序,第二个栈使得倒序又变成顺序即最终满足队列顺序的特点。参考图解:LeetCode进阶232、225-队列和栈

编码实践

  1. class MyQueue {

  2. Stack<Integer> s1 = new Stack<Integer>();

  3. Stack<Integer> s2 = new Stack<Integer>();


  4. public MyQueue() {


  5. }


  6. /**

  7. * 入"队列"至队尾

  8. *

  9. * @param x

  10. */

  11. public void push(int x) {

  12. s1.push(x);

  13. }


  14. /**

  15. * 首元素出“队列”

  16. *

  17. * @return

  18. */

  19. public int pop() {

  20. if (!s2.isEmpty()) {

  21. return s2.pop();

  22. }

  23. move();

  24. return s2.pop();

  25. }


  26. /**

  27. * 获取队列头部元素

  28. *

  29. * @return

  30. */

  31. public int peek() {

  32. if (!s2.isEmpty()) {

  33. return s2.peek();

  34. }

  35. move();

  36. return s2.peek();


  37. }


  38. /**

  39. * 利用第二个栈将“队列”中倒序的数据变成正序

  40. */

  41. private void move() {

  42. while (!s1.isEmpty()) {

  43. s2.push(s1.pop());

  44. }

  45. }

LeetCode进阶232、225-队列和栈

说明

见注释

225. 用队列实现栈

使用队列实现栈的下列操作:

push(x) -- 元素 x 入栈

pop() -- 移除栈顶元素

top() -- 获取栈顶元素

empty() -- 返回栈是否为空

注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。

你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。

分析&&思路

使用队列模拟栈,需要保证后进先出,在插入新元素到队列后,循环使得队列中队尾元素置顶即可。参考图解:LeetCode进阶232、225-队列和栈

编码实践

  1. class MyStack {

  2. Queue<Integer> queue = new LinkedList<Integer>();


  3. public MyStack() {


  4. }


  5. /**

  6. * 入“栈”至“栈”顶

  7. * 元素存入queue队列后,将存储元素的queue队列进行循环直到队尾元素成为队头

  8. * @param x

  9. */

  10. public void push(int x) {

  11. queue.add(x);

  12. for (int i = 0; i < queue.size() - 1; i++) {

  13. queue.add(queue.poll());

  14. }


  15. }


  16. /**

  17. * 出“栈”

  18. * @return

  19. */

  20. public int pop() {

  21. return queue.poll();

  22. }


  23. /**

  24. * 获取“栈”顶元素

  25. * @return

  26. */

  27. public int top() {

  28. return queue.peek();

  29. }


  30. /**

  31. * 判断“栈”是否为空

  32. * @return

  33. */

  34. public boolean empty() {

  35. return queue.isEmpty();

  36. }

  37. }

LeetCode进阶232、225-队列和栈

编码说明

见注释

总结

本篇通过介绍队列和栈的互相模拟方法加强对其特性的理解。实际开发中,队列和栈同样是十分重要的数据结构。最后,如果觉得本篇有所帮助或启发,不妨关注走一波~

LeetCode进阶232、225-队列和栈

关注订阅号 获取更多干货~


原文始发于微信公众号(Aeiric):LeetCode进阶232、225-队列和栈