2015년 11월 16일 월요일

안드로이드 http통신 retrofit 2.0

retrofit은 http통신모듈로서 android에서 많이 사용한다고 합니다.

  • 파싱 & value object로의 변환이 편하고
  • template 방식으로의 사용
  • 동기 & 비동기 지원

의 장점을 뽑을 수 있을 것 같습니다.
spring framework를 공부하면서 동시에 개발하고 있는데 사용방식이 많이 유사함이 느껴집니다.

2.0을 기준 입니다.

저의 환경으로는  json으로 서버와 값을 주고 받게 됩니다.

기본적인 튜토리얼은 http://square.github.io/retrofit/ 를 참고했습니다.

먼저 라이브러리 추가. (GRADLE)


compile 'com.squareup.retrofit:retrofit:2.0.0-beta2'
//json파싱을 위한 주입
compile 'com.squareup.retrofit:converter-gson:2.0.0-beta2'
//xml파싱을 위한 주입
compile 'com.squareup.retrofit:adapter-rxjava:2.0.0-beta1'

value object 작성

public class test {
    private String ret;

    public String getRet() {
        return ret;
    }

    public void setRet(String ret) {
        this.ret = ret;
    }
}

Service작성


public interface TestService {
    @FormUrlEncoded
    @POST("/test")
    public Call<test> retroTest(@Field("param") String aa);
}


어노테이션을 몇개 정리.
@POST("상세주소")를 이용하여 상세 주소를 설정합니다.
@GET/PUT/DELETE등도 사용가능합니다.
@HEARs를 이용해서 헤더 설정도 가능하고

@FormUrlEncoded을 사용하여 x-www-form-urlencoded를 설정하고
@Multipart를 이용한 파일전송 등도 설정 가능합니다.

동기/비동기 방식이 1.9버전에서는 선언하는 방식이 서로 달랐는데 2.0버전에서는 두가지의 차이가 없습니다. 사용에 따라서 동기/비동기가 나눠지는데 아래 설명하겠습니다.


Service생성 및 반환

public class repo {
    public TestService getService(){
        Retrofit retrofit = new Retrofit.Builder()
                .baseUrl("http://192.168.25.24:8080")
                .addConverterFactory(GsonConverterFactory.create())
//              .addConverterFactory(SimpleXmlConverterFactory.create())
                .build();
        TestService service =  retrofit.create(TestService.class);
        return service;
    }
}

baseUrl을 설정하고, 저는 json만을 사용하기 때문에 GsonConverterFactory만 설정하였고 xml을 사용하시려면 SimpleXmlConverterFactory까지 설정 하시면 됩니다.

getService()를 이용하여 TestService에 대한 설정,생성,반환을 받습니다.

동기방식 사용

String result = null;
TestService service = new repo().getService();
Call<test> c = service.retroTest("aa");
try {
    result = c.execute().body().getRet();
} catch (IOException e) {
    e.printStackTrace();
}
위 방식은 동기방식 입니다. Call<test>를 받은 이후 실행(execute) -> 결과(body)를 하게 되면 위의 결과는 test객체에 담겨져 오게 됩니다.

비동기방식 사용

final String[] result = {null};
TestService service = new repo().getService();
Call<test> c = service.retroTest("aa");
c.enqueue(new Callback() {

    @Override
    public void onResponse(Response response, Retrofit retrofit) {
        result[0] = response.body().getRet();
    }

    @Override
    public void onFailure(Throwable t) {
        result[0] = "false";
    }
});
위 방식은 비동기방식 입니다. Call<test>를 받은 이후 enqueue를 통해 구현합니다.
onResponse를 통하여 결과값을 받을 때 처리, 즉 callback방식으로의 처리를 하게 됩니다.

위의 방법으로 안드로이드(또는 다른 java플렛폼)에서 사용을 간단하게 http통신을 하게 됩니다.

2015년 11월 9일 월요일

[spring] - mongo 에러처리

mongodb의 특성상 처리에 대한 결과를 신경 쓰지 않는다.

즉, 삽입에서의 성공, 실패에 대한 처리가 불가능가능하지 않다.

 결과를 리턴받는 것은 필요한 기능이고 당연 기능을 제공한다. 하지만 spring에서든 node에서든 이러한 성격에 따라 결과를 신경쓰지 않는 것을 따기 때문에 default 설정으로 그냥 넘기게 된다.

