キュー

32474 ワード
テキストリンク

3.キュー


1）Q？


:先入先出、先入先出
:キューに並んでいる場合は、出力を印刷するときにキューを使用します.
:スタックとは異なり、キューにはdequeue()、front()があります.

2)キューの作成


:キューを表すクラスを直接作成できます.

(1)スタック実装に必要な方法


  • Enqueue(要素):キューの後ろに要素を追加します.

  • dequene():キュー内の最初の要素(一番前)を返して削除します.

  • front():キューの最初の要素を返します.

  • isEmpty():キューが空の場合はtrueまたはfalseを返します.

  • size():キュー内の要素の数を返します.(配列の長さに等しい()

    • (2) enqueue()


  • Enqueue()は、キューに要素を追加する方法であり、キューの後ろにのみ追加されます.

  • ただし、スタックの上部に魔要素を入れることができます.
    • var items = [];

this.enqueue = function(element){
  items.push(element);
}

    (3) dequeue()


  • キューに最初に追加した要素を削除します.

  • shift()は、インデックスが0の要素を配列から削除します.
    • this.dequeue= function(){
  return items.shift();
}

    (4) front()

  • キューの一番前の要素を見つけます.
    • this.front = function(){
  return item[0];
}

    (5) isEmpty()

  • キューはtrueとして空で、スタックの1つがfalseを返します.
    • this.isEmpty = function(){
  return items.length == 0;
}

<br/>

### (6) size()

- 스택의 size()와 같다.

```javascript
this.size = function(){
  return items.length;
}

    3）stack類、一目瞭然


    function Queue(){
  var items = [];
  
  this.enqueue = function(element){
    items.push(element);
  }
  this.dequeue = function(){
    return items[0];
  }
  this.isEmpty = function(){
    return items.length == 0;
  }
  this.clear = function(){
    items = [];
  }
  this.size = function(){
    return items.length;
  }
  this.print = function(){
    console.log(items.toString());
  }
}

    4）各種キュー


    (1)優先順位による優先順位キュー


  • 通常のキューとは異なり、要素は優先順位で追加および削除されます.

  • 優先キューには、優先順位によるエントリと優先順位による削除の2つのケースがあります.

  • 現実の生活では、ファーストクラスとビジネスクラスの乗客はいつもコーチクラスの乗客より優先されている.
    • function PriorityQueue(){
  var items = [];
  
  function QueueElement (element, priority){      //(a)
    this.element = element;
    this.priority = priority;
  }
    (a):キュー要素に優先権を付与する新しい要素.
      this.enqueue = function(element, priority){
    var queueElement = new QueueElement(element, priority);
    
    if(this.isEmpty()){
      items.push(queueElement);                  //(b)
    }
    (b):キューが空の場合、直接要素を入れます.
        else{
      var added = false;
      for(var i=0; i<items.length; i++){
        if(queueElement.priority < items[i].priority){
          items.splice(i, 0, queueElement);     //(c)
          added = true;
          break;                                //(d)
        }
      }
      if(!added){                               //(e)
        items.push(queueElement);
      }
    }
  };
  
  //기본 큐와 동일한 메소드
}
    (c)新しい要素と既存の要素を比較する
    :キューが空でない場合は、まず既存の要素と優先度を比較します.
    :既存の要素の優先度が新しい要素より高い場合は、セルの前に新しい要素を追加します.
    :このときはArrayです.slice(インデックス、削除する個数、挿入する要素)を使用して追加します.
    (d):サイクル終了.
    (e):新しい要素の優先度が最も低い場合は、キューの最後に追加します.

    (2)リングキュー

  • リング型Qはホットポテトゲームのようです.
    • 뜨거운 감자게임이란, 원형 테이블에 앉아있는 아이들이 뜨거운 감자를 옆 사람에게 넘긴다.
그러다가 갑자기 모두 동작을 멈추구 그때 뜨거운 감자를 손에 들고 있는 아이가 벌칙으로 퇴장하는 방식이다.
이 게임은 최후의 1인이 남을 때까지 반복한다.

    5)スタックの問題を解いてみる


    (1)18258号、開始2

    //1. 받을 명령의 개수
var input = prompt('명령의 개수를 입력하시오');
var box = [];

// 2. 명령의 개수만큼 반복
while(input > 0){
    let action = prompt('원하는 동작을 입력하시오');
    // push가 포함된 명령의 경우, 숫자만 추출하여 -> 입력
    QueueMethod(action);
    input = input-1;
}

function QueueMethod(action){
    var splitBox = action.split(' ')
    switch(splitBox[0]){
        case 'push':
            return(box.push(splitBox[1]));

        case 'pop':
            let popresult = box.shift();
            alert(popresult == undefined ? -1 : popresult);
            break;
        
        case 'size':
            alert(box.length);
            break;

        case 'empty':
            alert(box.length == 0 ? 1 : 0)
            break;
        
        case 'front':
            alert( box[0] == undefined ? -1 : box[0]);
            break;
        
        case 'back':
            alert(box[box.length-1] == undefined ? -1 : box[box.length-1]);
            break;
    }
    
}

    (2) 2164、カード2

    //1. n개의 카드가 주어진다.
card = prompt('카드의 개수를 입력하시오')
card_num = parseInt(card)
box = []
// 2.카드를 정렬한다.
for(var i=1; i<=card_num; i++){
    box.push(i);
};
alert(box);

//3. 
while(true){

//1,2,3,4
//0번째 버림
//0번째 버리고 -> 끝에 추가

    box.shift();
    alert('box=' + box);
    let move = box.shift();
    alert('box=' +  box);
    box.push(move);
    alert('box=' +  box);
    
    if(box.length == 1){
        alert(box[0]);
        break;
    }
}

    (3)11866,Joseph問題0

    //1. 1,2,3,4,5,6,7
// k = 3인 경우 [2번반복, 1번]
// shift()->push()
// shift()->push()
// shift()

// 1. n,k를 입력받는다.
var input = prompt('n k를 입력하시오');
var inputBox = input.split(' ');
var n = parseInt(inputBox[0]), k = parseInt(inputBox[1]);

var box = [], result = [];
//2. n개의 원소로 이루어진 배열 생성
for(var i=1; i<=n; i++){
    box.push(i);
}

// 3. k-1번 shift&push반복 | 1번 shift
while(true){
    for(let j=0; j<k-1; j++){
        let moveNum = box.shift();
        box.push(moveNum);
    }
    let resultNum = box.shift();
    result.push(resultNum);

    if(box.length == 0){
        alert(result);
        break;
    }
    TIL 🍩
    [国の原稿項目]FilePathGetter Class