题目地址
https://leetcode.com/problems/implement-queue-using-stacks/description/
题目描述
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Example:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
思路
这道题目是让我们用栈来模拟实现队列。 我们知道栈和队列都是一种受限的数据结构。
栈的特点是只能在一端进行所有操作,队列的特点是只能在一端入队,另一端出队。
在这里我们可以借助另外一个栈,也就是说用两个栈来实现队列的效果。这种做法的时间复杂度和空间复杂度都是O(n)。
由于栈只能操作一端,因此我们peek或者pop的时候也只去操作顶部元素,要达到目的
我们需要在push的时候将队头的元素放到栈顶即可。
因此我们只需要在push的时候,用一下辅助栈即可。
具体做法是先将栈清空并依次放到另一个辅助栈中,辅助栈中的元素再次放回栈中,最后将新的元素push进去即可。
比如我们现在栈中已经是1,2,3,4了。 我们现在要push一个5.
push之前是这样的:
然后我们将栈中的元素转移到辅助栈:
最后将新的元素添加到栈顶。
整个过程是这样的:
关键点解析
- 在push的时候利用辅助栈(双栈)
代码
- 语言支持:JS, Python, Java
Javascript Code:
/* * @lc app=leetcode id=232 lang=javascript * * [232] Implement Queue using Stacks */ /** * Initialize your data structure here. */ var MyQueue = function() { // tag: queue stack array this.stack = []; this.helperStack = []; }; /** * Push element x to the back of queue. * @param {number} x * @return {void} */ MyQueue.prototype.push = function(x) { let cur = null; while ((cur = this.stack.pop())) { this.helperStack.push(cur); } this.helperStack.push(x); while ((cur = this.helperStack.pop())) { this.stack.push(cur); } }; /** * Removes the element from in front of queue and returns that element. * @return {number} */ MyQueue.prototype.pop = function() { return this.stack.pop(); }; /** * Get the front element. * @return {number} */ MyQueue.prototype.peek = function() { return this.stack[this.stack.length - 1]; }; /** * Returns whether the queue is empty. * @return {boolean} */ MyQueue.prototype.empty = function() { return this.stack.length === 0; }; /** * Your MyQueue object will be instantiated and called as such: * var obj = new MyQueue() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.peek() * var param_4 = obj.empty() */
Python Code:
class MyQueue: def __init__(self): """ Initialize your data structure here. """ self.stack = [] self.help_stack = [] def push(self, x: int) -> None: """ Push element x to the back of queue. """ while self.stack: self.help_stack.append(self.stack.pop()) self.help_stack.append(x) while self.help_stack: self.stack.append(self.help_stack.pop()) def pop(self) -> int: """ Removes the element from in front of queue and returns that element. """ return self.stack.pop() def peek(self) -> int: """ Get the front element. """ return self.stack[-1] def empty(self) -> bool: """ Returns whether the queue is empty. """ return not bool(self.stack) # Your MyQueue object will be instantiated and called as such: # obj = MyQueue() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.peek() # param_4 = obj.empty()
Java Code
class MyQueue { Stack<Integer> pushStack = new Stack<> (); Stack<Integer> popStack = new Stack<> (); /** Initialize your data structure here. */ public MyQueue() { } /** Push element x to the back of queue. */ public void push(int x) { while (!popStack.isEmpty()) { pushStack.push(popStack.pop()); } pushStack.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { while (!pushStack.isEmpty()) { popStack.push(pushStack.pop()); } return popStack.pop(); } /** Get the front element. */ public int peek() { while (!pushStack.isEmpty()) { popStack.push(pushStack.pop()); } return popStack.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return pushStack.isEmpty() && popStack.isEmpty(); } } /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */
扩展
- 类似的题目有用队列实现栈,思路是完全一样的,大家有兴趣可以试一下。
- 栈混洗也是借助另外一个栈来完成的,从这点来看,两者有相似之处。
延伸阅读
实际上现实中也有使用两个栈来实现队列的情况,那么为什么我们要用两个stack来实现一个queue?
其实使用两个栈来替代一个队列的实现是为了在多进程中分开对同一个队列对读写操作。一个栈是用来读的,另一个是用来写的。当且仅当读栈满时或者写栈为空时,读写操作才会发生冲突。
当只有一个线程对栈进行读写操作的时候,总有一个栈是空的。在多线程应用中,如果我们只有一个队列,为了线程安全,我们在读或者写队列的时候都需要锁住整个队列。而在两个栈的实现中,只要写入栈不为空,那么push
操作的锁就不会影响到pop
。
-
reference
-
further reading
题目地址 https://leetcode.com/problems/implement-trie-prefix-tree/description/ 题目描述 Implement a trie with insert, search, and startsWith methods. Example: Trie trie = new Trie(); trie.…
LeetCode题解155.min-stack题目地址 https://leetcode.com/problems/min-stack/description/ 题目描述 Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push ele…
反转句子中每个单词的字符而无需反转单词顺序 - java我有这段代码应该按照标题的说明进行操作,在不更改单词顺序的情况下反转字符顺序:package stackTests; import java.util.Scanner; import java.util.Stack; public class StackTest { Stack<Character> stack; public StackTest…
LeetCode题解71. 简化路径以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径请注意,返回的规范路径必须始终以斜杠 / …