[TIL] Stack & Queue


Stack


データ構造

袋小路を考えなさい.
一番早く入った車は後ろの車が出るまで動かない.
止まらなければなりません.
逆に、最後に入った車は一番先に出ることができます.
これらのスタックのデータ構造ポリシーは、「最初の最初の出力」または「最初の最初の出力」とも呼ばれます.

スタックインプリメンテーション(追加2021.04.21日)

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0;
  }

  size() {
    return this.top;
  }

  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
	
	
  pop() {
    if (this.size()<=0) {//사이즈0이어도 오류없이 리턴!
      return;
    }

    const result = this.storage[this.top-1];
    delete this.storage[this.top-1];
    //storage의 저장 인덱스는 0부터 시작하지만
 	//top은 바로 1부터 추가되어서 this.top-1을 해줘야 위치를
    //잡아서 값을 빼줄수 있다.
    
    //항상 끝부터 빠져야함 중간값을 뺄 수는 없음.
    this.top= this.top-1;
    
    return result;
  }
}

let stack = new Stack();
スタックは、Webページの「前へ」ボタンと「後ろへ」ボタンを実現します.
or(let i=0; i<actions.length; i++){
    //if(prev.length===0 && next.length===0 && actions[i]){
    //  return [];
    //}
    if(actions[i]===-1 && prev.length !==0 ){
      //뒤로 가기 버튼을 누를 경우 원래 있던 페이지를 next 스택에 넣고, prev 스택의 top에 있는 페이지로 이동한 뒤 prev 스택의 값을 pop 합니다.
      next.push(prevPage);
      prevPage=prev.pop();
      //next.push(prev.pop());
      //prev.pop();
    }
    else if(actions[i]===1 && next.length !==0){
      //앞으로 가기 버튼을 누를 경우 원래 있던 페이지를 prev 스택에 넣고/ next 스택의 top에 있는 페이지로 이동한 뒤/ next 스택의 값을 pop 합니다. 
      prev.push(prevPage);
      prevPage=next.pop(); 
    }
    else{
      prev.push(prevPage);
      prevPage=actions[i];
      next=[];
    }
  }
prevPageは現在のページで、実際のページとは異なり、
2つのスタックを使用して、前のページを格納するデータ構造を1つ使用します.
もう1つは、データ構造を使用して後続のページを表示することです.

Queue


「スタック」とは反対の概念は、「最初のデータ」または「最初のデータ」の特徴を持つデータ構造です.

Qの一番いい例は料金所です.
料金所を想像してみてください.後ろがどれだけ混んでいても、最終的に出力値は1台1台です.
キューの特徴は,入力データの順序で処理することである.
Queueは、コンピュータデバイス間でデータを交換する際に、各デバイス間の速度差や時間差を克服するための一時メモリとして使用される.
これを総称してバッファ(buffer)と呼ぶ.
私たちがよく使うバッファもこの概念です.
YouTubeを見ているときのバッファリングも、ダウンロードした資料(データ)が動画を再生するのに足りない場合は順番にキューに入れ、動画量が十分な場合は再生を再開します.
通常、プリンタの速度が遅く、CPUの速度が比較的速いため、CPUは印刷材料(データ)を比較的速い速度で作成し、印刷ジョブキューに保存して他の操作を実行します.プリンタは、印刷ジョブキューからデータを取得し、一定の速度で印刷します.

キュー実装(追加2021.04.21)

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 += 1;
  }
    
    // 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
  dequeue() {
    // 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.size()<=0) {
      return;
    }const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;
    if(Object.keys(this.storage).length===0){
      this.front=0
      this.rear=0
    }
    //객체에 아무것도 안담겨있다면 위치값을 초기화(초기상태랑같게)
    return result;
  }
}
let queue = new Queue();