アルゴリズム学習1週目.スタック/キュー

37981 ワード

stack


先入後出(LIFO)
データ構造

jsでのスタックメソッド


追加データ:pushデータ消去:pop

接続リストを使用したスタックの実装

class Node {
  constructor(data) {
    this.data = data;
    this.prev = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
    this.length = 0;
  }
  push(data) {
    const newNode = new Node(data);

    if (this.length === 0) {
      this.top = newNode;
    } else {
      const preNode = this.top;
      this.top = newNode;
      this.top.prev = preNode;
    }
    this.length++;
  }
  peek() {
    this.length && console.log(this.top.data);
  }
  pop() {
    if (this.length === 0) {
      console.error("stack is empty");
    } else {
      this.top = this.top.prev;
    }
    this.length--;
  }
}

const stack = new Stack();
stack.push(1);
stack.peek();
stack.push(2);
stack.peek();
stack.push(3);
stack.peek();
stack.pop();
stack.pop();
stack.pop();
stack.peek();

スタック使用率の例

  • ページで
  • に戻る
  • 取り消し
  • array.reverse()
  • かっこ検査
  • 接尾辞表現法計算
  • プロセスとスタック


    プロセス
    実行中のプログラム
    ねじ山
    プロセスの実行単位
    プロセスのメモリ領域は4つの部分に分かれています.
  • テキスト:プログラムコード
  • を格納
  • データ:グローバル変数、静的変数など
  • を格納する.
  • スタック:格納(一時データ)/可変
  • 、領域変数、パラメータ、戻り値、関数戻りアドレスを含む
  • ヒップホップ:実行時に割り当てられた領域/可変
  • プロセス内のスレッドは、コード、データ、スタック領域を共有し、スタック領域とは独立しています.
    stackにより、各スレッドは独立してストリームを実行できます.
    スレッド間のテキスト領域共有により、関数呼び出しが可能になります.
    スレッド間のデータ,ヒップ領域共有によりメモリ空間を共有し,スレッド間の通信を可能にする.

    queue


    先入後出(FIFO)
    最初に入力したデータが最初に出力されるデータ構造

    jsでのqueueメソッド


    追加データ:pushデータ消去:shift

    接続リストを使用したキューの実装

    class Node {
      constructor(data) {
        this.data = data;
        this.next = null;
      }
    }
    
    class Queue {
      constructor() {
        this.top = null;
        this.bottom = null;
        this.length = 0;
      }
      push(data) {
        const newNode = new Node(data);
    
        if (this.length === 0) {
          this.top = newNode;
          this.bottom = newNode;
        } else {
          const preNode = this.top;
          this.top = newNode;
          preNode.next = newNode;
        }
        this.length++;
      }
      peek() {
        this.length > 0 && console.log(this.top.data);
      }
      shift() {
        if (this.length === 0) {
          console.error("stack is empty");
        } else {
          this.bottom = this.bottom.next;
        }
        this.length--;
      }
    }
    
    const queue = new Queue();
    queue.push(1);
    queue.peek();
    queue.push(2);
    queue.peek();
    queue.push(3);
    queue.peek();
    queue.shift();
    queue.shift();
    queue.shift();
    queue.shift();
    queue.peek();
    

    キュー使用率の例

  • プリンタおよびDell
  • プロセス管理
  • キャッシュ実装
  • 幅優先ナビゲーション(BFS)
  • キューとプロセス


    CPUはプロセスを管理し、各プロセスに適切なCPUを割り当てる.
    複数のプロセスで限られたメモリを効率的に使用するには、スケジューリング・テクノロジーによって選択される次の実行時に実行できるプロセスを選択する必要があります.
  • Job Queue:メインメモリの割り当て順序を待つスペース
  • 、ハードディスク上のプログラムを実行する
  • レディキュー:CPUが占有するスペースを待つ
  • 設備キュー:
  • 空間、I/O関連設備を待つ

    質問する


    https://programmers.co.kr/learn/courses/30/lessons/77485

    に近づく


    長方形の枠線の数字を分けて保存し、一番前の数字を後ろに送り、配列に入れればいいです.

    問題を解く


    1.行と列に適した配列を作成する

    const arr = Array.from(Array(rows), (_,i) => Array.from(Array(columns),(_,j)=>i*columns+j+1))

    2.query順に長方形の枠線値をスタックに保存

    const stack = [];
    for(let i=y1;i<y2;i++) stack.push(arr[x1][i]);
    for(let i=x1;i<x2;i++) stack.push(arr[i][y2]);
    for(let i=y2;i>y1;i--) stack.push(arr[x2][i]);
    for(let i=x2;i>x1;i--) stack.push(arr[i][y1]);

    3.ストレージスタックの最小値を結果にプッシュ

    answer.push(Math.min(...stack))

    4.スタックの前の値を最後に送信

    stack.unshift(stack.pop())

    5.アレイ内の長方形の枠線にスタック値を順次格納する

    for(let i=y1;i<y2;i++) arr[x1][i] = stack.shift();
    for(let i=x1;i<x2;i++) arr[i][y2] = stack.shift();
    for(let i=y2;i>y1;i--) arr[x2][i] = stack.shift();
    for(let i=x2;i>x1;i--) arr[i][y1] = stack.shift();

    完全なコード

     function solution(rows, columns, queries) {
        const answer = []
        const arr = Array.from(Array(rows), (_,i) => Array.from(Array(columns),(_,j)=>i*columns+j+1))
        console.log(arr)
    
        queries.map(query=>{
            const [x1,y1,x2,y2] = [query[0]-1,query[1]-1,query[2]-1,query[3]-1]
            
            const stack = [];
            for(let i=y1;i<y2;i++) stack.push(arr[x1][i]);
            for(let i=x1;i<x2;i++) stack.push(arr[i][y2]);
            for(let i=y2;i>y1;i--) stack.push(arr[x2][i]);
            for(let i=x2;i>x1;i--) stack.push(arr[i][y1]);
    
            answer.push(Math.min(...stack))
            stack.unshift(stack.pop())
            
            for(let i=y1;i<y2;i++) arr[x1][i] = stack.shift();
            for(let i=x1;i<x2;i++) arr[i][y2] = stack.shift();
            for(let i=y2;i>y1;i--) arr[x2][i] = stack.shift();
            for(let i=x2;i>x1;i--) arr[i][y1] = stack.shift();      
        }) 
        return answer;
    }