(1) Implementation Stack
-
문제
Stack 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요. -
맴버 변수
데이터를 저장할 Object 타입의 storage
스택의 가장 상단을 가리키는 Number 타입의 포인터 top -
메서드
size(): 스택에 추가된 데이터의 크기를 리턴해야 합니다.
push(): 스택에 데이터를 추가할 수 있어야 합니다.
pop(): 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴해야 합니다. -
주의사항
내장 객체 Array.prototype에 정의된 메서드는 사용하면 안됩니다.
포인터 변수 top의 초기값은 -1, 0, 1등 임의로 지정할 수 있지만 여기서는 0으로 하여 데이터가 추가될 위치를 가리키도록 합니다. -
사용 예시
const stack = new Stack();
stack.size(); // 0
for(let i = 1; i < 10; i++) {
stack.push(i);
}
stack.pop(); // 9
stack.pop(); // 8
stack.size(); // 7
stack.push(8);
stack.size(); // 8
...- 사용 코드
class Stack {
constructor() {
this.storage = {};
this.top = 0; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화 합니다.
}
size() {
return this.top;
}
// 스택에 데이터를 추가 할 수 있어야 합니다.
push(element) {
this.storage[this.top] = element; (element)를 키의 값으로 넣어준다. // ex push(3)을 할경우 -> stack.storage[0] // 3
this.top += 1; // top 카운트를 1늘려준다.
}
// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
pop() {
// 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
if (this.top===0) {
return; // 빈스택에서도 작동하게 해준다.
}
const result = this.storage[this.top -1]; //
this.top-1 이 된다.// push(1) push(2)이렇게 push를 두번 할경우에 storage ={ 0:1, 1:2} // top =2 인 상태이다 . 가장 나중에 들어온 값을 return 해줘야되기 때문에 delete 하기전에 변수(result)에 담는다.
delete this.storage[this.top-1]; //
this.top -= 1; // top 카운트를 1 줄여준다.
return result;
}
}- 예시 값 풀이
storage객체에 push를 통해서 key값은 0~n까지 계속추가되고 element가 키의 값으로 추가된다.
const stack = new Stack();
stack.push(3) // stack에 push(3)을 할 경우에
stack//
Stack {storage: {…}, top: 1}storage: {0: 3}top: 1[[Prototype]]: Object
stack.pop() // stack에 pop을 할 경우에
3
stack
Stack {storage: {…}, top: 0}storage: {}top: 0[[Prototype]]: Object(2) Implementation Queue
-
문제
Queue 구현을 위한 기본적인 코드가 작성되어 있습니다. Queue 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요. -
맴버 변수
데이터를 저장할 Object 타입의 storage
큐의 가장 앞을 가리키는 Number 타입의 포인터 front
큐의 가장 뒤를 가리키는 Number 타입의 포인터 rear -
메서드
size(): 큐에 추가된 데이터의 크기를 리턴해야 합니다.
enqueue(): 큐에 데이터를 추가할 수 있어야 합니다.
dequeue(): 가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터를 리턴해야 합니다. -
주의사항
내장 객체 Array.prototype에 정의된 메서드는 사용하면 안됩니다.
포인터 변수 front, rear의 초기값은 -1, 0, 1등 임의로 지정할 수 있지만 여기서는 0으로 합니다. -
사용 예시
const queue = new Queue();
queue.size(); // 0
for(let i = 1; i < 10; i++) {
queue.enqueue(i);
}
queue.dequeue(); // 1
queue.dequeue(); // 2
queue.size(); // 7
queue.enqueue(10);
queue.size(); // 8
queue.dequeue(); // 3
queue.dequeue(); // 4
queue.size(); // 6
...- 사용 코드
class Queue {
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
size() {
return this.rear-this.front; // dequeue front +1 enqueue rear +1
}
// 큐에 데이터를 추가 할 수 있어야 합니다.
enqueue(element) {
this.storage[this.rear] = element;
this.rear += 1;
} // Stack push하고 같다.
// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
dequeue() {
// 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
if (this.size() <= 0) {
return;
}
const result = this.storage[this.front]; // 앞에 있는게 나가야 하기 때문에 this.front를 해준다.
delete this.storage[this.front];
this.front += 1;
return result;
}
}출처: 코드스테이츠
