差点翻车

## 前言

`GithubAction`作为`Github`提供的免费的`CI/CD`服务，让开发者感受到了自动化的爽，相比起`Travis CI`来说，`GitHubAction`集成方便，非常适合快速部署的操作，本教程便是一篇如何利用`GithubAction`对于`GithubPage+Hexo`博客进行自动化部署，并利用`gulp`进行压缩。

## 配置GithubAction

### 生成key

首先依旧是申请key，

```shell
cd ~/.ssh
ssh-keygen -t rsa -b 4096 -C "$(git config user.email)" -f gh-pages -N ""
```

![image-20200724215856700](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724215856700.png)

此时会生成**.pub的公钥与没有后缀的私钥**：

![成功生成密钥](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200721154822499.png)

### 配置仓库

首先新建一个空仓库，用于存放你的博客根目录，新建完成后将**博客根目录**所有文件都上传到这个仓库中，传完项目结构大体如下：

![image-20200724220337436](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724220337436.png)

然后开始配置仓库，首先

![image-20200724220449987](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724220449987.png)

![image-20200724220517055](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724220517055.png)

配置成你的公钥，然后在上传博客的仓库中，上传你的私钥：

![image-20200724220651398](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724220651398.png)

**注意这里的私钥名字一定要跟后面Action里面设置的一样！(不知道就跟我一样)**

### 配置workflow

在博客根目录新建`.github`文件夹，再在`.github`文件夹里新建`workflows`文件夹，新建完在`workflows`文件夹里新建`deploy.yml`文件，然后按照如下编写：

```yaml
# workflow name
name: Deploy To Github Pages

# 当有 push 到仓库就运行
on: [push]

jobs:
  deploy: 
    name: Deploy Hexo Public To Pages
    runs-on: ubuntu-latest 
    env:
      TZ: Asia/Shanghai    
        
    steps:
    # 切换到master
    # from: https://github.com/actions/checkout
    - name: Checkout Repository master branch
      uses: actions/checkout@master 
    
    # 安装node
    # from: https://github.com/actions/setup-node  
    - name: Setup Node.js 11.x 
      uses: actions/setup-node@master
      with:
        node-version: "11.x"
    
    # 缓存 node_modules
    - name: Cache node modules
      uses: actions/cache@v2
      with:
        path: ~/.npm
        key: ${{ runner.os }}-node-${{ hashFiles('**/package-lock.json') }}
        restore-keys: |
          ${{ runner.OS }}-build-${{ env.cache-name }}-
          ${{ runner.OS }}-build-
          ${{ runner.OS }}-

    # 安装hexo并生成
    - name: Setup Hexo Dependencies
      run: |
        npm install hexo-cli -g
        npm install
        hexo generate
        
    # 部署到GitHubPage
    # from https://github.com/peaceiris/actions-gh-pages    
    - name: Deploy
      uses: peaceiris/actions-gh-pages@v3
      with:
        deploy_key: ${{ secrets.ACTIONS_DEPLOY_KEY }}
        # 这里写你自己的仓库名
        external_repository: xmmmmmovo/xmmmmmovo.github.io
        publish_branch: master
        publish_dir: ./public
        commit_message: ${{ github.event.head_commit.message }}

```

好了，这样就已经配置完成了，你每次提交到此仓库，便会自动帮你运行部署到GithubPage上去。

### 测试

![image-20200724221510619](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724221510619.png)

![image-20200724221450653](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724221450653.png)

可以看到，已经成功运行了。

## 配置gulp

我们随便点开一个文件：

![image-20200724221832348](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724221832348.png)

可以看到，里面充斥着大量的空格，积少成多，这会占用非常多的时间，让你的博客感觉加载起来很慢，所以既然我们都是全自动化部署了，我们不如直接在进行一遍压缩操作，这样使你博客加载的更加迅速，体验更加良好。

### 安装gulp

首先进到博客根目录，然后打开命令行，输入(这里其实你直接在`package.json`里面写也行(因为node_modules已经没用了)，但是我比较懒)：

```shell
npm install gulp@3.9.1 gulp-minify-css gulp-htmlmin gulp-htmlclean --save-dev
```

待完成后，改写`deploy.yml`：

```yaml
# workflow name
name: Deploy To Github Pages

# 当有 push 到仓库就运行
on: [push]

jobs:
  deploy: 
    name: Deploy Hexo Public To Pages
    runs-on: ubuntu-latest 
    env:
      TZ: Asia/Shanghai    
        
    steps:
    # 切换到master
    # from: https://github.com/actions/checkout
    - name: Checkout Repository master branch
      uses: actions/checkout@master 
    
    # 安装node
    # from: https://github.com/actions/setup-node  
    - name: Setup Node.js 11.x 
      uses: actions/setup-node@master
      with:
        node-version: "11.x"
    
    # 缓存 node_modules
    - name: Cache node modules
      uses: actions/cache@v2
      with:
        path: ~/.npm
        key: ${{ runner.os }}-node-${{ hashFiles('**/package-lock.json') }}
        restore-keys: |
          ${{ runner.OS }}-build-${{ env.cache-name }}-
          ${{ runner.OS }}-build-
          ${{ runner.OS }}-

    # 安装hexo并生成
    - name: Setup Hexo Dependencies
      run: |
        npm install hexo-cli -g
        npm install
        hexo generate
        gulp
        
    # 部署到GitHubPage
    # from https://github.com/peaceiris/actions-gh-pages    
    - name: Deploy
      uses: peaceiris/actions-gh-pages@v3
      with:
        deploy_key: ${{ secrets.ACTIONS_DEPLOY_KEY }}
        # 这里写你自己的仓库名
        external_repository: xmmmmmovo/xmmmmmovo.github.io
        publish_branch: master
        publish_dir: ./public
        # 这里我改成了与原格式相似格式的commit message
        commit_message: 'Site updated: ${{ github.event.head_commit.timestamp }}'

```