xml 설정의 mongoTemplate의 설정 부분을 바꾸면 된다.
<bean id="mongoTemplate" class="org.springframework.data.mongodb.core.MongoTemplate">
    <constructor-arg ref="mongo" />
    <constructor-arg value="oman" />
    <property name="writeResultChecking" value="EXCEPTION"/>
</bean>


value로 설정 할 수 있는 값은 3가지다.
none, exception, log



  • none
    • default 설정 값으로 아무런 행동도 하지 않는다. error를 던지지도 않고 로그로도 남기지 않는다.
  • log
    • 문제가 생길 경우 로그로 남긴다.
    • ....failed: E11000 duplicate key error index:........
  • exception
    • 예외처리가 되어 핸들링 할 수 있게 된다.
    • org.springframework.dao.DataIntegrityViolationException:.......

2015년 10월 24일 토요일

mysql transction isolation level (트렌젝션 격리 수준)



repeatable read
  • mysql에서 default로 설정되어 있는 트랜젝션 격리수준이다. 
  • 한 데이터에 대하여 데이터 트랜젝션이 수행중일 경우 읽기에 대한 접근을 할 수 있다.
  • 한 데이터에 대해 여러 트랜젝션이 동시에 진행중일 때 모든 트렌젝션이 끝날때까지 이전의 데이터를 읽을 수 있다.
    • 이점은 read commit 과 다른 점이다.
read uncommitted
  • 커밋 되지 않은 데이터 상태에서 읽을 경우 추후에 롤백이 되더라도 처리 된 부분까지의 결과를 읽을 수 있습니다. 즉, 트랜젝션 중간이라도 데이터 읽기에 대한 접근이 가능합니다.
  • dirty read라고 부르기도 한다.
read commit
  • 트랜젝션 중의 경우 커밋이 되어 있지 않다면 이전의 데이터를 읽는다는 점에서는 repeatable read와 비슷하다.
  • 여러 트랜젝션이 수행중일 경우 해당 세션에서 진행중인 트랜젝션의 범위 내에서만 적용된다.
 SERIALIZABLE
  • 가장 높은 level의 트랜젝션
  • 데이터에 대하여 트랜젝션이 수행중인 경우 읽기 쓰기 수정 삭제 모든게 불가능하다.

2015년 10월 12일 월요일

barcode 표기법 : code 128에 대하여



code 128에 대하여..

사진 출처는 언제나 위키피디아

code128은 아주 높은 정보를 집약해 놓을 수 있는 1차원 바코드 표기법이다.
즉, 적은 양의 표기로 많은 양의 정보를 보여줄 수 있다. (어디까지나 1차원 중에서..)
스마트폰의 스대가 오면서 2차원 바코드 스캐너, 즉 qr코드등의 스캔이 용이 해지면서 qr로 더욱 많은 정보를 전달하지만, 1차원 바코드가 비교적 빠르고 이미 많은 시스탬화 되어 있는 상황과 시중에 (특히 중고로 구매사용하는 상점들)은 1차원 바코드 스캐너를 이용하고 있다.  

흔히 바코드라 말하는 상품 분류코드는 ean 13으로 13자리표기로 물품을 분류관리 하고 있고 code128은 좀 다른 방식이다.

code 128의 심볼

총 108개의 문자를 표현 할 수 있다. 이중에 start symbol(3개)과 stop symbol(2개)를 제외하면 총 105개의 문자를 표현 할수 있다.
각 심볼을 구성하는 요소는 3개의 bar와 3개의 white space로 이루어져 있다.

Bar와 White Space

하나의 문자(심벌)에는 3개의 bar와 white space를 가지고 있으며 각각의 요소는 다른 두깨를 가지고 있으며 이에는 몇가지 규칙이 있다.

  • 이 두가지(bar,space)는 각각 1~4의 두깨를 가질수 있다.  
  • 하나의 symbol에서 Bar들의 두깨의 합은 짝수의 넓이를 가지고 
  • Space의 넓이들의 합은 홀수를 가져야 한다.
  • 하나의 심벌에서 모든 넓이의 값은 11의 넓이이다.(stop symbol일 경우 13)
바코드를 2진표기할때 이것을 이용한다.
예를 들어 0을 표기할때 11011001100로 표기하는데, 
순서대로 (단위: 두깨) 
  • 검은바(2) 흰공백(1) 검은바(2) 흰공백(2) 검은바(2) 흰공백(2)
