2015년 1월 28일 수요일

[JavaScript] 자바스크립트 String(문자열) 자료형

자바스크립트 String 데이터 타입

16bit 유니코드 문자들로 이루어지는 String(문자열) 데이터 타입 이다. 이 또한 다른 프로그래밍 언어에서도 볼 수 있는 흔한 타입이다. 자바스크립트(ECMA 스크립트)에서 String 타입은 쌍따옴표(")와 단따옴표(') 로 문자열을 감쌈으로써 선언이 가능하다. 단 문자열을 감싸는 따옴표가 같은 따옴표여야 한다.


var stringVar1 = "StringTest1";
var stringVar2 = 'StringTest2';
var stringVar3 = "StringTest2';//에러가 나게된다.


String 데이터 타입의 메모리 관리


사실 String(문자열) 타입은 따로 특별히 다룰게 없는데, String 데이터 타입의 메모리 매니지먼트는 알아두는게 좋다. Number, Boolean 등 다른 Primitive Data Type(원시 자료형)들이 변수 값의 수정시 추가적인 메모리 할당을 하지 않는 것에 반해, String 자료형은 변수값이 변경될 때마다 새로운 메모리를 할당해줘야한다. 물론 이건 자바스크립트 엔진이 할 일이니 코딩시 개발자들이 따로 특별한 코드를 부가해야하는 것은 아니다. 이런 일들이 벌어지게되는 이유는 바로 String(문자열) 데이터 타입이 이름에서도 잘 알 수 있듯 "문자들의 열"로 이루어져있기 때문이다. 16bit 유니코드 문자들의 열로 이루어진 ECMAScript 의 String 자료형은 문자 1개당 2바이트의 메모리를 소모하게 되다. 그렇다면 한번 생각해보자.

ABCDEFGH 라는 스트링을 저장해야한다고 할 때

[A][B][C][D][E][F][G][H]
처럼 16 바이트의 연속되는 메모리를 할당하는게 좋을까?

아니면

[A][ ][ ][ ][ ][ ]
[ ][B][C][D][ ][ ]
[ ][ ][F][G][ ][E]
[ ][ ][ ][H][ ][ ]
처럼 각기 떨어져있는 메모리들을 할당하는게 좋을까?

물론 당연히 전자의 경우가 훨씬 효과적일 것이다. 전자의 경우에는 메모리가 서로 연속되있어, RAM에 엑세스할시에 후자에 비해 훨씬 빠른속도로 전체 엑세스가 가능하다. 하지만 후자의 경우에는 각기 떨어져있는 메모리에 엑세스하느라 전자에 비해서는 느리게 읽게될것이다. 물론 이는 매우 미세한 차이지만, 메모리 관리의 효율성 관점으로 보았을 때, 후자의 경우대로 관리해서는 절대로 안될 것이다.

어쨋든 이게 String 값이 변경될 때 새로운 메모리를 할당해야된다는 것과 무슨 관련이 있나면,
스트링 변수에 주어진 메모리 바로 옆에 새로운 값이 할당되는것과 같은 아래의 경우와 같은 일이 발생할 수도 있다는건데

[A][B][C][D][E][F][G][H][0][N][E][W][V][A][L][U][E]

만약 이 경우에 새로운 메모리블록을 할당하지 않고 ABCDEFGH라는 스트링 값에 IJK를 추가해야 한다면, 아마 [0][N][E][W]가 저장된 메모리와 그 뒤의 메모리들이 순차적으로 뒤로 밀려나거나(매우 비효율적인 방법), [0][N][E][W]라는 메모리를 그냥 무시하고 [I][J][K][0]로 그냥 덮어 씌울 수도 있겠다. 하지만 이 경우에는 결국 NEWVALUE라는 값이 저장된 변수를 훼손하게 된다. 이런 이유 때문에 스트링값의 변경이 있을시에 새로운 메모리 블락을 할당해주고, 그 전 블락을 풀어주게 되는건데, 코드로 보자.


var stringVar1 = "ABCDEFGH";//[A][B][C][D][E][F][G][H]
var stringVar2 = 'NEWVALUE';//[A][B][C][D][E][F][G][H][0][N][E][W][V][A][L][U][E]
var stringVar1 = stringVar1 + "IJK";


위의 코드가 실행되면 메모리 할당은 아래와같이 바뀌게 된다

[ ][ ][ ][ ][ ][ ][ ][ ][ ][N][E][W][V][A][L][U][E]
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
[A][B][C][D][E][F][G][H][I][J][K][ ][ ][ ][ ][ ][ ]

이 모든게 개발자들이 보는 모니터 뒤에서 일어나는 일이기는 하지만, 이 때문에 자바스크립트 엔진 String 데이터 타입 관리에 따라서, String Concatenation(문자열 연결) 작업에 걸리는 시간이 좌지우지 되고, 나아가선 자바스크립트 엔진의 성능차이가 발생하는 원인이 되기도 한다.

String(문자열) 타입의 자동 타입 변환


타 자료형의 String 타입으로의 변환은 toString() 함수나, String() 함수로 손 쉽게 가능하다.
그리고 코드 작성시 보게되는 텍스트를 그대로 스트링타입으로 변환하니, 변환 불가능한 값이 없다고 말할 수 있다


var boolTrue = true;
var stringVar1 = boolTrue.toString(); //"true"

//toString()함수는 파라미터로 radix를 넣어서 2, 8, 10, 16진수로 변환 할 수도 있다.
var var1 = 33;
var stringVar1 = var1.toString(2); //"100001"
var stringVar2 = var1.toString(8); //"41"
var stringVar3 = var1.toString(16); //"21"

//단 null 이나 undefined 값은 toString() 함수로 변환하기가 불가능하다. 
//그렇기 때문에 필요한 경우에는 될 수 있으면 String() 함수를 이용해주자

var stringVar4 = String(null); //"null"
var stringVar5 = String(undefined); //"undefined"
var stringVar6 = String(2); //"2"

//또 따옴표를 이용할 수도 있다
var stringVar7 = '\"' + var1 + '\"'; //"33"

2015년 1월 27일 화요일

[JavaScript] 자바스크립트 Boolean 자료형

자바스크립트의 Boolean 데이터 타입

어떤 프로그래밍 언어에도 존재하는 자료형, 값이 true 또는 false, 총 2개밖에 존재하지 않는 자료형, 바로 Boolean 자료형이다. Boolean 자료형은 아래와 같이 선언된다.


var trueVariable = true;
var falseVariable = false;

//대소문자를 가리니, True 나 False 를 어싸인할시에는 에러가 뜬다

var trueVariable0 = True;
var falseVariable0 = False;

Number 자료형이 Number() 함수, parseInt() 함수를 사용해서 자료형을 변환할 수 있는 것처럼 Boolean 자료형도 Boolean 함수를 이용해서 다른 자료형을 Boolean 자료형으로 변환이 가능하다.


var booleanVar1 = Boolean("String");
var booleanVar2 = Boolean(null);
var booleanVar3 = Boolean(undefined);
var booleanVar4 = Boolean(4);
var booleanVar5 = Boolean(true);

자바스크립트 Boolean() 함수 자료형 변환 표


자료형
변환시 Boolean 값
truefalse
Booleantruefalse
String공을 제외한 모든 스트링 값스트링이 "" 처럼 공일때
Number0 보다 큰 모든 수들0 or NaN
Objectnull 을 제외한 모든 object 들null
Undefined해당 사항 없음undefined
Null해당 사항 없음null

[JavaScript] 자바스크립트 Number 자료형

자바스크립트의 Number 데이터 타입

ECMAScript 에서 Number 자료형은 정수형(Integer Value)이든 소수형(Floating Point Value)이든 상관없이 IEEE-754 형식을 이용해서 저장한다. IEEE-754가 뭔지 잠시 짚고 넘어가자면

IEEE-754는 전기 전자 기술자 협회(IEEE)에서 개발한 컴퓨터에서 부동소수점를 표현하는 가장 널리 쓰이는 표준이다. ±0 등의 수와 무한, NaN 등의 기호를 표시하는 법과 이러한 수에 대한 연산을 정의하고 있다.

간단히 말하자면 0 과 1, 즉 이진법으로 이루어진 컴퓨터 연산체계에서 0 과 1 이상의 수들을 표현하는 표준 방식이라고 할 수 있다. IEEE-754 체계에서는 가장 첫번째 비트가 +,-인지를, 즉 그 수가 음수인지 양수인지를 나타내는데, 이러한 이유로 ECMAScript 에서는 0과 -0이 둘다 존재할 수 있다. 물론 0 == -0이라는 조건은 true(참)이다.

정수형


IEEE 32bits Single Precision 형식
IEEE 32bits Single Precision 형식

ECMAScript 는 굉장한 유연성과 높은 자유도를 가졌는데, 이러한 이유로 다양한 정수형 수들(8진수, 16진수)을 표현하기위한 다양한 문법들이 존재한다.
참고로 정수형 수들을 저장할 때는 32bits single precision 형식으로 저장된다는걸 기억하자. 즉 어떤 정수 값이든간에, 32비트 형식으로 저장된다는 것 이다. 위의 그림에 나와있는 방식으로 저장된다 생각하면 된다.


var integerNumber = 35; //integer 값을 선언할 때

//8진수를 표현할 때는 첫번째 자리의 숫자가 무조건 0 이여야 한다.
var octalNumber1 = 07; //8진수 07, 10진수로 환산하면 7
var octalNumber2 = 017; //8진수 017, 10진수로 환산하면 15
var octalNumber3 = 019; //3번째 자리의 수가 8진수에 없는 숫자인 9라 일반 10진수로 받들여지게 된다.
//하지만 8진수의 사용은, strict 모드에서 에러를 발생시키고, 몇몇 브라우져에서는 제대로 실행되지 않으므로 사용을 자제하자.

//16진수를 표현할 때에는 숫자 앞에 무조건 0x 를 붙인다.
var hexaNumber1 = 0x7; //16진수 07, 10진수로 환산하면 7
var hexaNumber2 = 0xA7; //16진수 A7, 10진수로 환산하면 167
var hexaNumber3 = 0xB35; //16진수 B35, 10진수로 환산하면 2869


하지만 결국 16진수나 8진수로 선언된 변수들도 연산시에는 다 10진수로 변환되니, 별다른 특별한 이유가 없으면 10진수를 사용하도록 하자.

소수형


IEEE 64bits Double Precision 형식
IEEE 64bits Double Precision 형식

ECAMScript에서의 소수형은 정수형과는 달리 64bits double precision 형식으로 저장된다. 바로 위의 그림과 같은 형식이다. 소수형 수들은 아래와 같이 선언되는데


var floatingNumber1 = 0.3; 
var floatingNumber2 = 1.47;
var floatingNumber3 = .7;//안 좋은 예제 1
var floatingNumber3 = 3.;//안 좋은 예제 2, 결국 3으로 자동 변환되 저장됨
var floatingNumber3 = 4.0;//안 좋은 예제 3, 4가 정수형으로 인식되서 32bit 형식으로 저장됨
var floatingNumber3 = 4.572e3;// = 4572, 많이 작거나 큰 숫자의 경우에는 e-notation을 이용 10의 몇 승으로 표현할 수 있다.
var floatingNumber3 = 4.572e-3;// = 0.04572
//ECMASCript 는 소수점아래로 0이 5개보다 많을 시에 무조건 e-notation을 이용한 표기법으로 수를 표현한다.
var testFloat = 0.0000006533;
console.log(testFloat); //6.533e-7


위와 같이 다양한 방식으로 선언되고 어싸인될 수 있는데, 몇가지 피해야할 방식들이 있다. ECMAScript에서 정수형은 32bits로 소수형은 64bits 로 표현되는 만큼, 소수형을 표현하는데는 정수형의 2배에 달하는 메모리를 사용해야 한다. 이러한 이유로 ECMAScript는 제대로된 형식이 아닌 소수형 수들은 무조건 integer로 인식 32bits 형식으로 저장하게 된다.

우선 안 좋은 예제 1은 작동은 하나, 최대한 피해야할 방법이다. 몇몇 Javascript 엔진에 따라서는 에러가 뜰 수도, 또는 0이나 1로 변환되서 저장될 수도 있다.
안 좋은 예제 2 같은 경우는 제대로 완성되지 않은 숫자라, 3으로 자동 변환되서 저장된다.
안 좋은 예제 3 같은 경우에는 숫자 4.0가 정수형으로 변환되서 32bit 형식으로 저장된다.

소수형을 이용한 연산을 할 때 조심해야할건, 무슨 일이 있어도 var1 + var2 = 0.6 같은 소수형 비교는 하면 안된다는건데, 이 이유는 IEEE-754의 정확성에 있다.

IEEE-754 방식은 그냥 일반 수를 표현할 때는 소수점 아래로 17번째 자릿수까지 완벽하게 정확하지만, 사칙연산시에 그 결과값의 정확성이 매우 떨어지기 때문이다.


var var1= 0.2; //Double Precision시에 0.20000000298023224라는 값으로 저장된다.

var var2= 0.4; //Double Precision시에 0.4000000059604645라는 값으로 저장된다.

console.log(var1 + var2 == 0.6); //false값이 프린트된다

var var3= 0.6; //Double Precision시에 0.6000000238418579라는 값으로 저장된다.

console.log(var1 + var2 == var3); //false값이 프린트된다


위와 같은 경우
var1 + var2 는 0.6000000089406967라는 결과를 도출하게되고, 0.6이라는 값(메모리내에는 0.6000000238418579라는 값으로 저장) 과 일치하나는 조건에서 false(거짓)값을 가지게 된다.
그러니 소수형 수의 연산값을 이용한 조건문은 절대로 쓰지 않도록 하자.

표현할 수 있는 수의 범위와 무한(Infinity) 값

ECMAScript에서 Number 자료형을 표현할 때 사용하는 비트수에 제한이 있다보니, 표현할 수 있는 수가 무한하지가 않다. 
최대로 표현가능한 수와 최소수는 아래와 같이 확인이 가능하다.


console.log(Number.MAX_VALUE); //양수의 최대값 
console.log(Number.MIN_VALUE); //양수의 최소값


만약 이에서 더 커지거나 작아지면 IEEE-754로 표현하는 한계를 넘으면 그 수는 Infinity 로 표현된다


console.log(Number.MAX_VALUE + Number.MAX_VALUE); //Infinity
console.log(- Number.MAX_VALUE - Number.MAX_VALUE); //-Infinity


그리고 Infinity 값은 Infinity를 제외한 다른 수와의 어떤 연산에서도 Infinity 값을 결과로 도출한다.
참고로 Infinity 값은 아래와 같이 불러올 수 있다.


console.log(Number.NEGATIVE_INFINITY + Number.POSITIVE_INFINITY); //NaN
console.log(Number.NEGATIVE_INFINITY + Number.MAX_VALUE); //-Infinity
console.log(Number.POSITIVE_INFINITY - Number.MAX_VALUE); //Infinity


NaN 값 이란?


간단하다. Not a Number 의 약자로 연산의 결과가 수가 아닐때 사용된다.
-Infinity + Infinity, 3/0 와 같이 결과가 숫자로 도출될 수 없을 떄 사용된다.


console.log(Number.NEGATIVE_INFINITY + Number.POSITIVE_INFINITY); //NaN
console.log(NaN + 3);//NaN이 포함된 연산은 언제나 결과가 NaN이다.

console.log(NaN == NaN); //false
//NaN값은 본인을 포함한 어떠한 값과도 Equal하지 않는다. 이러한 이유로 ECMAScript 에는 isNaN이라는 function이 있다

console.log(isNaN(NaN)); //true


이 isNaN() function 은 주어진 파라미터를 Number 자료형으로 변환 시도를 해서, 성공적으로 변환이 되면 false 를 아니라면 true 값을 리턴하는 함수이다.
그러니 ECMAScript 의 자동변환으로 Number 자료형으로 변환될 수 있는 경우에는 false 값이 리턴된다.


console.log(isNaN(NaN)); //true 
console.log(isNaN(1)); //false 
console.log(isNaN("1")); //false 
console.log(isNaN("test")); //true
console.log(isNaN(true)); //false


타 자료형을 Number 자료형으로 변환시 

자바스크립트(ECMAScript)는 Number(), parseInt(), parseFloat() 함수등을 이용해 타 자료형을 Number 자료형으로 변환 할 수가 있다. 변환 값은 아래 표를 참고하자

Number() 함수를 사용해 타 자료형을 변환시



var num1 = Number("String");
var num2 = Number(true);
var num3 = Number(null);
var num4 = Number(undefined);
var num5 = Number(NaN);
var num6 = Number(new Object());


자료형
변환시 Number 값
01NaN숫자
Booleanfalsetrue해당 사항 없음해당 사항 없음
Undefined해당 사항 없음해당 사항 없음undefined해당 사항 없음
Nullnull해당 사항 없음해당 사항 없음해당 사항 없음
Number01NaN모든 숫자들
String"0" or """1","01""TEST", "0Tx34",등 다른 조건에 부합하지 않을 때따옴표 사이에 숫자밖에 없을 때 자동으로 수로 변환(16진수도 10진수로)
Object해당 사항 없음해당 사항 없음모든 object 타입해당 사항 없음


String 자료형의 Number 자료형으로의 변환에 대해 짧게 설명하자면, 

"0", "11", "055" 와 같이 스트링의 따옴표 사이에 숫자 밖에 없다면, 무조건 동일한 Number 값으로 변형된다. 숫자의 맨 앞에오는 0은 생략되고, 만약 따옴표안에 "0xAB"와 같이 16진수 수가 있다면 자동으로 10진수로 변환된다. 

Empty String, 빈 스트링 값 같은 경우에는 무조건 0으로 변환되고, 이를 제외한 모든 상횡에서는 다 NaN값으로 변환된다.

parseInt() 함수를 사용해 타 자료형을 변환시

parseInt() 함수는 Number 함수와 String 자료형 변환을 제외하고는 모두 똑같은 변환값을 가진다. 하지만 String 값의 경우에 캐릭터가 들어간 모든 String을 NaN 값 으로 변환하는 Number와 달리 첫자리가 숫자라면, 이어지는 숫자들까지 모두 Number 자료형(정수)으로 변환한다. 또한, 파라미터에 radix 를 설정해줄 경우에, 주어진 스트링을 2진수, 8진수, 16진수, 10진수로 인식하는것을 설정할 수도 있다

var num1 = parseInt("String");
var num1 = parseInt(true);
var num2 = parseInt(null);
var num3 = parseInt(undefined);
var num4 = parseInt(NaN);
var num5 = parseInt(new Object());
var num6 = parseInt("1110",2); //1110을 2진수로 인식, 10진수 14로 변환한다
var num7 = parseInt("17",8); //17을 8진수로 인식, 10진수 15로 변환한다
var num8 = parseInt("A3",16); //A3을 16진수로 인식, 10진수 163으로 변환한다
var num9 = parseInt("333",10); //10진수로 인식한다


자료형
변환시 Number 값
01NaN기타
Booleanfalsetrue해당 사항 없음해당 사항 없음
Undefined해당 사항 없음해당 사항 없음undefined해당 사항 없음
Nullnull해당 사항 없음해당 사항 없음해당 사항 없음
Number01NaN모든 숫자들,(소수일때 정수자리만 변환)
String"0" or """1","01""TEST", "Tx34",등 다른 조건에 부합하지 않을 때앞자리들이 숫자일 때는 앞자리들을 수로 변환("43TX8" -> 43)
만약 16진수라면 10진수로 변환("0xApp" -> 10)
Object해당 사항 없음해당 사항 없음모든 object 타입해당 사항 없음



parseFloat() 함수를 이용해 타 자료형을 변환시

parseFloat() 함수는 parseInt() 함수와 모든게 같으나, 32bits 정수형으로 변환하는 parseInt()함수와 달리 String 자료형 변환에서 소수형 수를 발견할 때 64bits 소수형으로 변환한다. 만약 정수형수라면 32bits 정수형으로 변환

var num1 = parseInt("String");
var num1 = parseFloat("0.44TQG"); //0.44
var num2 = parseInt("32BB"); //32(O), 32.0(X)

2015년 1월 26일 월요일

[JavaScript] 자바스크립트 Undefined 와 Null의 차이

Undefined Type


자바스크립트의 Undefined 타입은 값이 1개밖에 없다. 바로 'Undefined' 단 하나이다.
이 Undefined 라는 값은 변수가 정의되지 않았다는것을 의미하는데, 가장 쉽게 이 값을 얻는 방법은 var 키워드를 이용해 변수를 선언하고 초기화 하지(값이 어싸인되지 않았을 때) 않는 것 이다.


var testVar;
console.log(testVar);//undefined 가 프린트 될 것이다.
console.log(typeof testVar);//undefined 가 프린트 될 것이다.


ECMAScript 는 Primitive Data Type(원시 자료형) 5개, Composite/Reference Data Type(객체) 1개, 총 6개의 자료형을 가지고 있는데 undefined 는 Primitive Data Type 중 하나 이며, 저 5개의 Primitive Data Type(원시 자료형)에 포함되지 않는 값을 나올 때 있을 때 자동으로 undefined 값이 된다.
물론 변수에 undefined 값을 어싸인해주는 것도 가능하다


var undefinedVar = undefined;
console.log(undefinedVar);//undefined 가 프린트 될 것이다.
console.log(typeof undefinedVar);//undefined 가 프린트 될 것이다.


하지만 ECMAScript에 undefined 라는 자료형이 추가된 것은 단순히 변수 값들의 비교 작업을 수월히 하기 위해서이니, 위와 같이 변수 값에 undefined를 어싸인해주는 것은 자제하도록 하자.
그리고 또 하나 알아둬야 할 것은, 자바스크립트에서 변수생성은 변수 선언(Variable Declaration)에 의해 이루어지니 선언된적 않은 변수들은 절대로 undefined 값을 가지지 않는다.


var undefinedVar;//세미콜론(;)으로 선언을 완료했다.
console.log(undefinedVar);//undefined 가 프린트 될 것이다.
console.log(undeclaredVar);//Uncaught ReferenceError: undeclaredVar is not defined 에러를 보게될것이다


Null Type


Null 타입은 Undefined 타입과 같이 값이 null 1개 밖에 없다. Null 타입과 Undefined 타입의 차이점은 undefined 타입이 Primitive Data Type(원시 자료형)에 사용되는 자료형이고, null 타입은 Complex Data Type(복합 자료형), 즉 Ojbect(오브젝트)에 사용되는 자료형이라는건데... 즉 이론적으로 Null 타입은 Empty Object를 가리키는 포인터인데, 이 때문에 null 값을 가진 변수나 null 값에 typeof 연산자를 사용하게 되면, object 라는 결과가 나온다.


var t = null;
console.log(typeof t);//object 가 프린트 될 것이다
console.log(typeof null);//object 가 프린트 될 것이다


참고로 undefined 값은 null 값의 하위 타입이라 == 연산자를 이용해 비교하게되면, true 값이 나온다.



console.log(undefined==null);//true 값이 나온다.



그렇다면 이 null이라는 자료형을 어디에 써먹어야 하는가, 간단하다.
추후에 필요한 object 타입의 변수를 미리 생성해 놓아야할 때


var t = null;
if(t==null){
t = loadbook();
}


또는 Empty Object 가 필요한 작업에


var book = null;
book = loadBook()
if(book==null){
alert("책을 로드하는데 실패했습니다.");
}


요렇게들 사용하면 된다.

2015년 1월 24일 토요일

[Eclipse] 이클립스에서 Node.js 개발 환경 세팅하기

Node.js 로고
Node.js 로고
자바스크립트(JavaScript) 개발을 하다 보면 제대로 된 디버거가 없어서 alert 나 console 을 사용해서 웹브라우져의 개발자 도구 콘솔에 프린트 하거나 팝업을 띄우기 마련인데, 이런 방식은 쉴틈없이 새로고침을 해줘야 해서 귀찮기 마련이다. 그러니 이클립스Node.js 를 이용해서 이클립스에 자바스크립트 콘솔을 세팅해보도록 하자.

우선 Eclipse 를 켜서 하고 메뉴에서 Help->Install New Software를 클릭하면 아래와 같은 창을 보게 될 것이다.

이클립스 부가 소프트웨어 설치 스크린
이클립스 부가 소프트웨어 설치 스크린

노란색으로 강조해 놓은 옵션 박스에서, 본인의 이클립스 버젼을 선택한 후에, 아래의 이클립스 확장들을 설치해 준다.
  • JavaScript Development Tools 
  • Eclipse Web Developer Tools 

그리고 이곳[http://nodejs.org/]에서 Node.js 인스톨러를 다운 받아 설치해준다.
설치 후에 시스템 속성에 들어가 환경변수 설정에서 시스템 변수를 등록 해주자.

Node.js 윈도우 환경 변수 등록

나 같은 경우는 위와 같이 등록해줬다. node.js 설치시 기본값으로 설치했다면 변수 값을 나와 같이 하면 된다. 그리고 본인의 변수 이름을 잘 기억하도록 하자.

그리고 다시 Eclipse 로 돌아가서 메뉴에서

Run -> External Tools -> External Tools Configuration
외부 도구 설정으로 들어가자


Eclipse 외부 도구 설정

위의 이미지에 1 Javascript라 적힌건 무시하자, 내가 이미 설정해 놓은게 있어서 저렇게 나오는거니까.

그리고나서 저걸 클릭하면 요런 창을 보게 되는데



노란색으로 칠해놓은 새로만들기 버튼을 누르면




이런 창을 보게 된다. 여기서 Location, Working Directory, Arguments를 저렇게 적어주자.

만약 환경변수 설정시에 변수 이름을 node 로 하지 않았다면 Arguments의

/c "node ${resource_loc}" /c "환경변수이름 ${resource_loc}"

이렇게 적어주면 된다.

그리고나서 자바스크립트 프로젝트를 생성하고  console.log 를 이용 스크립트 작성 후 아래와 같이 External Tool을 클릭해서 방금 우리가 만든 설정을 이용하면





이렇게 이클립스 콘솔에 프린트 된다. 

2015년 1월 23일 금요일

[JavaScript] Keyword 들과 Reserve Words 란?

자바스크립트의 Keyword(키워드)란?


ECMA Script 는 Statement 를 시작하거나 끝낼 때, 특수한 기능을 수행할 때 등 특수한 목적을 위한 Keyword들을 가지고 있는데 이러한 키워드들은 특수한 목적을 두고 있으니 사용이 제약된다. 특히 keyword 는 코드 작성시 변수 이름이나 함수 이름, 그리고 property 이름에 사용할 수 없으니 피해 가도록 하자. 만약 사용할 경우에는 'Identifier Expected' 라는 에러를 보게 될 것이다.

do
break 
do 
instanceof 
typeof 
case 
else 
new 
var 
catch 
finally 
return 
void 
continue 
for 
switch 
while 
debugger
function
this
with
default
if
throw
delete
in
try


자바스크립트의 Reserve Word(예약 키워드)란?


위에서 설명한 단어들이 현재 사용되고 있는 키워드라면 Reserve Word는 미래에, 즉 다음 ECMA Script 버젼에 사용될 확율이 높아 사용하지 않는게 좋은 키워드들 이다. 이 또한 변수 이름이나 함수 이름에 사용하지 말도록 하자. Reserve word 같은 경우에는 변수/함수 이름에 사용하는거에 제약이 있으나, property 이름에 사용하는데는 제약이 없다. 하지만 추후 코드 관리를 위해서 사용을 최대한 피하도록 하자


//Non-Strict 모드(일반 모드)에서도 사용시 에러를 보게되는 키워드들
class
enum
extends
super
const
export
import

//Strict 모드에서 사용이 제한되는 키워드들
implements
package 
public
interface
private
static
let
protected
yield

2015년 1월 22일 목요일

[JavaScript] Strict Mode를 사용해야 하는 이유

JavaScript 의 모체인 ECMAScript 는 C와 C를 이은 언어들, JAVA, C++ 등의 문법적인 요소들을 많이 이어 받아 비슷한 점들이 매우 많다. 하지만 그와 다른점이 있다면 몇몇 문법적인 요소들을 사용자의 자유에 맞기고 그리 철저하게 강요하지 않는다는건데, 만약 제대로된 문법을 지키지 않고, 단지 에러가 나지 않는다는 이유로 엉망진창인 프로그래밍하게되면 ECMAScript Core 가 새 버젼으로 바뀌게 될 경우에 큰 문제를 마주치게 될 수도 있다.

ECMA 스크립트는 버젼이 바뀌면서 새로운 기능들과 요소들을 추가하게 되는데 만약 당신이 이러한 요소들을을 고려하지 않고 미래에 쓰일 Identifier들이나 키워드들을 지금 당장의 편의를 위해서 사용해버리면 추후에 많은 에러를 양산하게 될 수도 있고 결국 이는 모든 코드의 재 검사, 재 작성으로 이어지게 된다.

또한, 웹브라우져들은 각각 다른 내장 자바스크립트 엔진을 사용하는데
Mozila Firefox = SpiderMonkey
Google Chrome = V8
Internet Explorer = Chakra
이런 엔진에 따라 인터넷 익스플로러에서 작동하는 코드가 다른 브라우져에서 작동하지 않는 경우가 발생할 수도 있다. 문제는 개발환경이 매우 다양한 자바스크립트 개발과정에서 이러한 기준을 정한채 개발하는게 초보 개발자들에게는 어렵다는건데,

이러한 이유에서인지 ECMAScript 5에 들어서 Strict mode 라는게 생겼다. 이 Strict Mode는 코드 컴파일시 ECMA Script의 문법 요소들과 Reserved Keyword 들의 미사용을 철저하게 강요해 일반 실행 모드보다 더 많은 예외(Exception)들을 발생시키게하여 궁극적으로는 안전한 자바스크립트 코드를 작성하는데 목적을 두고 있다.

Strict Mode 는 아래와 같이 실행이 가능하다.

"use strict";//이 컨텍스트에서 스트릭트 모드를 사용한다

function testFunction()
{

"use strict";
//이 컨텍스트에서 스트릭트 모드를 사용한다. 후에 이 function 실행이 종료되면 strict mode도 종료된다.

alert("STRICT MODE");

}

아래는 브라우져들의 Strict Mode를 지원 현황이다.  초록색으로 표시된 버젼들이 모두 지원하는 버젼들이니, 거의 대부분의 브라우져들이 지원한다고 보면 된다. 클릭하면 크게 볼 수 있다

출처: http://caniuse.com/#search=strict%20mode


Strict Mode는 거의 대부분의 브라우져들이 지원하니 코드 작성시에 strict mode 를 사용해서 안전한 자바스크립트 코드를 작성하자.

2015년 1월 19일 월요일

[JavaScript] HTML의 Script 태그, 그리고 Async와 Defer 속성

부제 : Script 태그의 Async 와 Defer 속성

HTML 파일에 자바스크립트를 삽입하는 유일한 방법은 아래와 같이 HTML의 스크립트 태그를 이용하는거다. 자바스크립트를 시작하기 전에 Script 태그에 대해서 좀 자세하게 다뤄볼까 한다.

우선 Script 태그는 아래와 같이 사용된다

<html>
<head>
<script>
alert("Script Tag");
</script>
</head>
<body>
This is Body
Body End
<script src = "www.example.com/js/script.js"></script>
</body>
</html>

위와 같이 Script 태그는 어디든지 배치 될 수 있으며 위에서 아래로 HTML 문서를 읽는 브라우져들의 특성상, head 태그에 외부 스크립트가 배치 될 경우에는 페이지 렌더링(rendering)이 시작되기 전에 head 태그에 배치된 스크립트가 다운로드되고, 파싱(Parsing)되고 실행되게 된다. 만약 상당히 큰 스크립트 파일을 head 태그에 배치하게 될 경우에, body 렌더링이 시작되기전에 스크립트를 실행하는데 많은 시간을 할애 할 수 있다. 하지만 body 태그의 마지막에 스크립트 태그를 배치하게 되면, html 페이지의 body 내용이 다 렌더링(rendering)된 후에으로써 스크립트를 다운받기 시작하니 사용자 입장에서 보이는 페이지 로딩시간을 줄일 수 있다.

주의할 점
위에서 아래로 읽히는 HTML 문서의 특성상 스크립트 태그 안에 "</script>", 스크립트 엔드 태그가 존재할 경우에 태그를 닫게 된다. 아래 예제를 보자

<html>
<head>
<script>
var a = "</script> end tag test";//스크립트가 여기서 끝나게 되버려 alert 가 실행되지 않는다
alert(a);
</script>
</head>
<body>
This is Body
<script>
var t = "<\/script>";// '/'(Slash)를 표시하는 escaped character 인 '\/'를 이용하자
alert(t);
</script>
</body>
</html>

위와 같이 자바스크립트에서 스크립트 언어에 사용되는 기호들을 String 값으로 표현할 때, Escape Character 를 이용하여 표시한다. Slash(/) 를 표시하는 기호인 '\/'를 이용해서 "</script>"를 스트링값으로 저장할 수 있다.

Script 태그의 Attribute

Script 태그는 총 5개의 Attribute 를 가진다. 필수적인 Attribute 은 가지지 않는다

  • async
    • 외부 스크립트의 다운로드가  페이지 파싱이나 다른 스크립트 다운로드 프로세스와 동시에 진행된다. 그리고 스크립트 다운로드가 완료되는 즉시 바로 실행된다
  • charset
    • UTF-8, euc-kr 과 같은 스크립트의 Character set를 지정한다
  • defer
    • 외부 스크립트의 다운로드가  페이지 파싱이나 다른 스크립트 다운로드 프로세스와 동시에 진행된다. HTML 페이지 파싱이 완료된 후에서야 스크립트가 실행된다
  • src
    • 외부 스크립트를 다운로드할 주소
  • type
    • 스크립트의 종류
    • javascript 의 경우에는 type = "text/javascript"로 적는다.

async 속성과 defer 속성

위에 잠시 이야기했듯이, 기본적으로 웹 브라우져는 html 코드를 위에서 아래로 파싱(Parsing)한다. 이 때문에 큰 스크립트 파일같은 경우에, 그 배치 위치에 따라 사용자 입장에서의 페이지 로딩 타임이 길어질 수도, 짧아질 수도 있는데, 이를 조정하기 위해서 나온게 async 와 defer 속성이다.

아래와 같이 쓰인다

<html>
<head>
<script async src = "www.example.com/js/script.js"></script>
<script defer src = "www.example.com/js/script.js"></script>
</head>
<body>
This is Body
Body End
</body>
</html>


Script 태그 async 속성과 defer 속성
Script 태그 async 속성과 defer 속성

위의 이미지를 보자

일반적인 스크립트 태그 같은 경우에는  html 파싱(Parsing) 중, 스크립트 태그를 읽게 되면 잠시 파싱을 멈추고 스크립트를 다운받아 실행한 후에 다시 파싱 작업을 이어간다. 이 경우에, html 태그의  앞부분에 스크립트 태그를 배치하게되면(특히나 헤드 태그 내에) 페이지 렌더링이 시작되기도 전에(페이지 렌더링은 body 태그의 시작과 함께 시작된다) 스크립트를 다운로드하고 실행하는데 시간을 할애하게 된다. 사용자의 입장에서 생각해봤을 때, 당신의 웹 페이지를 보는 사용자는 스크립트가 다운로드 되는 동안 텅빈 하얀 페이지를 보고만 있어야 한다. 물론 짧은 스크립트일 때는 이 시간은 극히 짧으니 그리 신경 쓸 필요가 없다, 그렇지만 만약에 인터넷 커넥션이 느리거나 사이즈가 큰 스크립트를 다운받는다면 아마 사용자는 긴 시간동안 페이지 로딩을 기다려야 할 것이다. 이러한 문제들을 해결하기 위해서 HTML5 에 들어 async 속성과 defer 속성이 추가되었다

Async 속성을 가진 스크립트 태그 같은 경우에는 HTML 파싱과 동시에 스크립트 다운로드가 진행된다. 그리고 스크립트 다운로드가 완료되는 순간 HTML 파싱을 잠시 멈추고 스크립트를 실행한다. 이러한 특성 때문에 순서대로 다운로드가 시작된 스크립트라도 순서대로 실행되지는 않는다. 아래 예제를 보자

<html>
<head>
<script async src = "www.example.com/js/script1.js"></script>
<script async src = "www.example.com/js/script2.js"></script>
//script2가 script1 보다 먼져 실행될 수도 있다.
</head>
<body>
This is Body
Body End
</body>
</html>

이러한 이유로 DOM(Document Object Model)을 수정하는 스크립트 같은 경우에는 async 속성을 사용하지 않는게 좋다.

Defer 속성을 가진 스크립트 태그 같은 경우에는 HTML 파싱과 동시에 스크립트 다운로드가 진행된다. 그러나 async 속성과는 달리 HTML 파싱이 완료된(</html> 태그를 읽은 후) 후에야 스크립트가 실행된다.  아래의 예제를 보자

<html>
<head>
<script defer src = "www.example.com/js/script1.js"></script>
<script defer src = "www.example.com/js/script2.js"></script>
//script1가 script2 보다 먼져 실행된다
</head>
<body>
This is Body
Body End
</body>
</html>

스크립트 태그가 헤드 태그 내에 위치해 있으나 HTML 파싱을 멈추지 않고 바로 다운로드가 진행된다. 그리고 </html> 엔드 태그를 읽은 후에야 스크립트를 실행하게 된다. 그리고 async 태그와는 달리 스크립트는 HTML 문서 내에 위치한 순서대로 실행 된다. 그러니 위의 예제에서는 html 문서 파싱이 완료된 후에 script1.js 가 실행되고 그 후에야 script2.js 가 실행된다.

async 속성이나 defer 속성이든 둘다 외부 스크립트 파일에만 적용이 가능한 속성이니 내부 스크립트에 쓰는 일은 없도록 하자

noscript 태그

요즘은 자바 스크립트를 지원하지 않는 웹 브라우져를 찾을 수가 없지만, 초기에만 해도 자바스크립트가 지원되지 않던 브라우져들이 존재 했었다. 그럴 경우를 위해서 나온게 바로 noscript 태그 이다. 사용법은 간단하다. 

<html>
<head>
<title>NOSCRIPT TAG EXAMPLE</title>
</head>
<body>
<script src = "www.example.com/script.js"></script>
<noscript>
<h1>자바스크립트 기능을 활성화 해 주세요</h1>
</noscript>
</body>
</html>


만약 자바스크립트 실행이 비활성화 되있다면(또는 자바스크립트 기능이 없거나) noscript 태그 내의 html이 파싱된다. 웹브라우져 개발자 도구를 들어가서 자바스크립트를 비활성화 시킨 다면 "자바스크립트 기능을 활성화 해 주세요" 구문을 보게 될 것이다

2015년 1월 13일 화요일

JPG, PNG, GIF 이미지 파일들의 특징과 차이

JPG 이미지 파일의 특징

  • 사진과 같은 다양하게 연결되는 톤을 가진 이미지에 알맞은 포맷이다. 
  • JPG는 약 160만개에 달하는 색들을 표현할 수 있다.
  • 사이즈를 줄이기 위해서 이미지 정보를 삭제하기 때문에 손실률이 높은 포맷이다.
  • 투명도를 지원하지 않는다
  • 에니메이션을 지원하지 않는다

PNG 이미지 파일의 특징


  • 몇가지 색으로만 이루어지거나, 선들로 이루어진 이미지들, 예를 들어 로고, 클립 아트 그리고 텍스트 이미지를 표현하는데 알맞다.
  • PNG는 약 백만개에 달하는 색들을 표현할 수 있고, 종류에 따라 표현할 수 있는 색의 갯수를 달리한다. 예)PNG-8, PNG-24, PNG-32.
  • PNG포맷 또한 JPG 와 같이 사이즈를 줄이는 포맷이나 이미지의 정보를 삭제하지는 않는다. 그렇기 때문에 "lossless"(무손실) 포맷이라 불리고는 한다. 
  • 투명도를 지원한다.
  • 대부분의 경우에 같은 이미지를 표현하는 JPEG 파일보다 사이즈가 더 크다, 
  • GIF 와 비교했을 때 사용되는 색의 갯수에 따라 사이즈가 더 작거나 크거나 한다.


GIF 이미지 파일의 특징


  • PNG, GIF 와 같은 이미지 포맷들은 로고, 클립아트, 텍스트 이미지와 같이 적은 색들로 이루어졌거나 선들로 이루어진 이미지들을 표현하기에 적합하다.
  • GIF는 약 265개의 색들을 표현 가능하다.
  • GIF 또한  PNG와 같이 "lossless", 즉 무손실 포맷이다.
  • GIF는 투명도를 지원한다, 하지만 이미지당 색 1개만 투명 설정이 가능하다.
  • 대분의 경우에 같은 이미지를 표현하는 JPEG 파일보다 사이즈가 더 크다.
  • 애니메이션을 지원한다

2015년 1월 12일 월요일

[JavaScript] 자바스크립트란 무엇인가?

부제 : ECMAScript와 자바스크립트


비공식 자바스크립트(Javascript) 로고


자바스크립트(Javascript)는 1995년 넷스케이프(Netscape) 웹 브라우져에서 웹페이지에 동적인 요소를 구현하기 위해서 발명 되었다. 그 후 많은 다른 웹 브라우져들 또한 이 언어를 탑재하기 시작했고, 그 결과로 현대의 웹 어플리케이션의 구현을 가능하게 만든 언어이다. 이 언어로 인해 웹 어플리케이션에서 더 이상 사용자가 페이지 새로고침 또는 페이지를 새로 불러오지 않고도 웹과 직접적인 연결이 가능하게 되었다.


우선 자바스크립트(Javascript)를 시작하기 전에 처음 알아야 할 것은 이 자바스크립트(Javascript)라는 언어는 Sun System이 개발하여 지금은 Oracle에서 관리되고있는 자바(Java)라는 프로그래밍 언어와는 전혀 관계가 없다는 것이다. 둘다 자바(Java) 라는 단어를 이름에 가지고 있으니 비슷해 보일 수도 있겠지만, 전혀 그렇지 않다. 몇몇 소스들에 따르면 이 자바스크립트(Javascript)라는 이름은 자바(Java)의 유명세를 등에 업기 위해서 이리 이름 지어졌다고도 한다. 자바스크립트(Javascript)가 처음 나왔을 때는 1995년, 바로 자바(Java)라는 프로그래밍 언어가 유명세를 타며 세상을 휩쓸고 있을 때였다. 아마 이 유명세를 등에 업으려 그렇게 한게 아닐까?


어쨋든, 자바스크립트(Javascript)가 넷스케이프(Netscape) 브라우져만이 아니라 다른 웹 브라우져들의 지원까지 받기 시작하면서 다양한 웹 브라우져에서 자바스크립트(Javascript)가 공통되게 잘 작동하기 위해서 표준 규격이 필요해졌는데, 이 때문에, ECMA 국제 기구에서 "ECMAScript Standard"라 불리는 스크립트 표준이 만들어지게 된다. 자바스크립트와 비슷한 뜻으로 많이 들어본 사람들이 있을텐데, Javascript는 ECMAScript와 BOM(Browser Object Model) 와 DOM(Document Object Model)이라는 1개의 코어와, 2개의 모델로 이루어져 있다. ECMAScript 와 Javascript 는 비슷한 뜻으로 자주 쓰이나 작은 차이를 가지고 있다는 걸 알아두자.

앞서 말했듯 흔히 우리가 자바스크립트(Javascript)라 부르는 것은 정확히 말하면 3가지가 합쳐서 만들어진것인데 그것들은 바로 ECMAScript 와 DOM(Document Object Model) 와 BOM(Browser Object Model) 이다.

ECMAScript는 자바 스크립트를 이루는 코어(Core) 스크립트 언어로, 웹 환경에서만 호스트 되는 언어가 아니다. 웹 환경은 ECMA 스크립트가 호스트되는 환경들 중 하나일 뿐이다. EMCA 스크립트 호스트 환경은 ECMA 스크립트 실행 환경이 구현되있고, 각각 그 환경에 알맞는 확장성을 가지고 있다. 예를들어 웹 브라우져 환경에서는 BOM(Browser Object Model)과 DOM(Document Object Model)이 그 확장성이 되겠다. 이러한 확장성들은 EMCA 스크립트의 문법과 기능에 맞춰 기능의 확장을 가능게 한다. 자바스크립트의 document 객체가 좋은 예이다. 다른 호스트 환경으로는 node.js, Adobe Flash, MongoDB, CouchDB  등이 있다

ECMA 스크립트는 기본적으로 언어의
  • 문법(Syntax)
  • 데이터 타입(Type)
  • 구문(조건문, 반복문 등)(Statement)
  • 키워드(Keyword)
  • 예정 키워드(Reserved Word)
  • 연산자(Operator)
  • 객체(Object)
등을 규정짓는다. 이는 어떤 ECMA 스크립트 호스트 환경에서든 동일하다.

자바스크립트(Javascript)의 코어 스크립트인 ECMAScript 에는 몇가지 버젼들이 있는데, 2000년부터 2010년까지는 "ECMAScript 버젼 3"이 가장 대중적으로 지원되었다. 그리고 이 동안 언어에 근본적인 변화, 발전, 그리고 확장을 꾀한다는 야심을 가지고 "ECMAScript 버젼 4"의 개발이 진행되었다. 매우 대중적으로 쓰이고, 거의 모든 웹에서 쓰이는 언어를 바꾼다는게 쉽지는 않았는지, 원래 2008년 발표로 계획되었던 "ECMAScript 버젼 4"는 2008년에 엎어져 버렸고(ECMAScript Harmony(버젼 6)라는 다른 프로젝트로 이름을 바꿨다, 현재 진행 중), "ECMAScript 버젼 5"라는 이름으로 원래 계획된 거에는 미치지 못하지만 그래도 작은 발전을 가진 다섯번째 ECMAScript 에디션이 발표되었다. 참고로 내가 앞으로 포스트 할 자바스크립트가 바로 요즘 잘 쓰이고 있는 "ECMAScript 버젼 5"이다. 현재 "ECMAScript 버젼 6", 즉 버젼 4에서 엎어졌던 기능들을 이어가는 "ECMAScript Harmony" 프로젝트가 거의 완성단계에 있으며, 몇몇 웹 브라우져들은 미리 발표된 기능들을 지원하기도 한다.  어쨋든  "ECMAScript 버젼 6"은  2015년 6월 발표를 앞두고 계속 개발되고 있는 중이다.

이 ECMAScript 언어는 다른 언어에 비해 매우 높은 자유도를 가졌는데. 이는 왜냐하면 초기 자바스크립트(Javascript)가 초심자들의 접근을 용이하게, 더 쉽게 하는데 목적을 두고 개발된 언어이기 때문이다. 하지만 실제 개발 상황에서는, 시스템이 문제가 뭔지 제대로 알려주지 않아 개발을 더 어렵게 만들기도 한다. 그렇지만 이런 자유도에 따라오는 몇가지 장점들이 있는데, 그건 바로 자유도가 낮은 다른 프로그래밍 언어들이 구현하기 거의 불가능한 기능들을 자바스크립트(Javascript)로 구현할 수 있다는것이다. 이러한 이유에서 ECMA 스크립트는 몇년전 부터 소프트웨어 산업에서 많은 관심을 받고 있다.

2015년 1월 11일 일요일

[자료 구조] 힙(Heap)

자바(Java)예제로 구현한 힙(Heap) 자료 구조

힙(Heap) 이란 무었인가?

힙(Heap)은 완전 이진 트리(Complete Binary Tree)로, 각각의 노드가 자신의 부모 노드보다 작거나 같은 값을 저장하는 자료형 이다. 힙(Heap)은 완전 이진 트리(Complete Binary Tree)라 가장 아래에 있는 노드들을 제외한 모든 노드들이 두 자식 노드를 모두 가지고 있거나 아예 자식 노드를 가지지 않는 특성을 가진다.
  • 만약 부모 노드가 자식 노드보다 크거나 같다면 그건 "Max Heap"(최대 힙)
  • 부모 노드가 자식 노드보다 작거나 같다면 "Min Heap"(최소 힙) 이라 불린다.
힙(Heap) 컨셉
힙(Heap) 컨셉

힙(Heap)은 실제로 어디에 사용될까?

  • Heapsort(힙 정렬)
  • 우선 순위 큐(Priority Queue)
    • 힙 자료 구조는 우선 순위 큐를 구현하는데 많이 쓰인다
  • 다양한 알고리즘(Algorithm) 구현

이진 힙(Binary Heap) 은 어떻게 구현되는가?

추상 자료형인 힙(Heap)은 매우 다양한 방법으로 구현될 수 있다. 가장 대중적인 힙 구현 방법은 Array를 이용하는 것이다. 우선 아래의 Big O 복잡도 표를 보고 가자

OperationBig O Complexity
InsertO(log n)
Remove MaxO(log n)
Fix RootO(log n)

*중요한건, Array 를 이용한 이진 트리 구현에서, 인덱스 i 에 저장된 부모 노드의 두 자식 노드는 인덱스 (2*i)+1 와 (2*i)+2에 저장된다는걸 기억하자.

아래는 자바 배열(array)로 구현한 힙(Heap) 자료 구조 이다.


public class Heap {
 private int[] data;
 private int size;
 private int maximumSize;

 public Heap() {
  data = new int[100];
 }

 public static void main(String[] args) {
  int[] arr = new int[5];
  for (int i : arr) {
   System.out.println(i);
  }
 }

 public Heap(int maximumSize) {
  if (maximumSize < 1) {
   this.maximumSize = 100;
  } else {
   this.maximumSize = maximumSize;
  }
  this.maximumSize = maximumSize;
 }

 public boolean isEmpty() {
  return size == 0;
 }

 public boolean isFull() {
  return size == 100;
 }

 public void clear() {
  data = null;
 }

 // 새로운 데이터를 삽입
 public void insert(int newInt) {
  int pointer;// 어레이의 인덱스를 가리키는 포인터 이다.
  if (isFull()) {
   throw new FullHeapException();
   // 힙이 꽉 차있다면 Exception(예외) 처리를 해주자
  } else {
   // 아니면 배열의 끝에 새로운 데이터를 삽입한다.
   data[size] = newInt;
   pointer = size;
   size++;

   while (pointer > 0 && data[pointer] > data[(pointer - 1) / 2]) {
    // 최대 힙에서 자식 노드는 무조건 부모 노드보다 작거나 같아야한다
    // 그러니 끝에 삽입된 노드를 부모 노드와 비교해서 크다면 부모 노드와 교체해주자
    int temp = data[pointer];
    data[pointer] = data[(pointer - 1) / 2];
    data[(pointer - 1) / 2] = temp;
    pointer = (pointer - 1) / 2;
   }
  }
 }
 
 // 힙에서 노드를 제거
 // 힙에서 제거 메소드는 가장 큰 노드 1개, 즉 루트 노드를 제거하고 반환한다.
 public int remove() {
  int toReturn;//리턴될 인스턴스
  if (!isEmpty()) {
   toReturn = data[0];
   // 어레이의 가장 끝에 존재하는 노드를 루트 노드에 집어넣는다
   data[0] = data[--size];
   data[size] = 0;
  } else {
   // 만약 힙이 텅 빈 상태라면 예외 처리를 해주자
   throw new EmptyHeapException();
  }

  // 어레이의 가장 끝에 있는 노드를 루트 노드에 넣었으니, 힙을 재정렬 해야한다.
  fixRoot();//재정렬 메소드를 실행하자

  return toReturn;//toReturn 인스턴스에 저장된 값을 반환한다.

 }

 public void fixRoot() {
  // remove 메소드에서 가장 큰 노드,즉 루트 노드를 제거하고 그 자리에 가장 끝에 있는 노드를 삽입했다.
  // 다시 힙을 재정렬 함으로써 루트 노드가 적절값을 가지도록 해야한다.

  int pointer = 0;//루트 노드에서 시작한다
  while (pointer * 2 + 1 < size) {
   // 자식 노드중 더 큰 노드와 자리를 교체한다.
   if (data[pointer * 2 + 1] > data[pointer * 2 + 2]) {
    int temp = data[pointer];
    data[pointer] = data[pointer * 2 + 1];
    data[pointer * 2 + 1] = temp;
    pointer = pointer * 2 + 1;
   } else {
    int temp = data[pointer];
    data[pointer] = data[pointer * 2 + 2];
    data[pointer * 2 + 2] = temp;
    pointer = pointer * 2 + 2;
   }
  }
 }
}

2015년 1월 10일 토요일

[자료 구조] 이진 탐색 트리 (Binary Search Tree(BST))

자바 예제로 설명하는 이진 탐색 트리 (Binary Search Tree(BST))


이진 탐색 트리 예제
이진 탐색 트리 예제

이진 탐색 트리 (Binary Search Tree(BST)) 란?

이진 탐색 트리는 트리 자료 구조의 종류 중 1개로써, 각 노드가 최대 2개의 자식(Child) 노드를 가질 수 있는 트리이다. 이진 탐색 트리에서 새로운 노드는 루트 노드부터 비교를 거쳐, 비교된 노드 보다 더 크면 오른쪽 서브 트리로 이동하고, 작으면 왼쪽 서브 트리로 이동해서 계속 크기 비교 후, 알맞은 자리에 삽입된다. 위의 그림에서 3이라는 노드가 삽입될 때, 우선 루트 노드인 33 과 비교 후, 22와 비교 후, 22의 왼쪽 자식 노드로 삽입되는 것 이다.

이러한 특징 덕분에, 이진 탐색 트리(Binary Search Tree)를 중위 순회(Inorder Traversal)로 순회하게 되면, 정렬된 값을 읽을 수 있다. 위의 예제를 Inorder Traversal 로 순회한다면
[3, 22, 26, 33, 44 55, 77]
이 된다

이진 탐색 트리(Binary Search Tree) 는 어디에 쓰일까?

  • 이진 암호화
  • 데이터 베이스
  • 파일 시스템

이진 탐색 트리(Binary Search Tree)는 어떻게 구현되는가?

이진 트리는 추상 자료형이다, 이는 즉 매우 다양한 방법으로 구현될 수 있음을 의미한다. 보통 가장 자주 쓰이는 방법은 싱글 링크드 리스트(Singly Linked List)이다. 우선 아래에 적힌 이진 탐색트리의 Big O 복잡도를 보고 가자.

Operation Big O Complexity
Average Worst
InsertO(log n)O(n)
DeleteO(log n)O(n)
SearchO(log n)O(n)

큐(Queue)나 스택(Stack)과 같은 선형 자료 구조들과는 달리, 비선형 자료 구조에서 각각의 오퍼레이션들은 평균(Average)와 최악(Worst) 케이스이라는 두가지 케이스의 Big O 복잡도를 가진다. 이진 탐색 트리(Binary Search Tree)의 경우에 Average(평균) 케이스란 균형이 잘 맞는(Well-Balanced) 트리를 말하며, 최악의 케이스란 아래의 그림과 같은 형태를 띄어 선형 자료 구조와 다른게 없는 상황을 말한다. 아래 그림 예제를 보자.

이진 탐색 트리 최악의 경우
이진 탐색 트리 최악의 경우

만약 우리가 이진 탐색 트리에 데이터를 33,22,3 순으로 삽입하면, 위의 그림과 같은 구조를 볼 수 있을 것 이다. 이럴 경우에 이진 탐색 트리는 싱글 링크드 리스트와 완전 일치하며, 비선형 자료 구조의 장점을 잃게 된다.

이진 탐색 트리(Binary Search Tree), 왜 중복 노드를 가져서는 안되는걸까?

아래의 자바(Java) 예제 코드를 보면 알겠지만, 이진 탐색 트리(Binary Search Tree)는 매우 직관적이고 단순한 검색 알고리즘을 가지고 있다. 이진 탐색 트리에서 새로운 노드가 더 부모 노드보다 더 크면, 그 노드는 오른쪽에 위치하게 되고, 작으면 왼쪽에 위치하게 된다. 이러한 특성 때문에, 검색 알고리즘은 검색 쿼리와 노드 값을 비교해가며 노드의 위치를 찾아간다.

만약 중복값을 가진 노드가 존재한다 가정할 때, 우리는 두 가지 검색 알고리즘을 만들 수 있을것이다.

첫번째로, 우선 발견되는 노드만 신경쓰고, 중복 노드가 존재할 가능성을 무시하는것이다. 이 경우에 이진 탐색 트리(Binary Search Tree)는 아무런 쓸모가 없고 사용되지 않을 노드를 가지게 되는 것 이고, 결국에 이는 메모리 낭비에 불과하다.

두번째 경우는, 우리가 중복되는 모든 노드를 검색하는 것 이다. 이 경우에 우리 검색 알고리즘은 언제나 중복 노드가 존재한다는 가정을 할 것이고, 결국 모든 중복 노드를 찾기 위해서 언제나 잎(Leaf) 노드, 즉 최 하위 노드까지 검색을 이어가야 하는 그리 좋지 않은 시나리오를 가질 것이다

그렇니, 효율성(Efficiency)을 위해, 특이한 상황이 아니라면 트리는 중복 노드를 가지지 않는다.

아래 코드는 노드(Node) 클래스의 자바(Java) 예제 이다.

public class Node {
public class Node {
 private Node left, right;
 private int data;

 public Node(int data) {
  this.data = data;
  left = null;
  right = null;
 }

 /**
  * 현재 노드에서 중위 순회(inOrder Traversal)을 시작한다.
  */
 public void inOrder() {
  // 회귀 함수(Recursive Call)을 이용, 가장 왼쪽 노드로 이동한다.
  if (left != null) {
   left.preOrder();
  }
  // 그리고 노드를 읽는다.
  System.out.println(data);
  // 그 후 다시 회귀 함수(Recursive Call)을 이용 오른쪽 노드를 읽는다.
  if (right != null) {
   right.preOrder();
  }
 }

 /**
  * 현재 노드에서 전위 순회(PreOrder Traversal)을 시작한다
  */
 public void preOrder() {
  // 현재 노드를 읽는다
  System.out.println(data);
  // 그후 회귀 함수(Recursive Call)을 이용
  // 가장 왼쪽 잎(Leaf)노드로 이동.
  if (left != null) {
   left.preOrder();
  }
  // 그 후 오른쪽 노드를 탐색한다.
  if (right != null) {
   right.preOrder();
  }
 }

 /**
  * 현재 노드에서 후위 순회(PostOrder Traversal)을 시작한다
  */
 public void postOrder() {

  if (left != null) {
   left.postOrder();
  }

  if (right != null) {
   right.postOrder();
  }
  System.out.println(data);
 }

 public Node getLeft() {
  return left;
 }

 public void setLeft(Node left) {
  this.left = left;
 }

 public Node getRight() {
  return right;
 }

 public void setRight(Node right) {
  this.right = right;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

}


아래 코드는 이진 탐색 트리(Binary Search Tree) 클래스의 자바 예제 이다.

public class BinarySearchTree {
 private Node root;// 루트 노드 인스턴스 생성

 // 이진 탐색 트리 생성자
 public BinarySearchTree() {
  root = null;
 }

 public boolean isEmpty() {
  return root == null;
 }

 public void clear() {
  root = null;
 }

 public void inOrder() {
  root.inOrder();
 }

 public void preOrder() {
  root.preOrder();
 }

 public void postOrder() {
  root.postOrder();
 }

 /**
  * 주어진 인터져 t 로 새로운 노드를 생성, 삽입한다
  * 
  * @param 삽입할 인터져 t
  * @return 삽입이 성공하면 true 갑을, 실패하면 false 값을 리턴
  */
 public boolean insert(int t) {
  Node newNode = new Node(t);// 주어진 인터져 t 로 새 노드를 생성
  Node pointer;// 노드를 삽입할 위치까지 트리를 순회해야하니, 포인터 인스턴스를 생성한다
  boolean insertComplete = false;
  if (root == null) {
   // 트리가 empty 상태일 경우, 루트 노드에 삽입
   root = newNode;
  } else {
   pointer = root;
   // while 루프로 순회를 시작한다.
   while (!insertComplete) {
    if (pointer.getData() > t) {
     // 인터져 t 를 각 노드들과 비교하여, 작으면 
     // 왼쪽 자식으로, 크면 오른쪽 자식으로 이동한다
     if (pointer.getLeft() != null) {
      pointer = pointer.getLeft();
     } else {
      pointer.setLeft(newNode);
      insertComplete = true;
      break;
      // 노드 삽입이 완료됬다면, 더이상의 루핑은 불필요하다.
      // break 구문을 이용, 루프를 종료하자
     }
    } else if (pointer.getData() < t) {
     if (pointer.getRight() != null) {
      pointer = pointer.getRight();
     } else {
      pointer.setRight(newNode);
      insertComplete = true;
      break;
     }
    } else {
     // 만약 트리에 이미 중복되는 노드가 존재한다면
     // 삽입은 불필요하다. 그러니 루핑을 종료한다
     break;
    }
   }
  }
  // 삽입이 성공적이라면 true 값을
  // 중복 노드가 존재한다거나, 예상외 상황이 있어서 삽입을 실패했다면 false 값을 반환한다.
  return insertComplete;
 }

 /**
  * 인터져 t 를 가진 노드를 트리에서 제거한다
  * 
  * @param t 제거할 값 인터져 t
  * @return 성공적으로 제거했을 때 true 값을, 실패했을 때 false 값을 리턴한다
  */
 public boolean remove(int t) {
  Node pointer, parentPointer;
  pointer = parentPointer = root;
  while (pointer != null && pointer.getData() != t) {
   // 삭제할 노드를 찾을 때까지 루핑으로 트리를 순회한다
   parentPointer = pointer;// parentPointer 인스턴스가 삭제할 노드의 부모 노드를 참조하도록 한다.
   if (pointer.getData() > t) {
    pointer = pointer.getLeft();
   } else {
    pointer = pointer.getRight();
   }
  }

  if (pointer == null) {
   // 첫번째 상황: 트리에 삭제할 노드가 존재하지 않을때
   return false;
  } else {
   if (pointer == root && pointer.getLeft() == null) {
    // 두번째 상황: 제거할 노드가 루트 노드이고, 루트노드가 왼쪽 자식 노드를 가지지 않을 때
    root = root.getRight();
   } else if (pointer != root && pointer.getLeft() == null) {
    // 세번째 상황: 루트 노드가 아닌 제거할 노드가 왼쪽 자식 노드를 가지지 않을 때
    if (pointer == parentPointer.getLeft()) {
     // 제거할 노드가 부모 노드의 왼쪽에 위치할 때
     parentPointer.setLeft(pointer.getRight());
    } else {
     // 제거할 노드가 부모 노드의 오른쪽에 위치할 때
     parentPointer.setRight(pointer.getRight());
    }
   } else {
    // 네번째 상황: 제거할 노드가 2개의 자식 노드 모두를 가지고 있을 때
    // 이러한 상황에서 우리는 제거할 노드에서 파생된 서브 트리에서 가장 큰 노드를 검색한 후, 
    // 제거할 노드의 위치에 삽입할 것 이다.
    // BST에서 가장 오른쪽에 위치한 노드는 가장 큰 값을 가졌다는걸 기억하자.
    // 그러니 BST의 왼쪽 서브 트리의 가장 오른쪽에 존재하는 잎(Leaf)노드는 루트 노드의 가장 좋은 대체제 이다.
    Node rightMostNode = pointer;
    // while 루핑을 이용해서 가장 오른쪽 노드로 이동하자
    while (rightMostNode.getRight() != null) {
     rightMostNode = rightMostNode.getRight();
    }
    // 제거할 노드의 데이터 값을 가장 오른쪽 노드의 데이터 값으로 바꿔주자
    pointer.setData(rightMostNode.getData());
    rightMostNode = null;// 오른쪽 노드를 null로 만든다
   }
  }
  return true;
 }

 /**
  * 인터져 t 값을 가진 노드를 검색한다
  * 
  * @param t 검색할 인터져 t
  * @return 존재한다면 true 값을, 그렇지 않다면 false 값을 반환한다.
  */
 public boolean serach(int t) {
  Node pointer;
  if (root.getData() == t) {
   // 루트 노드가 값을 가지고 있는지 확인
   return true;
  } else {
   // 값을 찾을 때 까지 트리를 순회하자
   pointer = root;
   while (pointer != null) {
    if (pointer.getData() > t) {
     pointer = pointer.getLeft();
    } else if (pointer.getData() < t) {
     pointer = pointer.getRight();
    } else {
     // 인터져 t가 노드와 비교 했을 때 크지도 작지도 않다면, 이는 값이 일치함을 말한다. 
     // 루핑을 종료한다
     break;
    }
   }
  }
  // 만약 트리에 인터져 t 값을 가진 노드가 존재하지 않는다면
  // 위의 while 루프에서 트리의 끝까지 여행하게 될거고, 결국 pointer 인스턴스는 null 값을 참조하게 될 것 이다
  // 하지만 트리에 t값을 가진 노드가 존재한다면, pointer 인스턴스는 그 노드를 참조할 것 이다.
  // 그렇니 pointer 인스턴스가 null 값을 가지지 않는다면, 트리에 t 값을 가진 노드가 존재한다고 볼 수 있다.
  return pointer != null;
 }
}

2015년 1월 9일 금요일

[자료 구조] Tree

트리(Tree) 구조란 무었인가?

링크드 리스트, 스택, 큐는 모두 직선형 구조를 가지고 있다. 직선형 자료 구조는 1차원적 구성 위주고 이는 곧 계층적, 계급적 구조를 표현하는데 한계를 가지고 있다. 우리가 이번에 다룰 트리(Tree) 자료 구조는 노드(Node)들과 가지(Branch)들로 이루어진 비선형 자료 구조이다. 트리(Tree)의 최상위에는 뿌리(Root), 즉 루트 노드가 위치하며 그 아래로 자식(Child) 노드들이 가지(Branch)들을 통해 연결된다. 맨 아래의 노드들은 보통 잎(Leaf), 리프 노드라 불린다. 루트(Root) 노드를 제외한 모든 노드(Node)들은 부모(Parent) 노드를 가지며, 잎(Leaf) 노드를 제외한 모든 노드들은 자식(Child) 노드를 가진다. 그리고 모든 노드들은 가지(Branch)들로 연결되있다. 아래 그림은 트리 구조와 각각 파트의 이름, 주요 용어들을 정리해놓은 그림이다.


트리(Tree) 컨셉과 주요 용어들
트리(Tree) 컨셉과 주요 용어들

위의 그림에 나와있듯, 최상위에 위치한 노드는 뿌리(Root) 노드라 불리며, 가장 아래에 위치한 노드는 잎(Leaf)노드라 불린다. 그리고 트리(Tree)는 서브 트리(Sub Tree) 라 불리는 작은 트리들로 구성되있고, 서브 트리(Sub Tree) 들 또한 작은 트리들로 구성되있다. 위 그림 예제 같은 경우에는 왼쪽 서브 트리가 B 노드 부터 시작하고, 오른쪽 서브 트리는 C 노드 부터 시작한다. 그리고 B노드나 C 노드 둘다 아래로 서브 트리를 두지 않는다, 왜냐하면 D, E, F, G 노드들 모두 자식 노드가 없으니까~.

트리에서 조상(Ancestor) 관계와 후손(descendant) 관계란?

E 라는 노드가 T 노드의 조상(Ancestor)일 때, E 노드는 T 노드의 부모(Parent) 노드 이거나, T 노드의 부모(Parent) 노드의 조상(Ancestor)라 할 수 있다.
T 노드가 E 노드의 후손(Descendant)라 할 때, T 노드는 E 노드의 자식(Child) 노드 이거나, E 노드의 자식(Child) 노드의 후손(Descendant)라 할 수 있다.

노드(Node)의 깊이(Depth)란? 그리고 어떻게 계산되는가?

깊이란 루트(Root)노드에서 본인 위치까지에 있는 경로의 길이 이다. 노드 E 가 뿌리(Root) 노드라 할 때, 노드 E의 깊이(Depth)는 0이다. 루트(Root) 노드에서 한가지(Branch)씩 건너갈 때 마다 깊이는 +1 이 된다.

위의 그림을 예제로 들때
깊이 0 을 가진 노드는 : A
깊이 1 을 가진 노드는 : B, C
깊이 2 을 가진 노드는 : D, E, F, G
가 된다.

전체의 깊이(Depth Of Tree)란 최 하위에 위치한 잎(Leaf) 노드의 깊이(Depth)를 말한다. 위 그림의 경우에 Depth Of Tree는 2 가 된다.

트리 순회(Traversal)란? 그 종류, "Preorder"(전위), "Postorder"(후위), "Inorder"(중위) 순회는 어떻게 실행되는가?

  • 전위 순회(Preorder traversal)

    • 전위 순회(Preorder traversal)은 부모(Parent) 노드에서 자식(Child)노드로 진행된다
    1. 첫번째로 루트 노드를 방문한 후, 루트노드의 왼쪽 자식 노드로 이어간다
    2. 왼쪽 서브 트리를 전위 순회방식으로 순회한다.
    3. 그 후 오른쪽 서브 트리를 전위 순회방식으로 순회한다.
    • 위의 그림 예제에 나와있는 트리를 전위 순회 방식으로 순회하면
    • ABDECFG 와 같다.

  • 후위 순회(Postorder traversal)

    • 후위 순회(Postorder traversal)은 자식(Child) 노드에서 부모(Parent)노드로 진행된다
    1. 가장 왼쪽 아래에 위치한 자식노드를 방문한다, 그리고 그 자식 노드의 형제 노드를 방문한 후, 부모 노드로 진행한다.
    2. 왼쪽 서브 트리의 최 상위 노드에 도달할 때 까지 후위 순회를 진행한다
    3. 그 후, 오른쪽 서브 트리에서 후위순회를 진행한다.
    4. 마지막으로 루트 노드를 방문함으로써 후위순회를 마친다.
    • 위의 그림 예제에 나와있는 트리를 후위 순회 방식으로 순회하면
    • DEBFGCA 와 같다

  • 중위 순회(Inorder traversal)

    • 중위 순회(Inorder traversal)은 가장 아래 왼쪽 자식 노드에서 시작해 부모 노드를 거친 후에 오른쪽 자식 노드(시작 노드의 형제 노드)로 이어간다
    1. 가장 왼쪽 잎(leaf) 노드를 방문한다, 그리고 그 부모 노드를 방문 후, 아래로 형제 노드를 방문한다
    2. 이러한 방식으로 루트 노드까지 중위 순회를 이어간다.
    3. 그리고 오른쪽 서브 트리를 중위 순회로 순회한다
    • 위의 그림 예제에 나와있는 트리를 후위 순회 방식으로 순회하면
    • DBEAFCG 와 같다

2015년 1월 7일 수요일

[자료 구조] 큐(Queue)

자바(Java)로 구현한 큐(Queue) 예제


큐(Queue) 컨셉
큐(Queue) 컨셉

큐(Queue)란 무었인가?

큐는 직선형 자료 구조로써, 같은 타입의 데이터를 "하나 다음 하나" 라는 컨셉으로 순차적으로 저장하는 자료형이다. 스택(Stack)과는 달리, 큐(Queue)는 구조의 양 끝 모두에 접근이 가능하다. 맥도날드나 카페에서 줄을 서서 기다리는 걸 머리속에 그려보자. 줄은 새로운 사람이 끝에 섬으로써 길어지고, 가장 앞에선 사람이 주문을 함으로써 짧아진다. 이게 바로 큐(Queue)이다. 이렇한 이유로, 큐(Queue)는 보통 "FIFO(First In First Out) Structure"(먼져 들어간게 먼져 나오는 구조)라 영어권에서 표현된다.

큐(Queue) 실제로 어디에 쓰일까?

  • Operating System
    • 시스템 스케줄링, 인풋 버퍼(Input Buffer), 그리고 프린터 작업 관리 등

큐(Queue)는 어떻게 구현될까?

큐(Queue)는 스택(Stack)처럼 추상 자료형(Abstract Data Type)이므로, 다양한 방법으로 구현될 수 있다. 자바(Java)로 구현할 때 가장 많이 쓰이는 두가지 방법은 배열(Array)와 링크드 리스트(Linked List)를 이용하는 것이다. 큐(Queue)는 몇가지 필수적인 메소드들을 가지고 있는데 그것들은 아래와 같다
  • Enqueue(삽입)
    • 큐(Queue)의 끝에 새로운 자료를 삽입한다
    • 이 작업은 O(1)의 복잡도를 가진다
  • Dequeue(제거)
    • 큐(Queue)의 가장 첫 위치에 존재하는 자료를 반환하고 제거한다.
    • 이 작업은 O(1)의 복잡도를 가진다
  • Peek
    • 큐(Queue)의 처음에 존재하는 자료를 반환한다
    • Dequeue 메소드와는 달리, 처음에 존재하는 자료를 제거하지는 않는다.
  • isEmpty
    • 큐(Queue) 가 Empty 상태인지 확인한다.
  • clear
    • 큐(Queue) 내부의 모든 자료들을 삭제한다

아래는 자바(Java) 배열(Array)로 구현한 큐(Queue)의 예제이다


public class QueueWithArray {
 private Object[] queue;
 int first, last, size;
  public QueueWithArray(int size) {
  queue = new Object[size];// 주어진 인터져 size 값으로 size의 크기를 가진 오브젝트 어레이를 생성한다.
  first = last = -1;
  // 우선 아무것도 없는 배열에서, 우리의 마지막, 첫번째 데이터를 가리키는 first, last 인스턴스는 -1인덱스를 가리킨다.       
  this.size = size;// clear 메소드를 위해 사이즈 값을 저장해두자.
 }

 public boolean isEmpty() {
  return first == -1;
  // 만약 first 포인터 인스턴스가 -1 의 인덱스를 가리킨다면 그건 큐(Queue)가 empty 상태라는 뜻이다
 }

 public void clear() {
  queue = new Object[size]; // 새로운 배열(Array)를 생성하면서 원래 큐를 지워버리자
  first = last = -1;// 포인터 인스턴스를 리셋해준다.
 }

 public boolean isFull() {
   // 큐(Queue)가 꽉 찾는지를 확인한다.
   if ((first == 0 && last == size - 1) || first == last + 1) {
   // first 포인터가 인덱스 0, last 포인터가 배열의 마지막 인덱스(size - 1)를 가리키거나
   // first 포인터가 가리키는 인덱스가 last 포인터가 가리키는 인덱스보다 1이 크다면
   // 이는 큐(Queue)에 쓰는 배열이 꽉 찾음을 의미한다.
   return true;
  } else {
   return false;
  }

 }

 public void enQueue(Object e) {
  if (isFull()) {
   throw new FullQueueException();// 큐가 꽉 찾다면 Exception을 던져주자
  } else {
   //아니라면 삽입을 시작한다.
   if (first == -1) {// 만약 first 인스턴스가 -1값을 가지고 있다면, 이는 큐가 empty 상태인걸 의미한다.
    first = last = 0;// 그렇니 first 와 last 값을 0으로 바꿔주자
   } else {
    last = (last + 1) % size;
    // 이 메소드에서 새로운 object e 는 어레이의 가장 끝 인덱스의 위치로 삽입된다.
    // (last + 1) % size 는 배열(Array)의 중간에 last 인덱스가 위치할 경우를 생각한다.
   }
   queue[last] = e;
  }
 }

 public Object dequeue() {
  if (isEmpty()) {
   // 큐(Queue)가 Empty 인지 확인한다
   throw new EmptyQueueException();
  } else {
   Object toReturn = queue[first];
   if (first == last) {
    // first 와 last 가 같은 인덱스를 가리킨다면
    // 이는 큐(Queue)에 데이터가 1개밖에 없음을 의미한다.
    // 그렇니 그냥 포인터를 리셋해주자
    first = last = -1;
   } else {
    first = (first + 1) % size;
    // 만약 first 포인터가 배열(Array)의 마지막 인덱스를 가리키고 있다면
     // first + 1 은 ArrayOutOfBound Exception 을 낳을 것이다
     // first = (first + 1) % size; 은 그럴경우에는 0 이란 수가 계산되어
     // 옭바른 인덱스를 계산 할 수 있다.
   }
   return toReturn;
  }
 }

 public Object peek() {
  if (isEmpty()) {
   throw new EmptyQueueException();
  } else {
   return queue[first];
  }
 }
}



아래는 자바(Java) Linked List 로 구현한 큐(Queue)의 예제이다


import java.util.LinkedList;
public class QueueWithLinkedList {
 private LinkedList queue;

 public QueueWithLinkedList() {
  queue = new LinkedList();
 }

 public boolean isEmpty() {
  return queue.isEmpty();
 }

 public void enQueue(Object e) {
  queue.addLast(e);
 }

 public Object deQueue() {
  return queue.removeFirst();
 }

 public Object peek() {
  return queue.getFirst();
 }
}

[자료 구조] 스택 (Stack)

자바(Java)로 구현한 스택 예제


스택(Stack) 컨셉
스택(Stack) 컨셉

스택(Stack)이란 무었인가?

스택은 같은 타입의 자료를 "하나 다음 하나"라는 컨셉으로 순차적으로 저장하는 직선형 자료 구조이다. 우리가 스택에서 자료를 추출하고 삽입할 때 우리는 순렬의 끝에만 접근이 가능하다. 위 그림을 잠시 보자. 새로운 데이터는 스택의 최상위에 위치하게되고, 데이터 추출시, 우리는 오직 가장 최근에 삽입된 데이터만(최상위) 접근이 가능하다. 이 이유때문에 스택은 보통 "LIFO(Last In First Out)" 구조 라는, 가장 최근에 들어간게 가장 먼져 나온다는 뜻을 가진 어문으로 표현되기도 한다.

스택(Stack)은 실제로 어디에 사용되는가?

  • Operating Systems 
    • 프로그램에서 불러지는 함수(Method)들을 모두 Stack 이라는 자료형에 저장한다.
  • Compilers(컴파일러)
    • 컴파일러에서 수학기호들을 기계어(Machine Code)로 변환시, 괄호들을 매칭하거나 할 때.
  • JVM(Java Virtual Machine)자바 가상 머신
    • 자바 프로그램이 실행될 때 사용되는 JVM 에서도 스택은 사용된다. 각각의 스레드는 1개의 스택을 가지고 모든 메소드들을 트랙킹한다. 새로운 메소드들이 호출 될 때 마다, 새로운 프레임이 스택에 삽입되고, 메소드가 끝날 때 마다 스택에서 제거된다

스택(Stack)은 어떻게 구현될수 있을까?

앞에서 다룬 링크드 리스트와 달리 스택(Stack)은 추상 자료형(Abstract Data Type)이다. 추상 자료형이란 수학적 모델을 가진 자료형이고, 이는 곧 매우 다양한 방법으로 구현될 수 있음을 의미한다. 가장 자주 쓰이는 2가지 구현방법들은, ArrayList(어레이리스트)와 LinkedList(링크드 리스트)이다. 스택은 몇가지 필수적인 메소드들을 가지고 있는데 이는 아래와 같다
  • pop(추출)
    • 가장 최 상위에 위치한 자료를 추출한 후에 스택에서 제거한다
    • 이 작업은 O(1)의 복잡도를 가진다
  • push(삽입)
    • 스택의 최 상위에 새로운 자료를 삽입한다
    • 이 작업은 O(1)의 복잡도를 가진다
  • isEmpty
    • 스택이 empty 상태인지 확인한다
  • clear
    • 스택에 존재하는 모든 자료들을 삭제한다
  • peek
    • 가장 최 상위에 위치한 자료를 추출한다
    • pop 메소드와는 달리 스택에서 제거하지는 않는다.
    • 이 작업은 O(1)의 복잡도를 가진다

스택 Push 메소드
스택 Push 메소드

스택 Pop 메소드
스택 Pop 메소드

아래는 자바의 어레이리스트 api(java.util.ArrayList)로 구현한 스택(Stack) 자료형 이다


public class StackWithArrayList {
import java.util.*;//import arrayList

public class StackWithArrayList {
 private ArrayList stack;

 /**
  * 스택 인스턴스를 생성하는 컨스트럭터(Constructor)
  */
 public StackWithArrayList() {
  stack = new ArrayList();
 }

 /**
  * 스택을 최소 사이즈 s 로 생성한다
  * 
  * @param s 구현할 스택의 최소 사이즈
  */
 public StackWithArrayList(int s) {
  stack = new ArrayList();
  stack.ensureCapacity(s);
 }

 /**
  * 스택을 비운다
  */
 public void clear() {
  stack.clear();
 }

 /**
  * 스택이 Empty 상태인지 확인한다
  * 
  * @return 스택이 Empty 상태이면 true값을, 아니면 false 값을 반환한다.
  */
 public boolean isEmpty() {
  return stack.isEmpty();// 또는 "stack.size() == 0"를 이용할수도 있다
 }

 /**
  * 새로운 요소를 삽입한다
  * 
  * @param e 삽입될 새로운 요소
  */
 public void push(Object e) {
  stack.add(e);// ArrayList의 가장 마지막 index 에 새로운 요소를 삽입한다
 }

 /**
  * 스택에서 가장 최 상위에 위치한 데이터를 추출한 후 제거한다.
  * 
  * @return 스택에서 가장 최 상위에 위치한 데이터
  */
 public Object pop() {
  if (isEmpty()) {// 우선 스택이 empty 인걸 확인한 하고
   throw new EmptyStackException();
   // 그렇다면 Exception 을 던진다
  } else {
   return stack.remove(stack.size() - 1);
   // ArrayList.remove 메소드는 어레이에서 주어진 인덱스의 데이터를 제거후, 리턴한다 
  }
 }

 /**
  * 스택에서 가장 최상위에 위치한 데이터를 리턴한다, pop 메소드와는 달리 제거하지 않는다.
  * 
  * @return 스택에서 가장 최 상위에 위치한 데이터
  */
 public Object peek() {
  if (isEmpty()) {
   throw new EmptyStackException();

  } else {
   return stack.get(stack.size() - 1);
   // ArrayList.get 메소드는 주어진 인덱스에 저장된 값을 반환한다.
  }
 }
}


아래는 자바의 링크드리스트 api(java.util.LinkedList)로 구현한 스택(Stack) 자료형 이다

import java.util.EmptyStackException;
import java.util.LinkedList;

public class StackWithLinkedList {
 private LinkedList stack;

 public StackWithLinkedList() {
  this.stack = new LinkedList();
 }

 /**
  * 스택을 비운다
  */
 public void clear() {
  stack.clear();
 }

 /**
  * 스택이 Empty 상태인지 확인한다
  * 
  * @return 스택이 Empty 상태이면 True 값을, 아니면 false 값을 리턴한다
  */
 public boolean isEmpty() {
  return stack.isEmpty();// 또는 "stack.size() == 0" 구문을 이용할 수도 있다
 }

 /**
  * 스택에 새로운 데이터를 삽입한다.
  * 
  * @param e 삽입할 데이터
  */
 public void push(Object e) {
  stack.addLast(e);// 어레이리스트의 가장 마지막 인덱스에 추가한다.
 }

 /**
  * 스택에서 가장 최 상위에 위치한 데이터를 추출한 후 제거한다.
  * 
  * @return 스택에서 가장 최 상위에 위치한 데이터
  */
 public Object pop() {
  if (isEmpty()) {// 우선 스택이 empty 상태인지 확인한후
   throw new EmptyStackException();
   // empty 상태라면 Exception 을 던진다.
  } else {
   return stack.removeLast();
   // ArrayList.removeLast 메소드는 가장 마지막 인덱스에 위치한 자료를 어레이에서 리턴하고 제거한다
  }
 }

 /**
  * return 스택에서 가장 최상위에 위치한 데이터를 리턴한다, pop 메소드와는 달리 제거하지 않는다.
  * 
  * @return 스택에서 가장 최 상위에 위치한 데이터
  */
 public Object peek() {
  if (isEmpty()) {// 우선 스택이 empty 상태인지 확인한후
   throw new EmptyStackException();
   // empty 상태라면 Exception 을 던진다.
  } else {
   return stack.getLast();
   // ArrayList.getLast 메소드는 가장 마지막 인덱스에 위치한 데이터를 리턴한다.
  }
 }
}