データ構造シリーズ:スタックとキュー

導入

フォークを使ってパスタを食べたり、スプーンにスープを食べたり、箸を食べたりします.各々のsilverwaresはその利点/欠点を持っています、したがって、それがそれがよく相互作用する食物のためにもう一方よりよく働きます.そのように、別のデータ構造は、より適しており、状況/ユースケースに基づいて他よりも良い実行します.彼らはそれぞれ賛否両論を持っている.それはあなたが状況/目標に基づいて適切なデータ構造を選択できるようになるように、これらの長所と短所を理解することは、より良いプログラマに役立つことができます、それは大幅に適用されているアルゴリズムのパフォーマンスを向上させるのに役立ちます.あなたが質問をするならば、コメントを残してください!

目次

1 .What are Stacks and Queues?
2 .Implementation in JavaScript
3 .Implementation Using Linked List
4 .Big O
5 .Helpful Resources

スタックとキューは何ですか？

Stacks and Queues are two types of linear data structures with a main difference in their data management principle: LIFO (Last-In, First-Out) for Stacks, and FIFO (First-In, First-Out) for Queues.

スタック

スタックは、LIPO(最後のin、First Out)の原則に続く線形データ構造です.LIFOの原理では、データが最後に来たものは何でも最初に取り出されるでしょう.あなたがよく知られる例は、ワープロのようなテキストエディタの元に戻す機能です.Word文書では、アンドゥコマンドは、最後のアクションを元に戻すには、テキストの書式設定、ブロックの移動、テキストの入力、削除、書式設定、およびundoコマンドを使用します.

私はこのプラスチック製のおもちゃで“ロック-スタック”という名前の遊びをしていたことを覚えています.このおもちゃは、上に中心の円錐と異なるサイズで複数のカラフルなプラスチック・リングでベースとともに来ます.あなたの目標は、ピラミッドの形を形成するために最小から最大のサイズの順序でベースの上にリングをスタックすることです.リングはベースのために底から取り出すことができません、あなたが順序を再配置するために、スタックの一番上の位置にリングが何であるかについて取り出す必要があります.プログラミング世界のスタックは、基本的には、おもちゃのロック-スタックとは異なりません.

キュー

キューはまた線形データ構造であるが、FIFO(first in first first)原理に従う.FIFO原理で、最初にデータが何であったかは、取り出される最初であるでしょう.プリンタキューはキューデータ構造の良い例です.1つまたは複数のプリンタが複数の人々によって共有されるオフィス設定では、キューは、印刷タスクがそれらが入った年代順に実行されることを確認します.あなたが自宅でプリンタを使用して、ドキュメントページの複数のインスタンスを印刷する場合でも、それはキュー内のタスクをプッシュします.あなたがプリンタをオンにするのを忘れたと言いましょう、キューは印刷タスクが失われないことを確認します、しかし、最初に印刷タスクが最初に実行されるように、各々の仕事を待ち行列として実行します.

実際の生活の例は、TSAのセキュリティスキャンライン、または遊園地、レストランなどのような他の行のようになります.誰かがラインを切断するときは誰もそれを好む.番がくるまで待たなければならない.あなたがTSAラインに到着する最初のものであるならば、あなたは最初にセキュリティスキャンを通過します.これは、最初に、最初のアウトキューです.
要約では、スタックとキューは、データ管理原理の主な違いを持つ2つのタイプの線形データ構造です.

arrayの使用

Stacks and Queues can simply be implemented using a built in Array in JavaScript. For Stacks, you just need to use Array's push() and pop() methods to add and element at the end of an array, and remove the element at the end. For Queues, you will have to use push() method to add an element at the end, but use shift() to take out the first element that was pushed in. They will look something like this:

スタック

const stack = [];
stack.push('Baseball')
stack.push('Soccer')
stack.push('Football')
stack.push('Basketball')

return stack // ["Baseball", "Soccer", "Football", "Basketball"]

stack.pop() // returns "Basketball"

return stack // ["Baseball", "Soccer", "Football"]

キュー

const queue= [];
queue.push('Peanut Butter')
queue.push('Milk')
queue.push('Apple')
queue.push('Cheese')

return queue // ["Peanut Butter", "Milk", "Apple", "Cheese"]

queue.shift() // returns "Peanut Butter"

return queue // ["Milk", "Apple", "Cheese"]

