LeetCode 双刀流:Stack 与 Queue 的相互实作

Stack 与 Queue 的相互实作

先看一下题目描述

225. Implement Stack using Queues

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).

232. Implement Queue using Stacks

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

更多细节可以参考 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

先来看 225. Implement Stack using Queues 这个题目,你需要知道这两个结构拥有的特性以及限制:

  • 目标:实现 Stack 中的「push」、「pop」、「top」和「empty」
  • 来源: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 当中有两种标准定义的方法:

  • shift:取出最左边(最早被加入)的元素
  • push:新加入的元素会边加入到最右边

所以这个题目的限制是只能利用 Queue 的 peek 跟 push 方法实现 Stack 中的方法,初步的想法是在每次执行新增元素的时候,当将 Queue 中的元素倒序,可以达到「新加入的元素,将变成第一个被取出的元素」行为,也就是 FILO 的效果。

用 Python 实作一次

在 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 复刻一次

在 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

先来看 232. Implement Queue using Stacks 这个题目,你需要知道这两个结构拥有的特性以及限制:

  • 目标:实现 Queue 中的「push」、「pop」、「peek」和「empty」
  • 来源:Stack

根据题目中有特别提到的注意事项:

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 当中有两种标准定义的方法:

  • pop:取出最上边(最新被加入)的元素
  • push:新加入的元素会边加入到最上方

所以这个题目的限制是只能利用 Stack 的 pop 跟 push 方法实现 Queue 中的方法,初步的想法是在每次执行新增元素的时候,当将 Stack 中的元素倒序,可以达到「新加入的元素,将变成最後一个被取出的元素」行为,也就是 FILO 的效果。

用 Python 实作一次

在 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 复刻一次

在 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 担任资料工程师,同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验,持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享,邀请你加入 订阅 接收最新资讯。


<<:  Day 17 免费个资隐私盘点工具

>>:  D17/ 我要用的 View 没有支援 Compose 怎麽办? - AndroidView

Day 4

在前一天,我们提到了价量是有一定的关系在。 正向成长,一般是价量齐涨,若价涨,但量没涨太多。 这时一...

Day 23 ATT&CK for ICS - Lateral Movement(1)

横向移动 攻击者尝试从进入工控网路的其中一个设备,横向移动到另外一台设备中。 T0812 Defau...

Day-27 请问 git rebase 和 git merge 是什麽?差别又在哪里?

写程序一定会用到令人又爱又恨的 Git 这个版控软件,让我们来了解一下 git rebase 和 ...

[Day01] CH00:Hello, Java!

欢迎来到「30 天 Java 从陌生到更陌生」 我是 Piglet,接下来的 30 天,会带着初踏入...

Day20 - this&Object Prototypes Ch3 Objects - Review 开头

Object 有 两种写法,作者建议有特殊需求再用 constructed form litera...