然后编写`gulpfile.js`文件用来加载`gulp`：

```javascript
var gulp = require('gulp');
var minifycss = require('gulp-minify-css');
var htmlmin = require('gulp-htmlmin');
var htmlclean = require('gulp-htmlclean');
gulp.task('minify-css', function() {
    return gulp.src('./public/**/*.css')
        .pipe(minifycss())
        .pipe(gulp.dest('./public'))
});
gulp.task('minify-html', function() {
  return gulp.src('./public/**/*.html')
    .pipe(htmlclean())
    .pipe(htmlmin({
         removeComments: true,
         minifyJS: true,
         minifyCSS: true,
         minifyURLs: true
    }))
    .pipe(gulp.dest('./public'))
});
gulp.task('default', ['minify-html', 'minify-css']);
```

此时再次提交，等待`GithubAction`完成之后，便可以查看效果了~

![image-20200724222548668](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724222548668.png)

可以看到800多行瞬间变为了16行，是不是很爽~

如何利用GitHubAction和gulp自动化部署压缩你的GithubPage+Hexo博客

第一次看见的前面就标有极难的题目

## 思路

### 参考

本问题其实是有一篇论文作为参考的:

{% pdf https://ecommons.cornell.edu/bitstream/handle/1813/6273/80-433.pdf %}

这篇论文是以`LISP`作为实现语言的，我们本次依旧是使用`kotlin`进行实现。

当然，这里三个栈需要实现的是**双向队列**的**API**，六个栈实现的是**单向队列**。

### 实现思路

首先，先要说明一个事情——其实栈的实现大多数都是利用`顺序表`来进行实现的，但是根据算法第四版里面的实现方案，栈其实是利用链表来实现的，虽然不影响后面复杂度分析，但是底层区别首先在这里说清楚。

然而，队列的实现有着`顺序表`和`链表`两种解决方案，用`顺序表`虽然出队列也依旧是$\mathcal{O}(1)$的效率，但是随着标志位的后移，需要的空间会**线性增长**，但是如果不后移则会变成$\mathcal{O}(N)$的复杂度，所以衍生出了`循环队列`的中间方案。不过`Java`源码中，给出了一个非常巧妙的方案，它将`Queue`和`Deque`作为一个接口，让其他数据结构实现这个接口，这样无论是`链表`还是`线性表`，只要实现了这个接口，就可以作为队列来使用。

言归正传，回到这个问题，要分析多个栈实现队列，我们首先分析双栈情况，就是左右横跳，用另一个栈作为中间栈，每一次出队列先把所有的元素移动到另一个栈中再出栈，这样出栈时间复杂度$\mathcal{O}(N)$，入栈直接压入原栈，时间复杂度$\mathcal{O}(1)$，但如果我们再利用多个栈进行模拟，就可以把所有操作压缩到$\mathcal{O}(1)$的时间复杂度了。

根据算法第四版的题目描述，设定的是利用3个栈进行实现，但是这是均摊时间复杂度之后达到的$\mathcal{O}(1)$，不是真$\mathcal{O}(1)$，所以本文章又给出了第二种利用六个栈实现的方案。

## 三个栈实现双向队列(虚假的$\mathcal{O}(1)$)

主要实现`Deque`的几个方法，具体代码解释已经写到注释里面了，所以直接放代码了：

```kotlin
package ds

/*
 * 使用三个栈实现队列
 * 使得所有操作都是O(1)
 *  @Author xmmmmmovo
 *  @Version 1.0
 **/
class StackDeque<T> {
    // 左栈
    private val lst = Stack<T>()

    // 右栈
    private val rst = Stack<T>()

    // 中间栈
    private val tst = Stack<T>()

    // 表示存储的栈位置
    private var tmpIsRight = false


    fun isEmpty(): Boolean =
            lst.isEmpty() && rst.isEmpty() && tst.isEmpty()

    /**
     * 入左队列
     * */
    fun pushLeft(element: T) {
        lst.push(element)
    }

    /**
     * 入右队列
     * */
    fun pushRight(element: T) {
        rst.push(element)
    }

    /**
     * 出左队列(对应的是入右队列
     * */
    fun popLeft(): T {
        return when {
            /*
            * 这里如果左栈有值的话就说明要么左边插入值了
            * 要么右边或者中转栈转移到了左栈，无论哪种情况都是栈顶就是最左
            * 直接出栈就可以
            * */
            lst.isNotEmpty() -> lst.pop()
            /**
             * 这里先判断中转栈内容是否是存的右栈的内容
             * 判断如果是右栈的内容，再判断中转栈是否是空的
             * 如果不是就说明右栈已经转移到中转栈中了
             * 相当于移动到了左栈，所以直接弹出中转栈
             * */
            tst.isNotEmpty() && tmpIsRight -> tst.pop()
            /**
             * 这里先判断中转栈内容是否是存的右栈的内容
             * 判断如果不是右栈的内容，再判断中转栈是否是空的
             * 如果不是就说明是左栈移动到了中栈了
             * 相当于移动到了右栈，所以先弹出到左栈再弹出左栈
             * */
            tst.isNotEmpty() && !tmpIsRight -> {
                while (tst.isNotEmpty())
                    lst.push(tst.pop())
                lst.pop()
            }
            /**
             * 这里如果是中转栈是空的并且右栈不为空
             * 就直接转移到中转栈再弹出中转栈
             * */
            tst.isEmpty() && rst.isNotEmpty() -> {
                while (rst.isNotEmpty())
                    tst.push(rst.pop())
                tmpIsRight = true // 存的是右栈
                tst.pop()
            }
            /**
             * 所有栈都没有内容，自然就抛出异常
             * */
            else -> throw NoSuchElementException("Stack underflow")
        }
    }

    /**
     * 出右队列(对应的是出左队列
     * */
    fun popRight(): T {
        return when {
            rst.isNotEmpty() -> rst.pop()
            tst.isNotEmpty() && !tmpIsRight -> tst.pop()
            tst.isNotEmpty() && tmpIsRight -> {
                while (!tst.isEmpty())
                    rst.push(tst.pop())
                rst.pop()
            }
            tst.isEmpty() && lst.isNotEmpty() -> {
                while (lst.isNotEmpty())
                    tst.push(lst.pop())
                tmpIsRight = false // 存的是左栈
                tst.pop()
            }
            else -> throw NoSuchElementException("Stack underflow")
        }
    }

    val size: Int
        get() = lst.size + rst.size + tst.size

    fun asList(): List<T> {
        val list = mutableListOf<T>()
        lst.forEach {
            list.add(it)
        }
        // 如果非空那就得判断tmp里面存储的是左还是右了
        // 但是右栈一定要翻转
        tst.run {
            if (tmpIsRight) this else reversed()
        }.forEach { list.add(it) }
        rst.reversed().forEach {
            list.add(it)
        }
        return list
    }

    override fun toString(): String = asList().toString()
}
```

### 测试

```kotlin
val sq = StackDeque<String>()
sq.pushLeft("a")
sq.pushLeft("b")
sq.pushLeft("c")
sq.pushLeft("d")
sq.pushLeft("e")
println(sq.popRight())
sq.pushRight("f")
sq.pushRight("g")
sq.pushRight("h")
println(sq.asList())
```

![image-20200725134752097](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200725134752097.png)

### 分析

时间复杂度：

这里我们主要分析出队列的时间复杂度，因为入队列操作仅是一个入栈操作，时间复杂度：
$$
\mathcal{O}(1)
$$
出队列方面，因为两端出队列思想相似，所以仅分析其中一边即可。

可以看到，首先先说明一下，队列是先进先出的，所以是`右进左出`，`左进右出`，选择右进左出分析，可以看到出方向首先尝试从另一边栈进行出栈操作，如果成功就是$\mathcal{O}(1)$，如果失败就继续判断中转栈是否是右栈内容，尝试从中转栈进行出栈，成功依旧是$\mathcal{O}(1)$，当中转栈是左栈或者只有右栈不为空的时候，所需要的时间复杂度才为$\mathcal{O}(N)$，所以考虑N个元素，最差情况是便是`左进右出`情况，因为此时才会存在移栈，此时仅在第一次出队列时时间复杂度为$\mathcal{O}(N)$。所以均摊时间复杂度下，出队列操作的时间复杂度为：
$$
\mathcal{O}(N/N)\\\\
= \mathcal{O}(1)
$$
可以看到是均摊后时间复杂度才达到$\mathcal{O}(1)$，所以是虚假的$\mathcal{O}(1)$。

空间复杂度：

虽然这里用到了三个栈，但是所有需求空间加起来是等于添加的总元素的，所以空间是成线性增长的，所以空间复杂度是：
$$
\mathcal{O}(N)
$$

## 六个栈实现单向队列(真正的$\mathcal{O}(1)$)

因为双向会更加绕，所以这里选用单项队列进行讲解，主要方向是`右进左出`。当然，这里的思想跟上面的有些许不同，三个栈的情况是存在单次操作$\mathcal{O}(N)$的，所以在这里我们将解决这个问题。

参考博客文章：[点此跳转](https://www.cnblogs.com/ikesnowy/p/7157813.html)

根据上面的思路，我们发现了整个实现的思路就是**均摊**，作为双向队列，如果仅用三个栈的话，中间栈只能存储一个栈，所以我们无论如何都需要有一次进行单个栈所有元素转存的方案，所以无法均摊到单个操作上(如果有四个栈可能可行)，但是本次仅用作单项队列，所以对于出栈来说只是左栈需要转存，所以可以把转存操作均摊到每一个出栈操作上来。

整体思路上是在入队列的时候便使得左右两个栈尽量相等，然后在出栈的时候再进行判断。

```kotlin
/*
 * Copyright (c) 2020. xmmmmmovo
 */
package ds

/**
 * 用六个栈实现单向队列
 * @author xmmmmmovo
 * @date 2020/7/28 16:43
 * @since version-1.0
 */
class StackDequeOpt<T> {
    /**
     * 左栈
     */
    private var lst = Stack<T>()

    /**
     * 右栈
     */
    private var rst = Stack<T>()

    /**
     * 左栈替换栈 用于复制时转换
     */
    private var tlst = Stack<T>()

    /**
     * 右栈替换栈 用于复制时候入队
     */
    private var trst = Stack<T>()

    /**
     * 左翻转栈，用于保护左栈原有数据
     */
    private var lstrev = Stack<T>()

    /**
     * 用于复制过程中的出栈操作
     */
    private var hlst = Stack<T>()

    /**
     * 判断是否在复制
     */
    private var isCopying = false

    /**
     * 需要复制数量
     */
    private var needCopy = 0

    /**
     * 队列是否为空
     * @author xmmmmmovo
     * @date 2020/7/29 16:54
     * @return 返回是否为空
     * @since version-1.0
     */
    fun isEmpty(): Boolean =
        lst.isEmpty() && rst.isEmpty() && tlst.isEmpty() && trst.isEmpty() && lstrev.isEmpty()


    /**
     * 入右队列
     * @author xmmmmmovo
     * @date 2020/7/29 16:55
     * @param element 入元素
     * @since version-1.0
     */
    fun pushRight(element: T) {
        when {
            /**
             * 左栈大于右栈
             */
            !isCopying && sizeDiff > 0 -> {
                needCopy = 0
                rst.push(element)
            }
            /**
             * 左右栈相等的时候，因为不知道下一步操作
             * 所以提前准备来进行复制操作
             */
            !isCopying && sizeDiff == 0 -> {
                rst.push(element)
                isCopying = true
                hlst = lst.clone()
                oneStep()
                oneStep()
            }
            /**
             * 如果还在复制直接 入栈到中转栈
             * 因为原栈需要别的用处
             */
            isCopying -> {
                tlst.push(element)
                oneStep()
                oneStep()
            }
        }
    }


    /**
     * 出左队列
     * @author xmmmmmovo
     * @date 2020/7/29 16:55
     * @return 返回队列第一个元素
     * @throws NoSuchElementException 没有元素时抛出
     * @since version-1.0
     */
    fun popLeft(): T {
        when {
            /**
             * 如果没有在copy的时候并且左大于右则直接左栈弹出
             */
            !isCopying && sizeDiff > 0 -> {
                return lst.pop()
            }
            /**
             * 如果没有在复制并且左栈刚好等于右栈，那么就直接弹出左栈
             * 这样左栈小于右栈，进入复制状态
             */
            !isCopying && sizeDiff == 0 -> {
                val t = lst.pop()
                hlst = lst.clone()
                isCopying = true
                oneStep()
                oneStep()
                return t
            }
            /**
             * 因为复制状态下，所有左栈元素会到hlst中所以直接hlst出栈
             */
            else -> {
                val t = hlst.pop()
                needCopy--
                oneStep()
                oneStep()
                return t
            }
        }
    }

    /**
     * 预览元素
     * @author xmmmmmovo
     * @date 2020/7/29 16:56
     * @return 返回队列第一个元素
     * @throws NoSuchElementException 没有元素时抛出
     * @since version-1.0
     */
    fun peekLeft(): T = if (isCopying) hlst.peek() else lst.peek()

    /**
     * 中间操作 这里是脱离了入栈出栈操作的额外操作
     * @author xmmmmmovo
     * @date 2020/7/29 20:32
     * @since version-1.0
     */
    private fun oneStep() {
        when {
            /**
             * 正在copy的时候左右栈都不是空的，这说明需要进行交换了
             * 本次这里右栈进入左栈中转栈
             * 左栈进入左栈反转栈(用于后面直接替换
             */
            isCopying && lst.isNotEmpty() && rst.isNotEmpty() -> {
                needCopy++
                tlst.push(rst.pop())
                lstrev.push(lst.pop())
            }
            /**
             * 此状态说明此时左栈已经完成转移，右栈还有剩余
             * 把右栈的元素移动到左栈中转栈中
             */
            isCopying && lst.isEmpty() && rst.isNotEmpty() -> {
                isCopying = true
                tlst.push(rst.pop())
            }
            /**
             * 此时说明左右栈都是空栈了
             * 但是需要复制的数量大于1
             * 就说明lstrev还有剩余可以转移的元素
             * 直接转移到左中转栈用于后面计算
             */
            isCopying && lst.isEmpty() && rst.isEmpty() && needCopy > 1 -> {
                isCopying = true
                needCopy--
                tlst.push(lstrev.pop())
            }
            /**
             * 如果左右栈都为空， 并且仅有一个需要复制的
             * 那么就直接把最后一个元素并入左栈中转栈
             * 中转栈转为主栈 就完成了一个循环
             */
            isCopying && lst.isEmpty() && rst.isEmpty() && needCopy == 1 -> {
                isCopying = false
                needCopy--
                tlst.push(lstrev.pop())
                lst = tlst
                rst = trst
                tlst = Stack()
                trst = Stack()
                lstrev = Stack()
                hlst = Stack()
            }
            /**
             * 同上
             */
            isCopying && lst.isEmpty() && rst.isEmpty() && needCopy == 0 -> {
                isCopying = false
                lst = tlst
                rst = trst
                tlst = Stack()
                trst = Stack()
                lstrev = Stack()
                hlst = Stack()
            }
        }
    }

    /**
     * 左栈-右栈大小的差值
     * @author xmmmmmovo
     * @date 2020/7/29 20:33
     * @since version-1.0
     */
    private val sizeDiff: Int
        get() = lst.size - rst.size

    /**
     * 队列总长度
     * @author xmmmmmovo
     * @date 2020/7/29 20:33
     * @since version-1.0
     */
    val size: Int
        get() = lst.size + rst.size + tlst.size + trst.size + lstrev.size
}
```

### 测试

```kotlin
/*
 * Copyright (c) 2020. xmmmmmovo
 */

package fundamental

import ds.StackDequeOpt
import org.junit.jupiter.api.*

import org.junit.jupiter.api.Assertions.*
import org.junit.platform.commons.logging.LoggerFactory

internal class StackDequeOptTest {
    private val sdo = StackDequeOpt<Int>()

    companion object {
        private val log = LoggerFactory.getLogger(StackDequeOptTest::class.java)

        @BeforeAll
        @JvmStatic
        fun before() {
            log.info { "StackDequeOptTest start" }
        }

        @AfterAll
        @JvmStatic
        fun after() {
            log.info { "StackDequeOptTest end" }
        }
    }

    @Test
    fun isEmpty() {
        assertEquals(true, sdo.isEmpty())
        sdo.pushRight(1)
        assertEquals(false, sdo.isEmpty())
        sdo.popLeft()
        assertEquals(true, sdo.isEmpty())
    }

    @Test
    fun pushRight() {
        sdo.pushRight(1)
        sdo.pushRight(2)
        sdo.pushRight(3)
        assertEquals(3, sdo.popLeft())
        assertEquals(2, sdo.popLeft())
        assertEquals(1, sdo.popLeft())
    }

    @Test
    fun peekLeft() {
        sdo.pushRight(1)
        sdo.pushRight(2)
        sdo.pushRight(3)
        assertEquals(3, sdo.peekLeft())
        sdo.popLeft()
        assertEquals(2, sdo.peekLeft())
    }

    @Test
    fun getSize() {
        assertEquals(0, sdo.size)
        sdo.pushRight(1)
        assertEquals(1, sdo.size)
        sdo.popLeft()
        assertEquals(0, sdo.size)
        sdo.pushRight(1)
        sdo.pushRight(2)
        sdo.pushRight(3)
        assertEquals(3, sdo.size)
    }
}
```

![](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/20200730001450.png)

### 分析

时间复杂度：

这里所有复杂度都均摊到了每一个操作上，不会出现某些情况时间复杂度激升的情况，综合时间复杂度：
$$
\mathcal{O}(1)
$$
空间复杂度：
$$
\mathcal{O}(N)
$$

## 总结

关于这个题目也是众说纷纭，有的人说作者已经将题目改成了有限个栈而非三个栈，但是官方网站上却标注着使用三个栈实现，然而因为疫情原因，纸质书依旧在学校里躺着，没法证明，但就从电子版来看，作者有很大可能也没有改题。其实这个题目在`stackoverflow`上面也有人询问([链接](https://stackoverflow.com/questions/5538192/how-to-implement-a-queue-with-three-stacks))，但是大多数人都暗示了使用三个栈是不可能存在真正的$\mathcal{O}(1)$的，当然也有一些抖机灵的解法——比如某些`套娃栈`的邪道解法，真的是天马行空。不管怎么说，对于一道存在这么个争议的题目，也就仅是能到这里了。

## Github

[Github](https://github.com/xmmmmmovo/Algorithms4thEditionKotlinSolutions)

算法(第四版)笔记(6)---如何利用六个栈使队列所有操作时间复杂度达到O(1)

如何解决hexo中mathjax公式不换行

## 问题

在`hexo`中写公式一般是用`LaTex`写然后利用`Mathjax`进行翻译来显示，但是当编写多行公式的时候，比如下面的公式的时候

![image-20200723115858343](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics//image-20200723115858343.png)

本来应该渲染出来如下效果

![image-20200723141719914](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics//image-20200723141719914.png)

然而实际渲染出来确实下面这个样子：

![image-20200723115846661](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics//image-20200723115846661.png)

很让人头大，经过多方面排查，最终发现了问题的根源。

## 解决

查看编译过后的html文件发现，其中的`\\`都被转义成了`\`，这样是无法利用`mathjax`进行显示换行的。

![image-20200723142052704](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics//image-20200723142052704.png)

所以我们现在要做的很简单，便是把`\\`转义掉，不让它再被编译即可。

![image-20200723142327914](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics//image-20200723142327914.png)

可以看到已经被成功转义

![image-20200723142423810](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics//image-20200723142423810.png)

现在公式已经会正常显示了

![image-20200723142544542](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics//image-20200723142544542.png)

解决mathjax公式不换行问题

本文是从物联网工程与技术实践期末文档中抽取出来的，可能格式比较奇怪。

## GithubAction

官网的第一段，便讲明了此功能的用途和作用。

> 在 GitHub 操作 的仓库中自动化、自定义和执行软件开发工作流程。 您可以发现、创建和共享操作以执行您喜欢的任何作业（包括 CI/CD），并将操作合并到完全自定义的工作流程中。

看上去云里雾里，其实就是利用yml进行的自定义脚本操作，用于测试/部署的时候的一些列繁琐重复工作实现全流水线自动化作业的功能。

## GithubPage

> 您可以为自己、您的组织或项目设置一个基本 GitHub Pages 站点。

白嫖Github服务器用来部署自己的web应用。部署后链接格式：`<用户名>.github.io/<仓库名>`

## 开始编写

### 生成密钥

```shell
cd ~/.ssh
ssh-keygen -t rsa -b 4096 -C "$(git config user.email)" -f gh-pages -N ""
```

![图2.13 成功生成密钥](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200724215856700.png)

此时会生成.pub的公钥与没有后缀的私钥：

![图2.14 成功生成密钥](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200721154822499.png)

此时再将公钥私钥部署到GitHub：

![image-20200721163516689](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200721163516689.png)

![图2.15 GitHub部署公钥](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/clip_image002.jpg)

![image-20200721163738918](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200721163738918.png)

![图2.16 GitHub部署私钥](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/clip_image004.jpg)

### 编写deploy.yml文件

首先先在仓库根目录新建`.github/workflows`文件夹，然后在此文件夹下新建`deploy.yml`文件

然后编写此文件：

```yaml
name: Deployment
on:
  push:
    branches:
      - master
jobs:
  deploy:
    runs-on: ubuntu-latest
    strategy:
      matrix:
        node-version: [12.x]
    steps:
    - uses: actions/checkout@v1
    - name: Use Node.js ${{ matrix.node-version }}
      uses: actions/setup-node@v1
      with:
        node-version: ${{ matrix.node-version }}
    - name: Install Packages
      run: npm install
    - name: Build page
      run: npm run build
    - name: Deploy to gh-pages
      uses: peaceiris/actions-gh-pages@v3
      with:
        deploy_key: ${{ secrets.ACTIONS_DEPLOY_KEY }}
        publish_dir: ./build
```

此时自动化流程部署已完成，每次commit便会自动部署到GitHub服务器中。

![图2.17 GitHub部署流程](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/clip_image001.png)

![图2.18 自动化部署](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/clip_image003.jpg)

### 添加依赖缓存

上面的流程如果仔细查看的话，会发现一个问题——每一次commit都会进行一次`Install Package`的操作，这样不仅浪费了性能，还极大的浪费了时间，每一次都会浪费平均50s左右的时间进行依赖下载，占用了我们的开发时间，所以我在这里对于`node_modules`做了缓存操作，最终`deploy.yml`文件如下：

```yaml
name: Deployment
on:
  push:
    branches:
      - master
jobs:
  deploy:
    runs-on: ubuntu-latest
    strategy:
      matrix:
        node-version: [12.x]
    steps:
    - uses: actions/checkout@v1
    - name: Use Node.js ${{ matrix.node-version }}
      uses: actions/setup-node@v1
      with:
        node-version: ${{ matrix.node-version }}
    - name: Cache node modules
      uses: actions/cache@v1
      with:
        path: node_modules
        key: ${{ runner.os }}-node-${{ hashFiles('**/package-lock.json') }}
        restore-keys: |
          ${{ runner.OS }}-build-${{ env.cache-name }}-
          ${{ runner.OS }}-build-
          ${{ runner.OS }}-
    - name: Install Packages
      run: npm install
    - name: Build page
      run: npm run build
    - name: Deploy to gh-pages
      uses: peaceiris/actions-gh-pages@v3
      with:
        deploy_key: ${{ secrets.ACTIONS_DEPLOY_KEY }}
        publish_dir: ./build
```

测试一下：

![图2.19 未加缓存](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200721160457703.png)

![图2.20 添加缓存](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200721160518125.png)

可以看到下载依赖的时间从42s变为了9s，可以说是质的飞跃了~

### 成果

[部署成果查看](http://2017iotrepo.github.io/IOTBP/)

[Github仓库](https://github.com/xmmmmmovo/IOTBP)

如何利用GitHubAction和GithubPage部署React应用

&nbsp;&nbsp;&nbsp;&nbsp;今天点开了许久未打开的GitHub，还没来得及点进动态查看大佬们star的项目之前，自己便先被一则消息吸引了，本着太长不看的原则，还未仔细查看便条件反射般的点了`Got it`的圆角矩形按钮。之后我的视线便顺着气泡凸起指向的位置寻去，发现了一枚雪花形状新徽章出现在了自己`Profile -> Highlights`上，让那枚`Pro`徽章显得不那么孤单。查看了一下详细信息后，阿这，这不是半年前在油管看到过的**GitHub北极代码库**计划吗？！

![image-20200718231856879](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200718231856879.png)



&nbsp;&nbsp;&nbsp;&nbsp;当时因为新冠的原因宅在家里实在是太闲了，甚至无聊到了在油管搜索GitHub.......

&nbsp;&nbsp;&nbsp;&nbsp;然后就看到了下面的这个视频👇(Youtube视频，显示可能需要某些手段)

<iframe width="890" height="500" src="https://www.youtube.com/embed/fzI9FNjXQ0o" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

&nbsp;&nbsp;&nbsp;&nbsp;大致讲的就是把代码存一份到北极去留作备份，用以后来信息断层的人们考古用，用以最容易理解的符号表示解密方案（怎么越听越像自举），然后根据解密方案查找信息。wow，awesome！竟然这么快就上线了，不愧是微软时代的GitHub，有钱就是效率高啊。

&nbsp;&nbsp;&nbsp;&nbsp;虽然没有被采用，但是我最感兴趣的还是其中提到的存储介质——**磁带**。

&nbsp;&nbsp;&nbsp;&nbsp;说到磁带，应该可以说是很多人的“ 童年 ”了，每天晚上洗脚的时候，每天早晨吃饭的时候，本应该在愉快的动画中度过的时间，被硬生生的安排成英语听力时间，每天听着机械一般的无感情的单词朗读和强挤出来的好似使出了自己毕生实力的浮夸演技对话仅是为了那用于糊弄老师的好似无上的圣旨一般的家长签字。有过类似经历的hxd们估计已经时会心一笑了，然而随着时代发展，磁带这一承载着童年回忆的物件如今却基本上在生活消费市场上销声匿迹了，现代课本也已经基本上全面使用光盘作为附载信息的存储介质了。然而，磁带作为一种经历了半个多世纪的存储介质，却从未消亡，沦为收藏家的玩物，反而在更加高精尖的研究机构/企业存储中继续发光发热。

&nbsp;&nbsp;&nbsp;&nbsp;上面的言论并非胡思乱想的民科行为，而是实打实的存在有公开数据的：

![image-20200719125239292](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200719125239292.png)

[**中国科学院遥感与数字地球研究所LTO磁带采购公告👆**](http://www.radi.cas.cn/gdxx/tzgg/201805/t20180521_5013864.html)

![image-20200719125412481](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200719125412481.png)

[**基因组研究所海量磁带库备份系统正式投入运行👆**](http://big.ac.cn/xwzx/kyjz/201501/t20150128_4306330.html)

&nbsp;&nbsp;&nbsp;&nbsp;可以看到，甚至在中国科学院内部，磁带依旧是很重要的存储介质，不仅在国内，国外各大研究机构也是磁带的“大客户”：

[**国际评价中子核数据库**](https://www.osti.gov/etdeweb/servlets/purl/20315863)中便多次提到磁带，并且明确提出离线检索中包含磁带数据，可以说，磁带只不过换了一种新的方式存在，并且发展的更加茁壮。

&nbsp;&nbsp;&nbsp;&nbsp;讲到这里，肯定很多人都会有着大大的疑惑——为什么这些研究机构不使用更加“现代”的存储工具呢？咱们接着往下看。

&nbsp;&nbsp;&nbsp;&nbsp;猛然提到研究机构有点让人不知所措，不如我们先从一些旧照片中找寻一下线索：

![img](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/1960s-woman-data-entry-computer-b-5000-vintage-images.jpg)

![ibm 1960s | Ibm, Old computers](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/56ff99412e0fa0da59ac26059574bc1c.jpg)

![This room-sized IBM computer from the 1960s was awesome in it\'s](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/d7d48f381d510e9d588ea96121280934.jpg)

&nbsp;&nbsp;&nbsp;&nbsp;上面一组照片拍摄于上世纪60年代，可以看到当时的磁带存放并用于大型机房，由专业的操作员进行专业的操作的，没错，1952年，IBM成功发布了计算机业内的第一款磁带机，拉开了磁带发展第一时期的序幕。这一时期延续了35年，主要特征是圆轴磁带的使用，并且需要人工手动操作(装载、卸载和归档)。如果说当时使用磁带是没有选择，那么为什么现代科研机构也还是继续使用磁带呢？

&nbsp;&nbsp;&nbsp;&nbsp;别急，接着往下讲，时间跨越到千禧年往后的2002年，此时磁带跨越了第二个时代——近现时代，此时磁带已经不需要那种大型磁带驱动器，不专用于主机，这让便携和低成本产品得以于平民消费市场面世，自然，廉价的存储介质和便于携带的特性很快便掀起了一股风潮......同年，磁带的容量首次超过了最大磁盘的容量，过去，一个磁盘所能容纳的信息量往往需要多盒磁带才能装得下；但是现在情况完全反过来，一盒磁带就可以容纳多个磁盘的数据。磁盘的失败从此便可见一斑。

![随身携带的磁带播放器](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/49-131215-9-4.jpg)

&nbsp;&nbsp;&nbsp;&nbsp;后面的事情大家也都经历了，计算机硬盘/软盘的出现，改变了家用电脑的存储境况，单位体积的容量大大提升，全面改善了用户体验，这使得家用电脑短暂的磁带存储介质的时代极其短暂。

![苹果Ⅱ 使用磁带作为存储媒介](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/v2-afaea03afc6c7d936cf24933f9081a87_r.jpg)

![苹果Ⅱ 使用磁带作为存储媒介](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/v2-a05960f41b5058867fc363c6b737c993_r.jpg)

![雅达利5200](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/v2-b8f4941449f99d7e6cff36972e5eabd2_r.jpg)

&nbsp;&nbsp;&nbsp;&nbsp;从这里，其实就可以看出民用设备与科研设备选用上的些许差距了，民用设备主要讲究的就是成本和便利，而科研设备主要考虑的则是稳定性和持久性。好了说了这么多，大概历史也说明了，磁带作为一种历史悠久的存储介质，甚至一直到2002年还在发展，但是其单位体积的存储容量使得其无法在民用大放异彩。总结一下，磁带价格低廉，发展没有落后，但是单位体积存储容量小。

&nbsp;&nbsp;&nbsp;&nbsp;相信已经有人分析出来结果了，在这里我引用一下**CERN**数据存储主管**Alberto Pace**的分析来说明优点

> &nbsp;&nbsp;&nbsp;&nbsp;相比硬盘，磁带储存拥有4大优势：虽然，磁带的装卸是落后的，即使在自动化装置协助下，在储存库中找出对应的磁带并装入读取装置中最快也需要40秒。但是一旦就绪后，磁带的读取速度却可以达到硬盘的4倍。 
> 
> &nbsp;&nbsp;&nbsp;&nbsp;其次是可靠性。磁带也会遇到损毁的情况，如断裂。但断裂后的磁带仍可以重新接上，而且仅会造成数百MB的损失——这对于动辄上TB的专业储存设备来说，实在小事一桩。但对硬盘来说，物理损坏甚至会导致全部数据丢失。CERN的实际数据是，他们每年储存在磁带上的100PB数据（1PB相当于1000TB），每年会损失数百MB；相对的，储存在硬盘上的50PB 数据，这个数字则达数百TB。
> 
> &nbsp;&nbsp;&nbsp;&nbsp;还有就是，对于磁带来说，突然断电也不会损坏记录下来的资料，但对于硬盘来说，这是一件危险的事情。
> ​&nbsp;&nbsp;&nbsp;&nbsp;最后也是最重要的，是磁盘一定程度上更加安全。比如说如果一间公司的数据中心被黑客劫持，他可以在数分钟内让硬盘上50PB数据从此在世上消失，但如果磁带的话，不好意思，可能需要数年。
> 
> &nbsp;&nbsp;&nbsp;&nbsp;不过，磁带储存并非只与那些每秒就碰撞出几个GB的核子对撞实验室有密切联系。调查表明，磁带储存也同样适合中小型企业。
> 
> &nbsp;&nbsp;&nbsp;&nbsp;首先，磁带储存更便宜也更持久。数据在磁带上往往能存放超过30年；硬盘超过5年的话，如果你是公司的IT主管，你就需要考虑将数据转移了。而且磁带目前仍然是储存成本最低的解决方案，目前大概每GB数据在磁带上的成本为4美分，硬盘的话则为10美分。如果考虑到前面所说的寿命问题，差距将会更大。所以，磁带在展示还并没有出现真正消亡的迹象，我们也看到了这个老一代的产品所寻求的生存潜力。

&nbsp;&nbsp;&nbsp;&nbsp;好了，讲完了一个传奇的历史，其实最让我惊奇的是一个已经淡出生活的物件竟然在另外一个领域还有这不俗的影响，磁带就如同软件语言的`C++`一样，“老” ，乃于它的历史。而技术却一直在改良。磁带和其他大部分储存媒介一样，磁带的储存密度也一直在攀升（遵循摩尔定律）。其实这种想当然的事情并不少见，比如常年混迹手机圈子的人，总会说一句：

> 索尼要凉

&nbsp;&nbsp;&nbsp;&nbsp;但其实呢，索尼靠着全世界的音乐版权，hi-res，PS系列，相机，电视······如此之多的产业早就让索尼赚的盆满钵满，说不准手机产业就是拿来试水的，到时候，公开宣布退出的时候，大抵又会有人说道：

> 索尼果然凉了

&nbsp;&nbsp;&nbsp;&nbsp;当然，这其实很正常，因为人类就是这样的生物，在**丹尼尔 · 卡尼曼**所著的**《思考，快与慢》**第五章中便描述了这种现象，下面我提出一个问题，再做出分析：

> 现在我公司有大量的重要数据集静态资源需要长时间稳定使用，仅是用于读取，请问我选取存储介质的时候是选用SSD还是HDD呢？

请作答。

。

。

。

&nbsp;&nbsp;&nbsp;&nbsp;hummmmm，相信有人很快选了HDD了，因为长时间稳定存储还是大量的存储，听说过SSD损耗的估计都早早排除了SSD这个选项了。事实上呢，这里应该选用SSD，因为仅是用于读取，而SSD的读取是不会有损耗的，仅是写入会有损耗（这里可以去看一下SSD原理就明白了），所以这里建议选取快速的SSD更佳。

&nbsp;&nbsp;&nbsp;&nbsp;当然，你可能会说：“这SSD读取不损耗我也不知道啊”，那你为什么不去百度呢？其实这里是你的“系统1”——经验系统在作怪，你想当然的把你已知的信息带入了当前环境中来，导致你不能存在客观的逻辑判断。

&nbsp;&nbsp;&nbsp;&nbsp;下面是原书中的形容：

![a](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200719194910451.png)

![b](https://cdn.jsdelivr.net/gh/xmmmmmovo/ResourcesBackup/blog/pics/image-20200719194943595.png)

&nbsp;&nbsp;&nbsp;&nbsp;几乎可以说，我们大多数时间都不能离开这个系统，它能帮助我们做出大量的简单的判断，比如闹铃响了需要关闹铃，手机没电了需要充电，这些都是由你的“系统1”来做出判断，但当你被这个系统牵着鼻子走，很少觉得自己会有“系统2”判断的时候，便是你需要警觉的时候，因为，我们独立思考的人格，才是我们作为一个活在这个多面的世界中的最好体现。

&nbsp;&nbsp;&nbsp;&nbsp;这便是小弟的一点点延展思考，仅代表自己的观点，欢迎反驳，但是不喜勿喷，和平讨论。