[data structure] Stack/Queue
資料構造とは何ですか。
データ値のセット、データ間の関係、およびデータに適用できる関数またはコマンドを事前に定義します.
すなわち、複数のデータセットは、データを格納または使用する方法を定義します.
シナリオによって方法はいろいろありますが、まずstack、queueについて知りました.
資料構造を学習する理由は,特定の状況に適した適切な資料構造を用いて,問題を解決する際に正確で最適なコードを記述できるからである.
そのため、資料構造の特徴、よく使われる状況、どのように資料構造を体現するかを重点的に学習した.
1. Stack
stackは資料を保存するための資料型で、その名の通り「資料を蓄積する構造」です.
データがタワーのように垂直に積み上げられている様子が想像できます.
スタックフィーチャー
stackは資料を保存するための資料型で、その名の通り「資料を蓄積する構造」です.
データがタワーのように垂直に積み上げられている様子が想像できます.
スタックフィーチャー
先入後出(FILO)
最後に添付した資料が先に出ます.
限られたアクセス資料
最初に保存したデータは、上のデータがすべて失われた後にアクセスする必要があります.
中間データは確認できません.
構造的特徴のため、中間データに何が含まれているかは判断できません.
アレイとしてスタックを実装する場合は、データサイズを予め指定する必要があります.これにより、ストレージスペースが無駄になる可能性があります.
構造が簡単で、実施しやすい.
データストレージ/読み取り速度が速い.
スタックの使用例
関数を再帰的に呼び出す必要がある場合は、スタックに一時的なデータを積み上げることができます.
スタック実装アルゴリズム
stackの核心は後入先出です.したがって、topというpropertyを作成し、データを追加または削除するときにデータを増減してデータのサイズを決定することができます.
class Stack {
constructor() {
this.storage: {},
this.top = 0 // 스택의 가장 상단을 가리키는 포인터 변수를 초기화
}
size() {
return this.top
}
push(element) {
this.storage[this.top] = element
this.top++
}
pop(element) {
// 빈 스택에 pop 연산을 적용해도 에러나지 않도록
if(this.top <= 0) {
return
}
const result = this.storage[this.top-1];
delete this.storage[this.top-1];
this.top -= 1;
return result;
}
}
2. Queue
Queueは、キューを意味する「資料(データ)をリストする構造」です.一端(後部)では挿入のみ、他端(前部)では削除のみを行います.
queueは、データ入力が必要な順序でデータを処理するために使用されます.
キューフィーチャー
先入先出(FIFO)
まずstackとは逆の概念が現れ,先に入った資料(データ)が現れる.
配列キューの実装には、データサイズを予め指定する必要があります.
後方が配列の最後のインデックスを指す場合、キューにスペースがあっても挿入できません.
削除時に残りのデータを前に移動しないと、スペースが無駄になります.
queue使用例
出力ボタン->キューに入る順->入る順に印刷
コンピュータとデバイスとの間に存在する速度差や時間差を克服するために、一時メモリとして用いられ、総称してバッファと呼ばれる.
バッファリング
ほとんどのコンピュータデバイスで発生するイベントは不規則であり、発行されるイベントプロセッサ(cupなど)は
一定の処理速度を有する.バッファを使用して、この2つの違いを解決できます.
もう1つの例は、ダウンロードされたコンテンツ(データ)がビデオを再生するのに不足している場合、youtubeを視聴するとバッファが順番にキューに配置され、ビデオ量が十分に大きい場合にビデオを復元して再生することである.
BFS(幅優先ナビゲーション)
処理するノードを保存する必要がある場合はqueueを使用します.
1つのノードを処理するたびに、そのノードに隣接するノードがキューに再格納されます.ノードアクセスの順序で処理できます.
キュー実装アルゴリズム
class Queue {
constructor() {
this.storage = {}
this.front = 0 //가장 앞 데이터 키
this.rear = 0 //가장 끝 데이터 키
}
size() {
return this.rear - this.front
}
enqueue(element) {
this.storage[this.rear] = element
this.rear++
}
dequeue(element) {
if(this.size() === 0) return;
let result = this.storage[this.front]
delete this.storage[this.front]
this.front++;
return result;
}
StackとQueue Arrayによる実装
従来のStackやQueue実装と同様に、classキーワードでカスタムデータ型を作成したり、Arrayで作成したりすることができます.
Arrayを使用すると、カスタムで作成する時間を短縮し、スタックやキューに似た方法が得られます.
push()とpop()
push()とshift()
Reference
この問題について([data structure] Stack/Queue), 我々は、より多くの情報をここで見つけました https://velog.io/@bining/data-structure-Stack-Queueテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol