😽

データ構造④　スタック・キュー(Stacks, Queues)

2024/03/18に公開

アルゴリズムとデータ構造

スタック・キューとは

スタックとは、Last in, First Out(LIFO)の原則に基づいて、最後に追加された要素が最初に取り出されるようなデータ構造のことである。積み重ねたお皿をイメージするとわかりやすい。最初に積んだ皿は最後に取り出され、最後に積んだ皿は最初に取り出される。

const myStack = new Stack();

// LIFO
myStack.push('tomato');
myStack.push('banana');
myStack.push('orange');
myStack.pop(); // 'orange'

キューは、First in, First Out(FIFO)の原則に基づいて、最初に追加された要素が最初に取り出されるようなデータ構造のことである。ジェットコースターなどの列を想像するとわかりやすく、最初に並んだ人がジェットコースターに乗れる。キューもこれと同様である。

const myQueue = new Queue();

// FIFO
myQueue.enqueue('tomato');
myQueue.enqueue('banana');
myQueue.enqueue('orange');
myQueue.dequeue(); // 'tomato'

実装

スタックの実装

配列を用いて実装する方法と連結リストを用いて実装する方法を記述する。

配列を用いての実装

class Stack {
    // 初期化
    constructor() {
        this.array = [];
    }

    // 先頭のデータ取得
    peek() {
        return this.array[0];
    }

    // データ追加
    push(value) {
        this.array.push(value);
    }

    // データ削除・取得
    pop(value) {
        return this.array.pop();
    }
}

連結リストを用いての実装

class Node{
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class Stack {
    // 初期化
    constructor(){
        this.top = null;
        this.bottom = null;
        this.length = 0;
    }

    // 先頭のデータ取得
    peek() {
        return this.top;
    }

    // データ追加
    push (value) {
        const newNode = new Node(value);

        if (!this.top) {
            this.top = newNode;
            this.bottom = newNode;
        } else {
            newNode.next = this.top;
            this.top = newNode;
        }
        this.length++;
        return this;
    }

    // データ削除・取得
    pop () {
        if (!this.top) {
            return null;
        }
        if (this.top === this.bottom) {
            this.bottom = null;
        }
        const wantedNode = this.top;

        this.top = this.top.next;
        this.length--;
        return wantedNode;
    }

    // 空かを判定
    isEmpty () {
        if (!this.top){
            return false
        } else {
            return true
        }
    }
}

キューの実装

連結リストを用いた実装方法を記述する。
配列での実装を行うと、popするたびに配列の先頭の要素がなくなるため、要素のシフトを行う必要があり非効率である。

class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}

class Queue {
    // 初期化
    constructor(value) {
        this.first = null;
        this.last = null;
        this.length = 0;
    }

    // データ追加
    enqueue(value) {
        const newNode = new Node(value);

        if(!this.first) {
            this.first = newNode;
            this.last = newNode;
        } else {
            this.last.next = newNode;
            this.last = newNode;
        }

        this.length++;
        return this;
    }

    // データ削除・取得
    dequeue(value) {
        if(!this.first) {
            return null;
        }
        if(this.first === this.last) {
            this.last == null;
        }
        const wantedNode = this.first;
        this.first = this.first.next;
        this.length--;
        return wantedNode;
    }

    // 空かを判定
    isEmpty() {
        if(!this.first) {
            return false;
        } else {
            return true;
        }
    }
}

それぞれの操作の計算量

スタックにおける計算量

それぞれの操作の計算量は以下。
特定のデータを探し出すことなどは苦手とするが、popやpushなどの操作は高速に行うことができる。
また、順序づけが可能な点も強みである。

操作	計算量
lookup	O(n)
pop	O(1)
push	O(1)
peek	O(1)

キューにおける計算量

それぞれの操作の計算量は以下。
特徴はスタックと同様であり、順序づけの順番がFIFOである点がスタックと異なる点。

操作	計算量
lookup	O(n)
enqueue	O(n)
dequeue	O(n)
peek	O(1)

参考webサイト

このUdemyの講座を参考にしています。