[Linear] Queue

큐는 흔히들 이야기하는 선착순, 카페 줄서기, 은행줄서기를 생각하면 이해하기 쉽다.

 

먼저 들어온 값이 먼저 나가는 것으로 , FIFO(First in First Out)으로 볼 수 있다.

 

전형적인 큐의 모습

큐는 프로세스 스케줄링, 네트워크 패킷처리, 프린트 대기열, 대부분의 입출력 등에서 사용된다.

 

큐에서 흔히 사용되는 ADT(Abstract Data Type)는  Enqueue(삽입), Dequeue(값 빼기), Size(크기확인),

 

Empty(비었는지 확인), peek (맨 앞값 확인) 가 있다.

Psuedo 코드

QueueArr[10] 생성
tail =0 생성(꼬리) head =0(맨앞) 생성

Enqueue(data) 함수 생성
tail이 큐배열의 길이보다 크면 "큐 오버플로우" 메시지 출력
그 반대면 배열에 data값 삽입
tail++ 증가.

Dequeue 함수 생성
tail <= head이면 "큐 언더 플로우" 메시지 출력
그 반대면 QueueArr.shift()로 값 제거하고, tail-- 감소.

isEmpty 함수생성
tail === 0이면 true 반환

peek 함수생성
QueueArr[0] 값 리턴

1. Functional intantiation

function Queue(){
  let items = [];
  
  this.enqueue = function(element){
    if(items.length >=10){
      console.log("Queue overFlow");
    }
    items.push(element);
  };

  this.dequeue= function(){
    if(items.length <0){
      console.log("Queue underFlow");
    }    
    return items.shift();
  };

  this.front = function(){
    return items[0];
  }
  this.isEmpty = function(){
    return items.length === 0;
  }
  this.size = function(){
    return items.length;
  }
  this.print = function(){
    console.log(items.toString());
  }
}

let queue = new Queue();

queue.enqueue('John');
queue.front();
queue.size();

2. Pseudoclassical instantiation

class Queue{
  constructor(){
   this.items = [];   
  }  
}

Queue.prototype.enqueue = function(element){
  if(this.items.length >=10){
     console.log("Queue overFlow");
  }
  this.items.push(element);
};

Queue.prototype.dequeue= function(){
  if(this.items.length <0){
    console.log("Queue underFlow");
  }    
  return this.items.shift();
};

Queue.prototype.front = function(){
  return this.items[0];
}

Queue.prototype.isEmpty = function(){
  return this.items.length === 0;
}

Queue.prototype.size = function(){
  return this.items.length;
}

Queue.prototype.print = function(){
  console.log(this.items.toString());
}


let queue = new Queue();

queue.enqueue('John');
queue.front();
queue.size();