가 되며 
  • 검은 바의 넓이의 합은 6(짝수)가 되며 흰공백의 넓이의 합은 5(홀수)가 된다.
  • 총 넓이의 합은 11이 된다.

Start Symbol

code128은 3가지의 code set을 사용한다. 각각 128a,128b,128c로 부른다.
이를 정의 하기 위한 symbol을 앞에 위치하게 된다. 위의 그림에서 2개의 2번영역 중 앞에 위치하게 된다.

Stop Symbol

stop심볼은 특수한 심볼이다. 다른 symbol들과는 달리 4개의 bar, 3개의 white space로 이루어져 있다. 1100011101011(2331112)로 적으며 위의 그림에서 2개의 2번영역중 뒤에 위치하게 된다. stop symbol은 아주 특수한 심벌로서 중요한 역활을 한다.
  • 바코드을 거꾸로 읽었을 경우를 인지 할 수 있다.
바로 읽을경우 2331112로 끝을 알리고 거꾸로 읽었을 경우 즉, 2111332일 경우 바코드를 반대로 읽었음을 인지하고 바로 할 수 있다.

Check digit

code 128에도 체크섬과 같은 역활을 하는 부분이 있다.
start symbol *1,과 각각의 2진비트값 * 위치 를 103으로 나눈 값을 적어 둔다.
마치 주민등록번호 유효성 검사와 같다.
위의 위치에서 4번에 위치하게 된다.

Quiet zone

바코드의 앞,뒤에 존재하게 되며, 최소한의 크기는 바코드의 내용문자의 *10의 크기를 가져야 한다. 위의 그림에서 1번에 위치하게 된다.

FUNCTION4

를 사용하면 더욱 많은 문자(특수한 문자)를 사용 할 수 있다고 한다.

2015년 6월 28일 일요일

몬티홀 문제 코딩 구현

확률에 관한 공부를 조금만 깊게 하면 한번쯤은 만나는 문제인듯 합니다.
몬티홀 게임, 몬티홀 딜레마 라고 불리는 이 문제의 법칙 및 순서는 아래와 같습니다.
  1. 각각의 3개의 문 뒤에는 염소 2마리, 자동차 1대 중 하나가 있다.
  2. 참가자는 하나의 문을 선택한다.
  3. 사회자는 선택되지 않은 문 중에 염소가 있는 문 하나를 공개한다.
  4. 참가자는 처음 선택한 문과 나머지 하나의 문 중에서 선택을 바꿀 기회를 얻는다.
  • 이러한 상황일 경우 바꾸는 것이 좋을 것인가? 그대로 선택하는 것이 좋을 것인가?


이 문제는 (적어도 저에게) 딜레마라는 문제 답게 이해하기 힘들었습니다.

이 문제는 사실 아주 쉬운 문제입니다.
  • 처음 고른 상품이 차 일 경우(1/3 확률) 사회자가 제외시킨 문을 제외하면 나머지는 무조건 염소
  • 처음 고른 상품이 염소 일 경우(2/3 확률) 사회자가 제외 시킨 문을 제외하면 나머지는 무조건 차

라는 결과가 나옵니다.

이 문제를 알려주셨던 선생님의 표현을 빌려 쓰자면, 사회자가 선택한 문의 확률이 흡수 되었다고 할 수 있습니다.


var i = 0;
var arr = ['goat','goat','goat'];
var success = 0;
var fail = 0;
for(i = 0;i<100000;i++,arr=['goat','goat','goat']){
	//자동차 랜덤 위치
	var car = Math.floor(Math.random()*3);
	arr[car] = 'car';
	
	//랜덤하게 선택
	var choice = Math.floor(Math.random()*3);
	
	
	//염소위치 알려줌
	do{	
		rm_index = Math.floor(Math.random()*3);
	}while(rm_index == car || rm_index == choice);


	//바꾼후 진행
	choice = 3-(rm_index+choice);
	
	if(arr[choice] == 'car'){
		success++;
	}
	else{
		fail++;
	}	
}

console.log("case : change")
console.log("success " + success);
console.log("fail " + fail);

결과는
success 33322
fail 66678
success 66660
fail 33340

2015년 5월 2일 토요일

