Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
这里稍微补充说明一下,Stacks 和 Queues 是两种方向不同的抽象资料结构(ADT)。如下图所示,Stack 的特性是「FILO」,也就是说它提供同一个入口与出口,先被加入的元素会比较晚被取出。Queue 的特性是「FIFO」,也就是说它提供分别两个入口与出口,从入口先被加入的元素会从出口比较早被取出。
更多细节可以参考 Algorithms - Stacks and Queues 内文。
class MyStack:
def __init__(self):
def push(self, x: int) -> None:
def pop(self) -> int:
def top(self) -> int:
def empty(self) -> bool:
class MyQueue:
def __init__(self):
def push(self, x: int) -> None:
def pop(self) -> int:
def peek(self) -> int:
def empty(self) -> bool:
# Your MyStack object will be instantiated and called as such:
obj = MyStack()
obj.push(x)
param_2 = obj.pop()
param_3 = obj.top()
param_4 = obj.empty()
# 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()
这个题目的形式类似於「填空题」,需要把题目中不同物件的细节补上。而这两题想练习是「如何用 Stack 实作 Queue」以及「如何用 Queue 实作 Stack」。
在理解完题目与条件之後,那我们下一步就开始「#初探直觉解」并且一起尝试「#刻意优化」的过程:
先来看 225. Implement Stack using Queues 这个题目,你需要知道这两个结构拥有的特性以及限制:
根据题目中有特别提到的注意事项:
You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
简单来说,本题仅可使用 Queue 资料结构作为来源 ,而在 Queue 当中有两种标准定义的方法:
所以这个题目的限制是只能利用 Queue 的 peek 跟 push 方法实现 Stack 中的方法,初步的想法是在每次执行新增元素的时候,当将 Queue 中的元素倒序,可以达到「新加入的元素,将变成第一个被取出的元素」行为,也就是 FILO 的效果。
在 Python 中,我们会利用 [...] 代表 Queue,当中的 append(...) 用来 加入元素
、 [0]/pop(0) 用来 取出元素
。
class MyStack:
def __init__(self):
self.queue = []
def push(self, x: int) -> None:
self.queue.append(x)
for _ in range(len(self.queue)-1):
self.queue.append(self.queue[-1])
self.queue = self.queue.remove(self.queue[-1])
def pop(self) -> int:
return self.queue.pop(0)
def top(self) -> int:
return self.queue[0]
def empty(self) -> bool:
return not self.queue
在 JavaScript 中,我们会利用 [...] 代表 Queue,当中的 push(...) 用来 加入元素
、 [0]/shift() 用来 取出元素
。
var MyStack = function() {
this.queue = [];
};
MyStack.prototype.push = function(x) {
this.queue.push(x);
for(let i = 1; i < this.queue.length; i++){
this.queue.push(this.queue.shift());
}
};
MyStack.prototype.pop = function() {
return this.queue.shift();
};
MyStack.prototype.top = function() {
return this.queue[0];
};
MyStack.prototype.empty = function() {
return this.queue.length === 0;
};
先来看 232. Implement Queue using Stacks 这个题目,你需要知道这两个结构拥有的特性以及限制:
根据题目中有特别提到的注意事项:
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.
简单来说,本题仅可使用 Stack 资料结构作为来源 ,而在 Stack 当中有两种标准定义的方法:
所以这个题目的限制是只能利用 Stack 的 pop 跟 push 方法实现 Queue 中的方法,初步的想法是在每次执行新增元素的时候,当将 Stack 中的元素倒序,可以达到「新加入的元素,将变成最後一个被取出的元素」行为,也就是 FILO 的效果。
在 Python 中,我们会利用 [...] 代表 stack,当中的 append(...) 用来 加入元素
、 [-1]/pop() 用来 取出元素
。
class MyQueue:
def __init__(self):
self.stack = []
def push(self, x):
swap = []
while self.stack:
swap.append(self.stack.pop())
swap.append(x)
while swap:
self.stack.append(swap.pop())
def pop(self) -> int:
return self.stack.pop()
def peek(self) -> int:
return self.stack[-1]
def empty(self) -> bool:
return not self.stack
在 JavaScript 中,我们会利用 [...] 代表 Queue,当中的 push(...) 用来 加入元素
、 [this.stack.length-1]/pop() 用来 取出元素
。
var MyQueue = function() {
this.stack = [];
};
MyQueue.prototype.push = function(x) {
swap = []
while(this.stack.length > 0)
swap.push(this.stack.pop());
swap.push(x)
while(swap.length > 0)
this.stack.push(swap.pop());
};
MyQueue.prototype.pop = function() {
return this.stack.pop();
};
MyQueue.prototype.peek = function() {
return this.stack[this.stack.length-1];
};
MyQueue.prototype.empty = function() {
return this.stack.length === 0;
};
这个题目是关於 Stack 和 Queue 的经典实作题,他们是两种方向不同的抽象资料结构(ADT)。也就是说,我们会定义一个 Stack 或 Queue 需要有哪些方法与特性,但我们不会特别限制实际上如何实现,因此常见的方法可以利用阵列、阵列串链来实作。而这个题目比较特别的是,如何用 Stack 与 Queue 两个结构相互实作。因此,必须要了解这两个结构的特性与方法并且能够进一步运用,才能更有效地完成该题目。
嗨,大家好!我是维元,一名擅长网站开发与资料科学的双栖工程师,斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师,同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验,持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享,邀请你加入 订阅 接收最新资讯。
>>: D17/ 我要用的 View 没有支援 Compose 怎麽办? - AndroidView
在前一天,我们提到了价量是有一定的关系在。 正向成长,一般是价量齐涨,若价涨,但量没涨太多。 这时一...
横向移动 攻击者尝试从进入工控网路的其中一个设备,横向移动到另外一台设备中。 T0812 Defau...
写程序一定会用到令人又爱又恨的 Git 这个版控软件,让我们来了解一下 git rebase 和 ...
欢迎来到「30 天 Java 从陌生到更陌生」 我是 Piglet,接下来的 30 天,会带着初踏入...
Object 有 两种写法,作者建议有特殊需求再用 constructed form litera...