これは完全に簡単で便利なスタックです.しかし、配列を使用してキューを実装する欠点があります.あなたはそれが何か推測できますか?push() and pop() 方法はo ( 1 )の時間複雑さを持ちますshift() and unshift() 方法はo(n)の時間複雑性を有する.これは、配列の要素を追加または削除するときに、その要素の右側にあるすべての要素が位置を並べ替える必要があるためです.
以来shift() and unshift() 配列でかなり高価です、スタックとキューを最適化する方法があるかどうか見ましょう.アハ!リンクリストは、最初と最後の要素を挿入/削除に最適です!リンクされたリストがどのように機能するかを覚えているなら、リンクされたリストはシーケンスのデータのコレクションですhead にtail . スタックとキューを使用して、それをよりよく視覚化するために、我々はポインタを呼びますfirst and last の代わりにhead and tail .
シンボリックリンクリストのノードは次のノードを参照しますが、前のノードは参照しません.新しい追加first ノードは、単一のリンクリストを迅速に、我々はちょうど新しいfirst , を設定し、next 古いノードfirst ノード.現在のfirst ノードも同様に、私たちはfirst ノードを設定し、新しいノードとして次のノードを設定しますfirst ノード.これは、単一のリンクリストのスタックのための完全な候補をlifo(最後に、最初の)原則に従うことになります.しかし、新しいノードをキュー(enqueue)に追加して、最後にリンクされたリストを使って最後のノード(dequeue)を削除するなら、最後のノードをデキューするのは効率的ではありません.これは、シンボリックリンクされたリストのノードが前のノードを参照していないので、リスト全体を横断して、前のノードのlast ノードはです.前のノードlast ノードはnewとして再割り当てする必要がありますlast ノード.このように、待ち行列はシングルリンクリストの上の二重リンクリストを利用するためにより最適化される.以下のコードをチェックしてください.

連結リストを用いた実施

Stack

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}
class Stack {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    // push() method adds a new node at the top (first)
    push(value){
        let newNode = new Node(value);
        if(!this.first) {
            this.first = this.last = newNode;
        } else {
            let oldNode = this.first;
            this.first = newNode;
            this.first.next = oldNode;
        }
        return ++this.size
    }
    // pop() method removes a node at the top (first)
    pop() {
        if(!this.first) return null;
        let removedNode = this.first;
        if(this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        this.size--
        return removedNode.value
    }
}

Pseudocode for push() :

• The function should accept a value
• Create a new node with that value
• If there are no nodes in the stack, set the first and last property to be the newly created node
• If there is at least one node, create a variable that stores the current first property on the stack
• Reset the first property to be the newly created node
• Set the next property on the node to be the previously created variable
• Increment the size of the stack by 1, and return it

Pseudocode for pop() :

• If there are no nodes in the stack, return null
• Create a temporary variable to store the first property on the stack
• If there is only 1 node, set the first and last property to be null
• If there is more than one node, set the first property to be the next property on the current first
• Decrement the size by 1
• Return the value of the node removed

---

Queue

class Queue {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    // enqueue() method adds a new node at the end (last)
    enqueue(value) {
        let newNode = new Node(value);
        if(!this.first) {
            this.first = this.last = newNode;
        } else {
            this.last.next = newNode;
            this.last = newNode;
        }
        return ++this.size;
    }
    // dequeue() method removes a node at the beginning (first)
    dequeue() {
        if(!this.first) return null;
        let removedNode = this.first;
        if(this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        this.size--
        return removedNode.value;
    }
}

Pseudocode for enqueue() :

• This function accepts a value
• Create a new node using the value passed to the function
• If there are no nodes in the queue, set this node to be the first and last property of the queue
• Otherwise, set the next property on the current last to be that node, and then set the last property of the queue to be that node

Pseudocode for dequeue() :

• If there is no first property, just return null
• Store the first property in a variable
• See if the first is the same as the last (check if there is only 1 node). If so, set the first and last to be null
• If there is more than 1 node, set the first property to be the next property of first
• Decrement the size by 1
• Return the value of the node dequeued

---

A bit more hassle to implement than just using Array, but this will make the data structure more optimized. I definitely recommend you to go check out the I wrote on Linked List to learn about it if you need a refresher or have a problem comprehending the code above.

---

ビッグ・オー

空間の複雑さ

o ( n )

このデータ構造の空間的複雑さは線形であり、リストのサイズが大きくなるので、スペースが増える

push/popとenqueue/dequeue :

o ( 1 )時間の複雑さ

我々が配列の上でリンクリストを利用することになっていたなら、プッシュ/ポップとenqueue/dequeueの時間複雑さの両方をo(1)に最適化することができます.さらに、リンクリストはスタックやキューを実装するための唯一の最適化された方法ではありません.たとえば、オブジェクトをストレージとして使用するクラスを作成できます.Here's あなたが興味を持っているならば、この実装のビデオは、あなたが見ることができるように、スタック/待ち行列をつくる多くの方法があります.

参考になるリソース

Online Course (udemyコース)
JavaScriptアルゴリズムとデータ構造MasterClassという名前のこのUDEMYコースをチェック!これは作成され、私はこのブログ記事のデータ構造の実装部分のための彼のコードを参照します.個人的には、私はどこからアルゴリズムやデータ構造、特に非技術的な背景から来て知っていない.このコースは非常によく初心者のためのこれらのトピックの基礎を構築するために構築されます.
Visual Animation ビジュアルゴ
データ構造は、コード/テキストを見るだけで、一部の人々のために理解するのが難しいかもしれません.上記のインストラクターは、Visualgoという名前のウェブサイトを使用して、アニメーションを通してアルゴリズムやデータ構造を視覚的に表現しています.
Data Structure Cheat Sheet (インタビューケーキ)
また、ここでは本当によく整理されたカンニングペーパー/データ構造の可視化です.