트랜젝션 4가지 속성 ACID!


  • 분명 공부할때 에시드 에시드 에시드 하면서 외웠지만 벙떄림..

  • 원자성(Atomicity)
    • 트랜젝션과 관련된 작업은 하나의 단위이다.
    • 은행에서 이체의 예
      • 1)a의 출금, 2)b의 입금   2가지의 작업
      • 에러의 시점
        • 1)전 : a의 출금이 되지 않는다. b의 입금이 되지 않는다.
        • 1)후, 2)전 : a의 출금이 되었다. b의 입금이 되지 않는다.
        • 2)후 : a의 출금이 되었다. b의 입금이 되었다.
      • 위의 경우 두번째의 경우 중간 단계까지 실행되고 실패하는 일은 없어야한다.
      • 이러한 일을 방지하기 위해 원자성을 보장해야한다. 중간단계에서 실패하는 경우는 없어야한다.
      • 모든 작업은 하나의 단위로 하여 모든 경우 에러, 성공의 결과가 같아야한다.
  • 일관성(Consistency)
    • 트랜잭션 처리 후 모든 데이터베이스의 상태는 이전의 상태와 같아야 한다.
    • 즉. 결과가 데이터베이스의 무결성 제약 등을 위반하거나 모든 상태에 영향을 주어서는 안 된다.
  • 고립성(Isolation)
    • 트랜잭션의 연산은 다른 트랜잭션, 다른 연산작업이 끼어들지 못하게 보장해야한다.
  • 지속성(Durability)
    • 트랜잭션의 연산이 성공적으로 이루어지고 나면 그 결과는 유지되어야 한다.

2015년 4월 20일 월요일

[data structure javascript] binary tree


  • 실행환경 : nodejs
전체 코드는 길어서 github로 대체합니다.
데모는 여기
  • javascript를 이용한 binary tree구현
    • node를 구현, left와 right 자식엘리먼트의 주소와 엘리먼트를 저장할 data로 구성
    • tree에는 root를 가르키며, 이후 subtree을 가르키며 트리를 구성
      • javascript에서는 object(객체)에 대해서는 call by reference로 작동된다.
  • binary tree의 특징
    • 탐색시간이 log n(밑2) 이다.
    • 한 node의 subtree는 2개 이하이다.
      • 구현에서는 정렬을 위해, 
        • 왼쪽 노드는 부모노드 보다 작은 값을,
        • 오른쪽 노드는 부모 노드보다 큰 값을 넣는다.
  • 위와 같은 방식을 사용할 경우 문제,
    • 트리의 균형이 보장되지 않는다.
  • 해결방법
    • avl, red black 트리 등이 있다.
  • 삽입,
    • case 1. root가 비어있을 경우
      • root에 값을 넣는다.
    • case 2. root(node)에 값이 있을 경우
      • 1-1) 값을 비교하여 작을 경우 왼쪽 노드를 따라 간다.
      • 1-2) 값을 비교하여 클 경우 오른쪽 노드를 따라간다.
      • 2-1) 해당 위치가 비어 있지 않다면 case 2를 반복한다.
      • 2-2) 해당 위치가 비어 있다면 값을 넣어준다.
        • 부모노드의 해당 위치에 노드를 연결한다.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
tree.prototype.add = function(element,node){
 //루트 부터 시작
 var node = node||this.root;

 //루트가 null, 즉 트리가 비어있을 경우
 if(this.root == null){
  this.root = new NODE(element);
 }

 //루트가 비어있지 않을 경우
 else{
  if(element<node.data){
   if(node.left == null){
    node.left = new NODE(element);
   }
   else{
    this.add(element,node.left);
   }
  }
  else if(element>=node.data){
   if(node.right == null){
    node.right = new NODE(element);
   }
   else{
    this.add(element,node.right);

   }
  }
 }

 console.log("-------------------------------------------------------------");
 console.log("insert ",element);
 console.log("-------------------------------------------------------------");
 this.print();
}

  • 탐색
    • 1. 찾으려는 값과 root(node)와 값을 비교한다.
    • 2-1) 작을 경우 왼쪽 node를 따라간다.
    • 2-2) 클 경우 오른쪽 node를 따라간다.
    • 3. 같은 값이 나올때까지 1-2를 반복한다. 가르키는 노드가 비어있다면 null를 비교한다.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
