232 - 用栈实现队列(implement-queue-using-stacks)

Create by jsliang on 2019-7-16 08:15:25
Recently revised in 2019-7-16 08:39:59

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
四 执行测试
五 LeetCode Submit
六 解题思路

二 前言

返回目录

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

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 操作)。

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

  • 解题代码
var MyQueue = function() {
  this.stack1 = [];
  this.stack2 = [];
};

MyQueue.prototype.push = function(x) {
  // 检查 stack2 是否为空,如果不为空把 stack2 的内容 pop 出来在压入 stack1 中
  while (this.stack2.length) {
    this.stack1.push(this.stack2.pop());
  }
  this.stack1.push(x);
};

MyQueue.prototype.pop = function() {
  // 每次 pop 都先把 stack1 中的元素压入 stack2 中
  while (this.stack1.length) {
    this.stack2.push(this.stack1.pop());
  }
  return this.stack2.pop();
};

MyQueue.prototype.peek = function() {
  while (this.stack2.length) {
    this.stack1.push(this.stack2.pop());
  }
  return this.stack1[0];
};

MyQueue.prototype.empty = function() {
  while (this.stack2.length) {
    this.stack1.push(this.stack2.pop());
  }
  return !this.stack1.length;
};

四 执行测试

返回目录

let queue = new MyQueue();

queue.push(1);
queue.push(2);
console.log(queue.peek());  // 1
console.log(queue.pop());   // 1
console.log(queue.empty()); // false

五 LeetCode Submit

返回目录

√ Accepted
  √ 17/17 cases passed (72 ms)
  √ Your runtime beats 91.08 % of javascript submissions
  √ Your memory usage beats 98.9 % of javascript submissions (33.1 MB)

六 解题思路

返回目录

如果小伙伴们看过 225-用队列实现栈,那么小伙伴对这道题也是迎刃而解;

如果没看过,没问题,咱复制粘贴过来(滑稽脸):

首先,官方出这道题的想法是,让小伙伴们了解下队列和栈。

那么,我们就讲讲这两者:

  • 队列:先进先出。简单来说,就是有一个数组,通过 push() 推进每个元素,通过 shift() 推出第一个元素,这种形式就是队列。
  • 栈:先进后出。简单来说,就是有一个数组,通过 push() 推进每个元素,通过 pop() 推出最后一个元素,这种形式就是栈。

如果小伙伴们还是不理解,那么我们讲讲两个例子:

  • 队列:饭堂打饭。我们需要排队,先到的排前面,打完饭后可以先走。
  • 栈;俄罗斯套娃,或者叠罗汉。先进的需要最后出,要不然取不出来,或者罗汉直接倒了。

最后,根据这个思路,我们可以轻易求解。


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-16 19:20:43

results matching ""

    No results matching ""