공부합시다.

2015년 4월 19일 일요일

[data structure javascript] Stack

실행환경 : nodejs

javascript를 이용한 stack 구현

배열의 구조,api를 활용
javascript의 약한 언어의 특징 때문에 쉬운 구현이 가능

때문에 크기에 제한을 두지 않는다.(메모리 크기까지 가능)
javascript의 array 메소드에 push, pop을 활용하여 간단한 구현을 하였습니다.

stack의 특징

last in first out, first in last out 특징
인터럽트, tree의 전위 순회 등에 쓰인다.

(제 tree의 구현에 사용했습니다.)

stack용어

push(,= put)

삽입, stack의 맨 위에 해당 엘리먼트를 삽입한다.

pop(,= get)

삭제, stack의 맨 위에 해당하는 엘리먼트를 리턴, 삭제한다.

맨 위의 값, push한 값, pop이 될 값이 된다.

buttom

맨 아래, top == buttom이라면 stack이 비었음을 의미한다.

var stack = function(){
 this.datas = [];
}


stack.prototype.isEmpty = function(){
  return this.datas.length==0?true:false;
}
stack.prototype.length = function(){
 return this.datas.length;
}
stack.prototype.push = function(element){

 this.datas.push(element);
 // console.log("-------------------------------------------------------------");
 // console.log("push ",element);
 // console.log("-------------------------------------------------------------");
 // this.print();

}
stack.prototype.pop = function(){
 element = this.peek();
 this.datas.pop();
 // console.log("-------------------------------------------------------------");
 // console.log("pop!");
 // console.log("return",element);
 // console.log("-------------------------------------------------------------");
 // this.print();
 return element;
}
stack.prototype.peek = function(){
 element = this.datas[this.datas.length-1]==undefined?null:this.datas[this.datas.length-1];
 return element;
}
stack.prototype.toArray = function(){
 return this.datas;
}
stack.prototype.print = function(){
 var tmp = this.datas;
 for(i=tmp.length-1;0<=i;i--){
  console.log("│ "+this.datas[i]+" │");
 }
 console.log("└---┘");
}

stack.prototype.delAll = function(){
 this.datas = [];
}

// S = new stack();

// S.push(3);
// S.push(5);
// S.push(1);
// S.push(6);

// S.pop();

// S.pop();

// S.push(9);
// S.push(8);

module.exports = stack;

아래 github또는 블로그 내에 다른 tree, linked list, tree에 대한 구현 글이 있습니다..
github에는 실행 데모도 있습니다.
https://github.com/ignocide/data-structure

[data structure, javascript] Queue

실행환경 : nodejs

javascript를 이용한 queue 구현

배열의 구조,api를 활용
javascript의 약한 언어의 특징 때문에 쉬운 구현이 가능

때문에 크기에 제한을 두지 않는다.(메모리 크기까지 가능)
같은 의미로서 linked list로 구현하는 큐의 장점( 큐의 크기에 제한이 적다)라는 점 역시 가지고 있다.
splice라는 array함수를 이용하여 중간 삽입도 쉽게 구현이 가능하다.

(구현 안 한건 비밀)

shift 함수를 이용하여 font,rare의 인덱스를 관리하지 않아도 되게끔 구현하였다.

queue의 특징

first in first out, last in last out 특징
tree의 깊이 우선탐색, sliding window 등 주로 순서 처리의 시스템에 쓰인다.

queue 용어

enqueue (,= put)

삽입, queue의 맨뒤에 해당 엘리먼트를 삽입한다.

dequeue (,= get)

삭제, queue의 맨 앞에 해당하는 엘리먼트를 리턴, 삭제한다.

rare

맨 뒤의 값, enqueue 한 값을 가르키게 된다.

front (,= head)

맨앞의 값, dequeue의 대상이 된다.

 var queue = function(){
  this.datas = [];
 }

 queue.prototype.isEmpty = function(){
   return this.datas.length==0?true:false;
 }
 queue.prototype.length = function(){
  return this.datas.length;
 }
 queue.prototype.enqueue = function(element){
  this.datas.push(element);
  // console.log("-------------------------------------------------------------");
  // console.log("enqueue ",element);
  // console.log("-------------------------------------------------------------");
  this.print();

 }
 queue.prototype.dequeue = function(){
  element = this.peek();
  this.datas.shift();
  // console.log("-------------------------------------------------------------");
  // console.log("dequeue, return ",element);
  // console.log("-------------------------------------------------------------");
  // this.print();
  return element;
 }
 queue.prototype.peek = function(){
  element = this.datas[0]==undefined?null:this.datas[0];
  return element;
 }
 queue.prototype.toArray = function(){
  return this.datas;
 }
 queue.prototype.print = function(){
  console.log(this.datas);
 }

 queue.prototype.delAll = function(){
  this.dats = [];
 }

 // Q = new queue();

 // Q.enqueue(5);
 // Q.enqueue(3);
 // Q.dequeue();
 // Q.enqueue(8);
 // Q.enqueue(7);
 // Q.dequeue();
 // Q.enqueue(9);
 // Q.enqueue(10);
 // Q.dequeue();

 module.exports = queue;

아래 github또는 블로그 내에 다른 stack, linked list, tree에 대한 구현 글이 있습니다..
github에는 실행 데모도 있습니다.
https://github.com/ignocide/data-structure