tree.prototype.search = function(element, node){
 var node = node||this.root;

 target = null;
 if(node.data == element){
  target = node;
 }
 else if(element < node.data){
  target = this.search(element,node.left);
 }
 else{
  target = this.search(element,node.right);
 }

 return target;

}

  • 삭제
    • 해당 노드를 찾는다. 이때 부모 노드도 기억한다.
      • stack을 이용하여 찾으려는 노드의 모든 경로를 기억한다.
      • 부모노드는 stack의 top에 해당하는 노드의 바로 아래에 위치해 있을 것이다.
    • case 1, subtree가 없을 경우
      • 부모노드로부터 해당 노드를 삭제한다.
    • case 2, subtree가 1개 이상일 경우 후보를 찾는다.
      • 해당 노드 자리에 후보노드를 대체한다.
------------

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
tree.prototype.search2 = function(stack,element,node){
 var node = node||this.root;
 stack.push(node);

 if(node.data == element){
 }
 else if(element < node.data){
  this.search2(stack,element,node.left);
 }
 else{
  this.search2(stack,element,node.right);
 }
}


tree.prototype.del = function(element,node){
 node = node||this.root;
 // console.log(target);
 console.log("-------------------------------------------------------------");
 console.log("del "+element);
 console.log("-------------------------------------------------------------");

 target = null;
 parent = null;
 selected_node = null;
    

 var S = new stack();
    this.search2(S,element);
    // S.print();
    target = S.pop();
    parent == null;
    if(!S.isEmpty()){
     parent = S.pop();
    }

 this.renewDH(target);

 left_parent = target;
 left_node = target.left;
 if(left_node){
  while(left_node.right){
   left_node = left_node.right;
  }
 }

 right_parent = target;
 right_node = target.right;
 if(right_node){
  while(right_node.left){
   right_parent = right_node;
   right_node = right_node.left;

  }
 }

 left_depth = left_node==null?0:left_node.depth;
 right_depth = right_node==null?0:right_node.depth;



 if(target.height == 1){
  if(parent == null){
   this.root = null;
  }
  else if(parent.left == target){
   parent.left = null;
  }
  else{
   parent.right = null;
  } 
 }
 else if(left_depth>right_depth){
  selected_node = left_node;
  selected_parent = left_parent;
  if(left_depth == 1){
   selected_node.right = target.right;
   if(parent == null){
    this.root = selected_node;
   }
   else if(parent.left == target){
    parent.left = selected_node;
   }
   else{
    parent.right = selected_node;    
   }
  }
  else if(left_depth >= 2){
   selected_parent.right = selected_node.left;
   selected_node.left = target.left;
   selected_node.right = target.right;
   if(parent == null){
    this.root  = selected_node;
   }
   else if(parent.left == target){
    parent.left = selected_node;
   }
   else{
    parent.right = selected_node;    
   }
  }
 }

 else if(left_depth<=right_depth){
  selected_node = right_node;
  selected_parent = right_parent;
  if(right_depth == 1){
   selected_node.left = target.left;
   if(parent == null){
    this.root = selected_node;
   }
   else if(parent.left == target){
    parent.left = selected_node;
   }
   else{
    parent.right = selected_node;    
   }
  }
  else if(right_depth >= 2){
   selected_parent.left = selected_node.right;
   selected_node.left = target.left;
   selected_node.right = target.right;
   if(parent == null){
    this.root  = selected_node;
   }
   else if(parent.left == target){
    parent.left = selected_node;
   }
   else{
    parent.right = selected_node;    
   }
  }
 }

    this.print();

}

  • 후보노드
          • 이것은 만드는 사람이 정하기 나름!
    • 왼쪽 방향
      • 해당노드의 left node를 시작으로 right node가 null일 경우 까지 계속 따라 내려간다.
    • 오른쪽 방향
      • 해당노드의 right node를 시작으로 left node가 null일 경우 까지 계속 따라 내려간다.
    • 두 노드 중에 depth가 큰 노드를 후보노드로 선정한다.

  • 구현에 있어서의 특징,
    • javascript의 특성상 closure의 특징 때문에 height를 구하는 점에 있어서 문제가 생긴다.  (node_left, node_right의 값이 recursive하며 계속하여 달라진다.)
      • 이를 해결하기 위해 stack를 사용함.
    • 출력에 있어서 깊이 우선 탐색을 하여 높은 노드부터 순차적으로 출력하도록 하였다. 부모노드 부터 순차적으로 기록하기 위해 queue를 사용하였다.




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

2015년 4월 19일 일요일

