'Javascript/DataStructures'에 해당되는 글 3건

자바스크립트 큐(Queue)  - Queue

- 자바스크립트의 큐는 자바로 구현 할 때보다  손쉽게 구현 가능하다

- 기존에 push(), shift() 함수를 이용한다

1. Queue.class

function Queue(){ this.dataStore = []; this.enqueue = enqueue; this.dequeue = dequeue; this.toString = toString; this.front = front; this.back = back; this.empty = empty; }

- enqueue() : 데이터를 넣는다

- dequeue() : 맨 앞에 넣은 데이터를 뽑는다

- front() : 앞에있는 데이터를 가져온다

- back() : 뒤에 있는 데이터를 가져온다

- empty() : 큐가 비어있는지 체크한다

2. enqueue(), dequeue()

function enqueue(element){ this.dataStore.push(element); } function dequeue(){ this.dataStore.shift(); }  

- 기존 자바스크립트 함수 push(), shift()를 활용한다

3. front(), back()

function front(){ return this.dataStore[0]; } function back(){ return this.dataStore[this.dataStore.length-1]; }  

4. empty(), toString()

function toString(){ var str="" for(var i = 0; i<this.dataStore.length; i++){ str += this.dataStore[i] + " "; } return str; } function empty(){ if(this.dataStore.length == 0){ return true; }else{ return false; } }  

5. 실행

var queue = new Queue(); queue.enqueue(2); queue.enqueue(5); queue.enqueue(6); queue.enqueue(7); document.write("<br>"+queue.toString()); queue.dequeue(); queue.dequeue(); document.write("<br>"+queue.front()); document.write("<br>"+queue.back()); document.write("<br>"+queue.toString());  

스택 구현 - Stack

- 함수형 클래스로 구현

1. Stack

1) Stack class

function Stack(){ this.dataStore = []; this.top = 0; this.push = push; this.pop = pop; this.peek = peek; this.length = length; this.clear = clear; this.print = print; }

2) pop(), push()

function push(element){ this.dataStore[this.top++] = element; } function pop(){ return this.dataStore[--this.top]; }  

3) peek()

function peek(){ return this.dataStore[this.top-1]; }  

4) length(), clear(), print()

function length(){ return this.top; } function clear(){ return this.top = 0; } function print(){ for(var i = 0; i<this.top; i++){ document.write(this.dataStore[i]+","); } }  

- length(): tack의 크기

- clear(): stack 초기화

- print() : 현재 상태

5) 실행

var s = new Stack(); s.push(1); s.push(4); s.push(6); s.push(7); s.push(3); s.push(99); s.pop(); s.pop(); s.clear(); s.print(); document.write('<br>'+s.peek());  

자바 스크립트 리스트 - List ADT (abstract data type) 

- 자바스크립트를 이용하여 LIST를 구현한다

- 자바로 치면 Arraylist

1. List Class

function List(){ //리스트 사이즈 this.listSize = 0; //현재 위치 this.pos = 0; //리스트 요소 저장 this.dataStore = []; //리스트 문자열로 반환 this.toString = toString; //새요소 리스트 끝에 추가 this.append = append; //요소 검색 this.find = find; //특정 요소 삭제 this.remove = remove; //요소 개수 this.length = length; //요소 삽입 this.insert = insert; //모든 요소 삭제 this.clear = clear; //리스트 탐색와 관련된 함수들 this.front = front; this.end = end; this.prev = prev; this.next = next; this.moveTo = moveTo; this.currPos = currPos; this.getElement = getElement; }

- 리스트 동작에 필요한 함수와 사이즈 등의 초기값을 선언한다

2. Append(element)

function append(element){ this.dataStore[this.listSize++] = element; }  

- 요소의 끝에 추가한다

3. find(element), remove(element), insert(element)

function find(element){ for(var i = 0; i<this.listSize; i++){ if(this.dataStore[i] == element){ return i; } } return -1; } function remove(element){ var index = this.find(element); if(index > -1){ this.dataStore.splice(index,1); this.listSize--; return true; } return false; } function insert(element, after){ var index = this.find(after); if(index > -1){ this.dataStore.splice(index+1,0,element); this.listSize++; return true; } return false; }  

- find()를 이용하여 element의 index 위치를 찾는다

- remove()/insert()는 find()를 이용하여 특정 위치에 삭제/삽입 한다

4. Length(), toString()

function length(){ return this.listSize; } function toString(){ return this.dataStore; }  

- 요소의 길이와 현재 상태를 배열의 형태로 출력한다

5. clear()

function clear(){ delete this.dataStore; this.dataStore = []; this.listSize = this.pos = 0; }  

- delete 명령어로 dataStore 배열을 삭제하고 이후에 새로 생성

6. 리스트 탐색

//탐색관련 함수 function front(){ this.pos = 0; } function end(){ this.pos = this.listSize; } function prev(){ if(this.pos > 0){ --this.pos; } } function next() { if (this.pos < this.listSize ) { ++this.pos; } } function currPos(){ return this.pos; } function moveTo(position){ this.pos = position; } function getElement(){ return this.dataStore[this.pos]; }  

- this.pos의 index 값을 기준으로 이동 시킨다

- 현재 this.pos가 가르키고 있는 값을 getElement() 를 이용하여 출력한다

7. 리스트 반복자

for(names.front();names.currPos()< names.length(); names.next()){ document.write(names.getElement()); }  

- for문을 이용하여 리스트 반복

- front(), end(), prev(), next(), currpos() 등의 함수를 이용하여 반복자를 구현한다

- 반복자를 이용하면 내부 저장소를 직접 참조 하지 않고 리스트를 탐색

1) 장점

- 리스트 요소에 접근할 때 내부 데이터 저장소가 무엇인기 걱정 안함

- 리스트가 바뀌어도 반복자를 갱신할 필요 없다

- List클래스에 데이터 저장소의 종류가 달라져도 이전과 같은 방식으로 요소 접근

8. 실행

var names = new List(); names.append(2); names.append(3); names.append(4); names.append(5); names.append(6); document.write(names.toString()+"\n"); names.next(); names.next(); names.next(); document.write(names.getElement()); for(names.front();names.currPos()< names.length(); names.next()){ document.write(names.getElement()); }