티스토리 뷰
간단한 구현 :
javascript로 큐를 간단히 구현하려면 배열, push() 함수 (enqueue), shift() 함수 (dequeue)를 이용하면 된다.
그런데 shift() 함수의 시간 복잡도는 O(n)으로 다소 비효율적일 수 있다.
온라인 저지 사이트에서 javascript로 문제 풀다가 큐 때문에 시간 초과가 나면 아래처럼 바꿔보자.
효율적인 구현 :
offset 변수를 추가로 이용해서 배열에서 dequeue 될 요소에 바로 접근한다 O(1)
만약 offset이 큐 길이 2배 이상이 되면 앞 부분을 자르고 (이미 dequeue 된 요소들),
offset은 0으로 초기화한다.
(내가 구현한 것 아님. 맨 아래 출처 참고 바랍니다.)
function Queue(){
// initialise the queue and offset
var queue = [];
var offset = 0;
// Returns the length of the queue.
this.getLength = function(){
return (queue.length - offset);
}
// Returns true if the queue is empty, and false otherwise.
this.isEmpty = function(){
return (queue.length == 0);
}
/* Enqueues the specified item. The parameter is:
*
* item - the item to enqueue
*/
this.enqueue = function(item){
queue.push(item);
}
/* Dequeues an item and returns it. If the queue is empty, the value
* 'undefined' is returned.
*/
this.dequeue = function(){
// if the queue is empty, return immediately
if (queue.length == 0) return undefined;
// store the item at the front of the queue
var item = queue[offset];
// increment the offset and remove the free space if necessary
if (++ offset * 2 >= queue.length){
queue = queue.slice(offset);
offset = 0;
}
// return the dequeued item
return item;
}
/* Returns the item at the front of the queue (without dequeuing it). If the
* queue is empty then undefined is returned.
*/
this.peek = function(){
return (queue.length > 0 ? queue[offset] : undefined);
}
}
같은 코드 짧은 버전 :
function Queue(){
var a=[],b=0;
this.getLength=function(){return a.length-b};
this.isEmpty=function(){return 0==a.length};
this.enqueue=function(b){a.push(b)};
this.dequeue=function(){if(0!=a.length){
var c=a[b];
2*++b>=a.length&&(a=a.slice(b),b=0);
return c}};
this.peek=function(){return 0<a.length?a[b]:void 0}
};
'시리즈 > Javascript' 카테고리의 다른 글
정규표현식 예제 (0) | 2021.02.20 |
---|---|
Map and Set (0) | 2021.02.20 |
String.prototype.replace() 함수 (0) | 2021.01.22 |
javascript 팁 (0) | 2021.01.21 |
javascript 콘솔 입출력 (0) | 2021.01.21 |
댓글
공지사항
최근에 올라온 글