[data structure javascript] Linked List


  • 실행환경 : nodejs

  • javascript를 이용한 linked list구현
    • node를 구현, 단순 linked list 이기 때문에 다음 느드를 가르키는 next와, 엘리먼트를 저장할 data로 구성
    • node를 출력하면 다음 노드, 다음 노드의 다음노드, 다음 노드의 다음 노드의 다음 노드..... 쭈욱 출력이 되지만, 실제로는 객체 값이 저장되는 것이 아니라 주소를 가르키고 있다.
      • javascript에서는 object(객체)에 대해서는 call by reference로 작동된다.
  • linked_list의 특징
    • 노드로 구성
    • 노드에는 값과 다음 값에 대한 주소를 가지고 있다.
  • 장정
    • 크기에 제한을 가지고 있지 않다.
    • 중간 삽입, 삭제가 array에 비하여 쉽다.
    • 삽입, 삭제에 대한 비용이 적다. O(1)
    • 때문에 c,c++ 등에서 자료구조를 구현할때 linked list를 주로 활용한다.
  • 단점
    • 탐색에 있어서 단방향이다.
    • 탐색에 대하여 비용이 크다. O(n)
    • 때문에 삽입,삭제 에 있어서 이전 노드의 주소(객체)의 정보를 가지고 있어야 한다.
    • 이중 연결 리스트가 방안이 될 수 있다.
  • linked list용어
    • node
      • 하나의 객체로, 값과 다음 값으로 이루어 져 있다.
  • 자매품
    • 환영 연결 리스트
    • 이중 연결 리스트
  • 삽입 방법
    • 삽입 할 노드의 앞의 노드를 찾는다. (이전노드)
    • 이전 노드의 next의 주소를 삽입할 노드의 next로 넣는다.
    • 이전 노드의 next의 주소를 삽입할 노드의 주소를 넣는다.

  • 삭제 방법
    • 삽입 반대로.





  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
var linkedList = function(){
 this.length = 0;
 this.headNode = new node(null);
}


var node = function(element){
 this.data = element;
 this.next = null;
}

linkedList.prototype.add = function(element,position){
 
 //position이 null일 경우 마지막위치로
 var position = position==undefined?this.length+1:position;
 
 //입력값으로 node 생성

 var newNode = new node(element);

 var preNode = this.headNode;
 for(i = 1;i<position;i++){
  preNode = preNode.next;
 }
 newNode.next = preNode==null?null:preNode.next;
 preNode.next = newNode;

 this.length++;

 // console.log("-------------------------------------------");
 // console.log("add",element);
 // console.log("position",position);
 // console.log("-------------------------------------------");
 // this.print();
}

linkedList.prototype.remove = function(position){

 var ret = null;
 var position = position==undefined?0:position;
 if(this.isEmpty()){
  console.log("list is Empty");
 }
 else if(position<this.length){
  var preNode = this.headNode;

  for(i = 0;i<position;i++){
   preNode = preNode.next;
  }
  ret = preNode.next.data;
  preNode.next = preNode.next.next;
  
  this.length--;
 }
 else{
  console.log("index error");
 }

 // console.log("-------------------------------------------");
 // console.log("position",position);
 // console.log("remove",ret);
 // console.log("-------------------------------------------");
 // this.print();
 return ret;
}


linkedList.prototype.peek = function(position){

 var ret = null;
 var position = position==undefined?0:position;
 if(this.isEmpty()){
  console.log("list is Empty");
 }
 else if(position<this.length){
  var preNode = this.headNode;

  for(i = 0;i<position;i++){
   preNode = preNode.next;
  }
  ret = preNode.next.data;

 }
 else{
  console.log("index error");
 }

 return ret;
}

linkedList.prototype.print = function(position){
 var str = "linkedList : ";
 var node = this.headNode.next;
 while(node != null){
  str += node.data;
  str += " -> ";
  node = node.next;
 };
 console.log(str);
}


linkedList.prototype.isEmpty = function(){
 var ret = false;
 if(!this.length){
  ret = true;
 }

 return ret;
}

// list = new linkedList();

// list.add(1);

// list.add(2);

// list.add(3);

// list.add(3,1);

// list.add(1);

// list.remove();
// list.remove(3);

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

[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의 맨 위에 해당하는 엘리먼트를 리턴, 삭제한다.
    • top
      • 맨 위의 값, push한 값, pop이 될 값이 된다.
    • buttom
      • 맨 아래, top == buttom이라면 stack이 비었음을 의미한다.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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의 대상이 된다.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 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