openMyFile();
try {
writeMyFile(theData); //This may throw a error
} catch (e) {
handleError(e); // If we got a error we handle it
} finally {
closeMyFile(); // always close the resource
}
가장 윗부분에서만
자료의 추가와 삭제가 일어나므로 실행속도가 빠르고 구현이 쉬운 효율적인 자료구조다.탑(top)
이라 불리는 리스트의 한쪽 끝으로만 요소에 접근할 수 있다.후입선출(last in, first out, LIFO)
자료구조 알려져 있다.push 동작
을 이용해 오소를 스택에 추가한다.pop 동작
을 이용해 스택에서 요소를 꺼낼 수 있다.peek
을 이용하면 스택의 탑에 있는 요소를 제거하지 않고 내용만 확인할 수 있다.top 변수
를 이용해 관리한다.스택을 구현하려면 스택 요소를 내부적으로 저장한 자료구조를 결정해야 한다.
여기서는 배열을 사용한다.
class Stack {
constructor() {
this.dataStore = []; //스택 요소 저장하는 배열
this.top = 0;
}
push(element) {
this.dataStore[this.top++] = element; //현재 top 위치에 새 요소 추가한 다음 top에 1 증가
}
pop() {
return this.dataStore[--this.top]; // top 1을 감소하고 스택의 탑 위치에 있는 요소 반환
}
peek() {
return this.dataStore[this.top - 1]; //top-1 위치의 요소에 접근해 스택의 탑 요소 반환, 스택이 비어있을 때 호출하면 undefined 반환
}
length() {
return this.top;
}
clear() {
this.top = 0;
}
}
// Stack 클래스 구현 테스트
let s = new Stack();
s.push('Marco');
s.push('Dotori');
s.push('Pocky');
s.push('Millie');
console.log('length:' + s.length());
console.log(s.peek());
console.log('Popped element: ', s.pop());
console.log(s.peek());
console.log('length:' + s.length());
s.clear();
console.log('clear');
console.log('length:' + s.length());
n이라는 숫자가 있고 b라는 진법으로 변환할 때 다음과 같은 알고리즘 이용할 수 있다.
// 2진수부터 9진수 사이에서만 동작하는 알고리즘
function mulBase(num, base) {
let s = new Stack(); //위에서 정의한 stack 클래스 사용
while (num > 0) {
s.push(num % base);
num = Math.floor(num / base);
}
let converted = '';
while (s.length() > 0) {
converted += s.pop();
}
return converted;
}
console.log(mulBase(7, 2));
console.log(mulBase(45, 6));
앞으로 읽으나 뒤로 읽으나 같은 단어, 구절, 숫자를 회문(palindrome)이라 한다.
스택을 이용해 어떤 문자열이 회문인지 여부를 판단할 수 있다.
스택에 문자열을 추가하고, 스택의 각 문자를 다시 꺼내 새 문자열을 만든다.
역순으로 바뀐 문자열과 원래 문자열을 비교하여, 비교 결과가 같은 문자열을 회문이다.
function isPalindrome(word) {
let s = new Stack();
for (let i = 0; i < word.length; ++i) {
s.push(word[i]);
}
let rword = '';
while (s.length() > 0) {
rword += s.pop();
}
if (word == rword) {
return true;
} else {
return false;
}
}
console.log(isPalindrome('racecar')); // true, racecar는 거꾸로 해도 racecar
console.log(isPalindrome('hello')); //false
재귀를 구현할 때도 스택을 사용한다. 스택을 이용해 재귀 프로세스를 흉내낼 수 있다.
//팩토리얼 계산하는 재귀 함수
function factorial(n) {
if (n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
console.log(factorial(5)); //120
//스택을 이용한 재귀 과정 시뮬레이션
function fact(n) {
let s = new Stack();
while (n > 1) {
s.push(n--); // 5,4,3,2 순으로 쌓인다.
}
let product = 1;
while (s.length() > 0) {
product *= s.pop(); // 2,3,4,5 순으로 곱해진다.
}
return product;
}
console.log(fact(5)); //120
큐는 리스트의 일종으로 끝부분(end)
으로 데이터가 삽입되고 앞부분(front)
에서는 데이터가 삭제되는 자료구조다.
큐는 선입선출(first-in, first-out, FIFO)
자료구조다. 먼저 온 고객부터 먼저 처리해드리는 것과 같다.
인큐(enqueue)
라고 한다.끝부분
에 요소를 추가
한다.데큐(dequeue)
라고 한다.앞부분
에서 요소를 삭제
한다.class Queue {
constructor() {
this.dataStore = [];
}
enqueue(element) {
this.dataStore.push(element);
}
dequeue() {
this.dataStore.shift();
}
front() {
return this.dataStore[0];
}
back() {
return this.dataStore[this.dataStore.length - 1];
}
// toString(), 큐의 모든 요소 출력
toString() {
let retStr = '';
for (let i = 0; i < this.dataStore.length; ++i) {
retStr += this.dataStore[i] + '\n';
}
return retStr;
}
isEmpty() {
if (this.dataStore.length == 0) {
return true;
} else {
return false;
}
}
}
let q = new Queue();
q.enqueue('A');
q.enqueue('B');
q.enqueue('C');
q.enqueue('D');
console.log(q.toString());
console.log('[dequeue 실행 후]');
q.dequeue();
console.log(q.toString());
console.log('제일 앞 요소: ' + q.front());
console.log('제일 뒤 요소: ' + q.back());
//digit은 1의 자리, 10의 자리 숫자를 구분하는 매개변수
// 1의 자리 숫자인지 10의 자리 숫자인지 구분해 큐에 숫자 추가하는 함수
function distribute(nums, queues, n, digit) {
for (let i = 0; i < n; i++) {
if (digit == 1) {
queues[nums[i] % 10].enqueue(nums[i]);
} else {
queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
}
}
return queues;
}
// 큐에 저장된 숫자를 수집하는 함수
function collect(queues, nums) {
let i = 0;
const result = [];
//이중 루프(이차원 배열을 일차원 배열로 만들기 위해)
for (let digit = 0; digit < 10; digit++) {
while (!queues[digit].isEmpty()) {
nums[i++] = queues[digit].dequeue(); //원본배열 nums의 인덱스에 순차적으로 queues[digit] 배에서 dequeue한 요소를 재할당한다.
}
}
return result;
}
let queues = [];
for (let i = 0; i < 10; i++) {
queues[i] = new Queue();
}
let nums = [];
for (let i = 0; i < 10; i++) {
nums[i] = Math.floor(Math.random() * 101);
}
console.log('기수 정렬 전');
console.log(nums);
console.log('1의 자리 수로 기수 정렬 후 ');
console.log(distribute(nums, queues, 10, 1));
collect(queues, nums);
console.log(nums);
console.log('기수 정렬 전');
console.log(nums);
console.log('10의 자리 수로 기수 정렬 후 ');
console.log(distribute(nums, queues, 10, 10));
collect(queues, nums);
console.log(nums);
//큐에 저장할 객체 Patient의 요소 name, code 정의
function Patient(name, code) {
this.name = name;
this.code = code;
}
//가장 높은 우선순위를 가진 요소를 삭제하도록 dequeue 함수를 고친다.
Queue.prototype.dequeue = function () {
let entry = 0;
for (let i = 0; i < this.dataStore.length; i++) {
if (this.dataStore[i].code < this.dataStore[entry].code) {
entry = i;
}
}
return this.dataStore.splice(entry, 1);
};
Queue.prototype.toString = function () {
let retStr = '';
for (let i = 0; i < this.dataStore.length; ++i) {
retStr += `${this.dataStore[i].name} ${this.dataStore[i].code}\n`;
}
return retStr;
};
let ed = new Queue();
let p = new Patient('Smith', 5);
ed.enqueue(p);
p = new Patient('Jones', 4);
ed.enqueue(p);
p = new Patient('Marco', 6);
ed.enqueue(p);
p = new Patient('Brown', 1);
ed.enqueue(p);
p = new Patient('Ingram', 1);
ed.enqueue(p);
console.log('치료 대기중인 환자:\n', ed.toString());
console.log('방금 치료받은 환자: ', ed.dequeue()[0]);
console.log('치료 대기중인 환자:\n', ed.toString());
console.log('방금 치료받은 환자: ', ed.dequeue()[0]);
console.log('치료 대기중인 환자:\n', ed.toString());
console.log('방금 치료받은 환자: ', ed.dequeue()[0]);
console.log('치료 대기중인 환자:\n', ed.toString());
console.log('방금 치료받은 환자: ', ed.dequeue()[0]);
console.log('치료 대기중인 환자:\n', ed.toString());
console.log('방금 치료받은 환자: ', ed.dequeue()[0]);
console.log('치료 대기중인 환자:\n', ed.toString());
console.log('방금 치료받은 환자: ', ed.dequeue()[0]);
console.log('치료 대기중인 환자:\n', ed.toString());
//output
치료 대기중인 환자:
Smith 5
Jones 4
Marco 6
Brown 1
Ingram 1
방금 치료받은 환자: Patient { name: 'Brown', code: 1 }
치료 대기중인 환자:
Smith 5
Jones 4
Marco 6
Ingram 1
방금 치료받은 환자: Patient { name: 'Ingram', code: 1 }
치료 대기중인 환자:
Smith 5
Jones 4
Marco 6
방금 치료받은 환자: Patient { name: 'Jones', code: 4 }
치료 대기중인 환자:
Smith 5
Marco 6
방금 치료받은 환자: Patient { name: 'Smith', code: 5 }
치료 대기중인 환자:
Marco 6
방금 치료받은 환자: Patient { name: 'Marco', code: 6 }
치료 대기중인 환자:
방금 치료받은 환자: undefined
치료 대기중인 환자:
연결 리스트
로 바꿀 수 있다. 임의의 요소에 접근해야 할 때는 연결 리스트보다 배열이 좋다.노드(node)
라 불리는 객체가 모여 연결 리스트를 구성한다.객체 레퍼런스
를 통해 리스트의 다른 노드와 연결된다.링크(link)
라 한다.헤더
라 불리는 특별한 노드를 이용해 표현한다.이전 노드가 가리키던 노드
를 가리키도록 설정해야 한다.새 노드
를 가리키도록 바꿔야 하고삭제하려는 노드의 다음 노드
를 가리키도록 바꿔야 하고,Null
로 설정한다.Node 클래스
와 LinkedList 클래스
를 만든다.LinkedList 클래스
는 노드의 삽입, 삭제, 리스트 출력, 기타 연결 리스트에 필요한 기능을 제공한다.Node 클래스의 두 가지 프로퍼티
element
next
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
LList
클래스는 연결 리스트의 기능을 제공한다.
class LList {
constructor() {
this.head = new Node('head');
}
find = function () {};
insert = function () {};
remove = function () {};
display = function () {};
}
// find 함수 - 특정 데이터를 포함하는 노드를 검색하여 해당 노드를 반환
function find(item) {
//새 노드를 만들고 head 노드로 설정한다
let currentNode = this.head;
//다음 노드로 반복 이동하면서 현재 노드의 element 프로퍼티 값이 탐색하려는 값과 같은지 확인한다.
while (currentNode.element !== item) {
currentNode = currentNode.next;
}
//원하는 데이터를 찾으면 해당 노드를 반환한다.
// 데이터를 찾지 못했으면 null이 반환된다(currentNode.next가 null)
return currentNode;
}
newNode.next
)는 이전 노드가 가리키던 노드(current.next
)를 가리키도록 설정하고,current.next
)는 새 노드(newNode
)를 가리키도록 바꿔야 한다.insert(newElement, item) {
let newNode = new Node(newElement);
let current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
display() {
let currentNode = this.head;
while (currentNode.next !== null) {
//실제로 데이터를 포함하는 노드만 출력할 수 있도록(즉, 헤드 노드는 제외하도록) currentNode가 가리키는 다음 노드의 element 프로퍼티에 접근한다.
console.log(currentNode.next.element);
currentNode = currentNode.next;
}
}
삭제하려는 데이터를 포함하는 노드의 이전 노드(previousNode)
를 반환한다. findPrevious(item) {
let currentNode = this.head;
while (currentNode.next !== null && currentNode.next.element !== item) {
currentNode = currentNode.next;
}
return currentNode;
}
previousNode.next
)는 삭제하려는 노드의 다음 노드(previousNode.next.next
)를 가리키도록 바꿔야 한다.findPrevious()함수
사용하여 삭제하려는 바로 이전 노드(previousNode)
를 찾는다.Null
로 설정한다. remove(item) {
let previousNode = this.findPrevious(item);
if (previousNode.next !== null) {
previousNode.next = previousNode.next.next;
}
}
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
class LList {
constructor() {
this.head = new Node('head');
}
find(item) {
let currentNode = this.head;
while (currentNode.element !== item) {
currentNode = currentNode.next;
}
return currentNode;
}
insert(newElement, item) {
let newNode = new Node(newElement);
let current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
display() {
let currentNode = this.head;
while (currentNode.next !== null) {
console.log(currentNode.next.element);
currentNode = currentNode.next;
}
}
findPrevious(item) {
let currentNode = this.head;
while (currentNode.next !== null && currentNode.next.element !== item) {
currentNode = currentNode.next;
}
return currentNode;
}
remove(item) {
let previousNode = this.findPrevious(item);
if (previousNode.next !== null) {
previousNode.next = previousNode.next.next;
}
}
}
//테스트
let cities = new LList();
//insert(새 요소, 기존 요소)
cities.insert('Seoul', 'head');
cities.insert('Pusan', 'Seoul');
cities.insert('Gwangju', 'Pusan');
cities.insert('Daegu', 'Gwangju');
cities.display();
// console.log(cities);
console.log('-------삭제 후------');
cities.remove('Pusan');
cities.display();
// console.log(cities);
//수정
class Node {
constructor(element) {
this.element = element;
this.next = null;
this.previous = null; //양방향 연결 리스트 위해 이전 노드의 링크 저장하는 프로퍼티 추가
}
insert(newElement, item) {
let newNode = new Node(newElement);
let current = this.find(item);
newNode.next = current.next;
newNode.previous = current; //양방향 연결 리스트 위해 연결
current.next = newNode;
}
}
currentNode.previous.next
)가 삭제하려는 노드의 다음 노드(currentNode.next
)를 가리키도록 설정currentNode.next.previous
)를 삭제하려는 노드의 previous 값(currentNode.previous
)으로 설정 remove(item) {
let currentNode = this.find(item);
if (currentNode.next !== null) {
//이전 노드의 링크가 삭제하려는 노드의 다음 노드를 가리키도록 설정
currentNode.previous.next = currentNode.next;
//삭제하려는 노드 다음 노드의 previous 프로퍼티를 삭제하려는 노드의 previous 값으로 설정
currentNode.next.previous = currentNode.previous;
//삭제하려는 노드의 next, previous 프로퍼티를 null로 설정
currentNode.next = null;
currentNode.previous = null;
}
}
class Node {
constructor(element) {
this.element = element;
this.next = null;
this.previous = null; //양방향 연결 리스트 위해 이전 노드의 링크 저장하는 프로퍼티 추가
}
}
class LList {
constructor() {
this.head = new Node('head');
}
find(item) {
let currentNode = this.head;
while (currentNode.element !== item) {
currentNode = currentNode.next;
}
return currentNode;
}
insert(newElement, item) {
let newNode = new Node(newElement);
let current = this.find(item);
newNode.next = current.next;
newNode.previous = current; //양방향 연결 리스트 위해 연결
current.next = newNode;
}
display() {
let currentNode = this.head;
while (currentNode.next !== null) {
console.log(currentNode.next.element);
currentNode = currentNode.next;
}
}
/* //단방향 연결시 사용
findPrevious(item) {
let currentNode = this.head;
while (currentNode.next !== null && currentNode.next.element !== item) {
currentNode = currentNode.next;
}
return currentNode;
} */
remove(item) {
let currentNode = this.find(item);
if (currentNode.next !== null) {
//이전 노드의 링크가 삭제하려는 노드의 다음 노드를 가리키도록 설정
currentNode.previous.next = currentNode.next;
//삭제하려는 노드 다음 노드의 previous 프로퍼티를 삭제하려는 노드의 previous 값으로 설정
currentNode.next.previous = currentNode.previous;
currentNode.next = null;
currentNode.previous = null;
}
}
// 유틸리티 함수 - 양방향 연결리스트의 마지막 노드로 이동
findLast() {
let currentNode = this.head;
while (currentNode.next !== null) {
currentNode = currentNode.next;
}
return currentNode;
}
//역순으로 양방향 연결리스트의 요소 출력 (findLast 이용)
displayReverse() {
let currentNode = this.head;
currentNode = this.findLast();
while (currentNode.previous !== null) {
console.log(currentNode.element);
currentNode = currentNode.previous;
}
}
}
//테스트
let cities = new LList();
//insert(새 요소, 기존 요소)
cities.insert('Seoul', 'head');
cities.insert('Pusan', 'Seoul');
cities.insert('Gwangju', 'Pusan');
cities.insert('Daegu', 'Gwangju');
cities.display();
console.log('-------삭제 후------');
cities.remove('Pusan');
cities.display();
console.log('-----역순으로 요소 출력------');
cities.displayReverse();
//output
/*
Seoul
Pusan
Gwangju
Daegu
-------삭제 후------
Seoul
Gwangju
Daegu
-----역순으로 요소 출력------
Daegu
Gwangju
Seoul
*/
헤드의 next 프로퍼티가 자신을 가리킨다는 것
이다. head.next= head