100日アルゴリズム[15日目・スタックとキュー]

スタックとキューとは

スタックとキューは特別なデータ構造ではなく、データの扱う順番をどうするかを決めたものです。
スタックは「データの要素を順番に入れていき、データを取り出す順番は最後から取り出すもの」です。一方キューは、「データの要素を順番に入れていき、データを取り出す順番は最初から取り出すもの」です。

コンビニを例で考えると分かりやすいです。コンビニにはタバコのケースがありますよね。あのケースはどんどん新しいタバコがケースの一番手前に来るようになっています。そういう意味では古いタバコは最初に納品されるが、取り出されるのは新しいタバコから取り出されるということでスタックのような扱われ方です。一方でコンビニのお弁当。お弁当は当然毎日納品されるので、自然と賞味期限が古いものから順番に納品されます。しかしコンビニ側は賞味期限が切れる前にお弁当を売りたいので賞味期限が古いお弁当は一番手前に来るように陳列されます。そういった意味でコンビニ弁当はキューのようにお弁当を順番に納品するものの、お弁当が取り出される順番は最初から順番に取り出されると言えます。

enqueueとdequeue

データの要素を配列などに"追加"するのをenqueueと言い、データの要素を配列から取り出すのをdequeueと言います。

プログラミングでのスタックとキューの違い

スタックは上から順番に取り出していきます。ですがキューは配列の先頭から取り出しても良いですし、配列の一番後ろから取り出すこともできます。これがアルゴリズムの実装での大きな違いです。

解いた問題

スタック

https://leetcode.com/problems/min-stack/

解法

以下は最初に書いたstackのコード。

class MinStack {
    private _stack: number[];
    constructor () {
        this._stack = [];
    }

    push (val: number): void {
        this._stack.push(val);
    }

    pop () {
        this._stack.splice(this._stack.length -1, 1);
    }

    top () {
        return this._stack[this._stack.length -1];
    }

    getMin () {
        let minInt:number = this._stack[0];
        for (let i = 0; i < this._stack.length; i++) {
            if (this._stack[i] < minInt) minInt = this._stack[i]
        }
        return minInt;

    }
}

getMinでfor文を使っているので、89msと他のコード提出者と比べて遅かった。あと、問題文の全ての関数の計算量がO(1)であることというルールから逸れていた。そこで改善して2回目のコードを書いた。

getMinでfor文を使うとO(n)になるので、最小値がわかりやすい構造のスタックを実装する必要がある。そこで最小値のスタックを_stackとは別に設けることにした。

class MinStack {
    private _stack: number[];
    private _minStack: number[];

    constructor () {
        this._stack = [];
        this._minStack = [];
    }

    push (val: number): void {
        this._stack.push(val);
        // NOTE: minStackのtopには最小値がくる
        if (this._minStack.length == 0||val <= this._minStack[this._minStack.length -1]) {
            this._minStack.push(val)
        }
    }

    pop () {
        let topValue = this.top()
        if (this._minStack[this._minStack.length -1] == topValue) {
            this._minStack.splice(this._minStack.length - 1, 1)
        }
        this._stack.splice(this._stack.length -1, 1);
    }

    top () {
        return this._stack[this._stack.length -1];
    }

    getMin () {
        return this._minStack[this._minStack.length -1]
    }
}

上記のアルゴリズムだと計算時間は11msにまで改善した。

上記とは違う方法だと_stackの要素をオブジェクトで設定していれば{value:~~, minValue:~}というような_stackも実装でき、_minStackは不要になる。

キュー

解いた問題
https://leetcode.com/problems/implement-queue-using-stacks/

解法

class MyQueue {
    private _queue:number[];

    constructor () {
        this._queue = []
    }

    push (x:number) :void {
        this._queue.push(x);
    }

    pop () :number {
        const frontElement = this._queue[0]
        this._queue.splice(0, 1);

        return frontElement;
    }

    peek () :number {
        return this._queue[0]
    }

    empty () :boolean {
        return this._queue.length == 0
    }

}