算法面试通关 40 讲
覃超
Sophon Tech 创始人,前 Facebook 工程师,卡内基梅隆大学计算机硕士
78356 人已学习
新⼈⾸单¥68
课程目录
已完结/共 62 讲
第二章:理论讲解+面试题实战 (53讲)
算法面试通关 40 讲
登录|注册
留言
35
收藏
沉浸
阅读
分享
手机端
回顶部
当前播放: 09 | 面试题:用队列实现栈&用栈实现队列
00:00 / 00:00
高清
  • 高清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.75x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看
01 | 合格程序员的第一步:算法与数据结构
02 | 如何事半功倍地学习算法与数据结构
03 | 如何计算算法的复杂度
04 | 如何通过LeetCode来进行算法题目练习
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&判断链表是否有环
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是否有效
09 | 面试题:用队列实现栈&用栈实现队列
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第K大元素
12 | 面试题:返回滑动窗口中的最大值
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二叉搜索树
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索树的最近公共祖先
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时机
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最小深度
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方根的函数
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词搜索问题
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&比特位计数问题
42 | 面试题:N皇后问题的另一种解法
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径和
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友圈(上)
54 | 面试题:岛屿的个数&朋友圈(下)
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LRU Cache缓存机制
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件套
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契数列
62 | 结课测试&最后的一些经验分享
登录 后留言

全部留言(35)

  • 最新
  • 精选
一直等月落
Java语言实现版,在push时候做翻转 class MyStack { Queue<Integer> queue=new LinkedList<Integer>(); /** Push element x onto stack. */ public void push(int x) { Queue<Integer> temp=new LinkedList<Integer>(); while (!queue.isEmpty()){ temp.add(queue.poll()); } queue.add(x); while (!temp.isEmpty()){ queue.add(temp.poll()); } } /** Removes the element on top of the stack and returns that element. */ public int pop() { return queue.poll(); } /** Get the top element. */ public int top() { return queue.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return queue.isEmpty(); } }

作者回复: 赞!

2019-04-01
2
Derek
GO语言版实现: type MyQueue struct { inStack []int outStack []int } /** Initialize your data structure here. */ func Constructor() MyQueue { return MyQueue{ inStack: make([]int, 0), outStack: make([]int, 0), } } /** Push element x to the back of queue. */ func (this *MyQueue) Push(x int) { this.inStack = append(this.inStack, x) } /** Removes the element from in front of queue and returns that element. */ func (this *MyQueue) Pop() int { for _, v := range this.inStack { this.outStack = append(this.outStack, v) } this.inStack = make([]int, 0) v := this.outStack[0] this.outStack = this.outStack[1 : len(this.outStack)-1] return v } /** Get the front element. */ func (this *MyQueue) Peek() int { for _, v := range this.inStack { this.outStack = append(this.outStack, v) } this.inStack = make([]int, 0) return this.outStack[0] } /** Returns whether the queue is empty. */ func (this *MyQueue) Empty() bool { return len(this.inStack) != 0 || len(this.outStack) != 0 } /** * Your MyQueue object will be instantiated and called as such: * obj := Constructor(); * obj.Push(x); * param_2 := obj.Pop(); * param_3 := obj.Peek(); * param_4 := obj.Empty(); */

作者回复: 👍🏻👍🏻

2018-12-12
卷福
接着shawn的优化一下。前面的步骤都一样,最后的input output可以不用互换,只需要在每次push/pull/peek操作前判断一下哪个队列不为空,就从不为空的队列开始操作到空的队列即可,省去了一次互换的操作,减少了一倍的时间复杂度。
2018-10-25
9
Jimbol
老师能否指点下如何用队列实现栈呢?
2018-10-13
2
6
shawn
队列变栈,应该是两个队列,input和output,入input,出的时候,出input全队放入output中,pop把最后出队的值返回不放回output,peek放回output,然后input output互换,后续操作都如此吧
2018-10-23
5
driver
我这提供一个队列实现栈的思路:入栈在非空队列中加入(如果都是空队列任选一个队列加入),出栈和查看栈顶元素,把非空队列元素输入到空队列中,最后一个输入元素就是要出栈或者查看的元素。
2018-10-19
5
ada_shen
老师,我刚刚又优化了下速度,因为刚刚在leetcode试了之前的方法才击败了50%,现在这个击败96% # -*- coding: UTF-8 -* class MyQueue(object): def __init__(self): """ Initialize your data structure here. """ self.input_stack = [] self.output_stack = [] def push(self, x): """ Push element x to the back of queue. :type x: int :rtype: None """ self.input_stack.append(x) def pop(self): """ Removes the element from in front of queue and returns that element. :rtype: int """ if self.empty(): return None else: if len(self.output_stack): return self.output_stack.pop() else: # for i in xrange(0, len(self.input_stack)): # self.output_stack.append(self.input_stack.pop()) length = len(self.input_stack) self.output_stack = map(lambda x: self.input_stack.pop(), range(0, length)) return self.output_stack.pop() def peek(self): """ Get the front element. :rtype: int """ if self.empty(): return None else: if len(self.output_stack): return self.output_stack[-1] else: # for i in xrange(0, len(self.input_stack)): # self.output_stack.append(self.input_stack.pop()) length = len(self.input_stack) self.output_stack = map(lambda x: self.input_stack.pop(), range(0, length)) return self.output_stack[-1] def empty(self): """ Returns whether the queue is empty. :rtype: bool """ return bool(len(self.input_stack) == 0 and len(self.output_stack) == 0)
2019-07-16
3
编码者
public class MyQueue { Stack<int> _inputStack; Stack<int> _outputStack; /** Initialize your data structure here. */ public MyQueue() { _inputStack = new Stack<int>(); _outputStack = new Stack<int>(); } /** Push element x to the back of queue. */ public void Push(int x) { _inputStack.Push(x); } /** Removes the element from in front of queue and returns that element. */ public int Pop() { MoveInputToOutput(); return _outputStack.Pop(); } /** Get the front element. */ public int Peek() { MoveInputToOutput(); return _outputStack.Peek(); } /** Returns whether the queue is empty. */ public bool Empty() { return _inputStack.Count == 0 && _outputStack.Count == 0; } private void MoveInputToOutput() { if (_outputStack.Count == 0) { while (_inputStack.Count != 0) { _outputStack.Push(_inputStack.Pop()); } } } }
2020-04-16
2
pikachu122
LeetCode232 Java代码 0 ms 34.2 MB 打败100%Java提交 class MyQueue { Stack<Integer> in = new Stack<>(); Stack<Integer> out = new Stack<>(); /** Initialize your data structure here. */ public MyQueue() { } /** Push element x to the back of queue. */ public void push(int x) { in.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { if (out.isEmpty()) { while (!in.isEmpty()) { out.push(in.pop()); } } return out.pop(); } /** Get the front element. */ public int peek() { if (out.isEmpty()){ while (!in.isEmpty()) { out.push(in.pop()); } } return out.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return in.isEmpty() && out.isEmpty(); } }
2020-01-16
2
他在她城断了弦
关于用队列实现栈,大家可以看我写的博客,有两种比较好想的思路:https://blog.csdn.net/zpznba/article/details/83987480
2018-11-12
2
收起评论