Queue
Queue라는 클래스 안에 storage, front, rear 속성이 아래처럼 정의되어 있다. size와 enqueue, dequeue를 구현해 보자.
class Queue {
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
size() - 큐의 현재 요소 개수를 반환한다.
- 값들이 저장되는 storage가 객체이니까 키들의 갯수를 세면 될 것 같다.
Object.keys(this.storage).length;
enqueue(element) - 요소를 큐의 뒤에 추가한다.
- storage 가장 마지막에 element를 추가한다. 즉 , this.rear에 element를 할당한 후 rear++한다.
this.storage[this.rear] = element;
this.rear++
dequeue() - 요소를 큐의 앞에서 제거하고 반환한다.
- storage에 맨 앞에 있는 값 front를 제거한 후 그 다음 값을 front로 할당해 준다.
let rm = this.storage[this.front]; // 제거할 값을 변수에 넣는다.
delete.this.storage[this.front]; // 값을 제거한다.
this.front = this.front++; // 바로 다음에 있던 값을 front로 할당해준다.
return rm; // 제거할 값을 리턴한다.
** 제거할 값을 변수에 넣지 않으면
예를 들어 삭제하고 바로 다른 값을 추가하는 경우라면 return문 전에 front++ 라는 증감문이 있어서 다음 값을 리턴하게 됨
< 전체 코드 >
class Queue {
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0; // 새로운 값 하나가 추가되면 1이 되어야함. 이후에도 ++
}
size() {
// 큐의 현재 요소 개수를 반환한다.
return Object.keys(this.storage).length
}
enqueue(element) { // 요소를 큐의 뒤에 추가한다.
this.storage[this.rear] = element;
// 값이 추가되었으므로 this.rear 값도 커진다.
this.rear++
}
dequeue() { // 요소를 큐의 앞에서 제거하고 반환한다.
let rm = this.storage[this.front];
delete this.storage[this.front];
// 앞에서부터 값이 삭제되니까 다음 front 값은 1커진 다음 값이 된다.
this.front++
return rm
}
}
Stack
stack이라는 클래스 안에 storage, top 이라는 속성이 아래처럼 정의되어 있다. size, push, pop 메서드를 구현해보자.
size() - 스택의 현재 요소 개수를 반환한다.
- 값들이 저장되는 storage 객체의 키의 갯수를 세면 될 것 같다.
Object.keys(this.storage).length;
push(element) - 요소를 스택의 최상단에 추가한다.
- 스택은 top에서만 값을 추가, 삭제할 수 있기 때문에 top에 element를 할당한 뒤 top을 1 증가시키면 된다.
this.storage[this.top] = element;
this.top++;
pop() - 스택의 최상단에서 요소를 제거하고 반환한다.
- 제거할 값을 변수에 넣는다.
- storage에서 최상단에 있는 값을 제거한다.
- 제거할 값의 이전 값을 top으로 할당해 준다.
- 제거할 값을 리턴한다.
let rm = this.storage[this.top -1];
delete this.storage[this.top -1];
this.top = this.top--;
return rm;
< 전체코드 >
class Stack {
constructor() {
this.storage = {}; // class의 속성을 정의 : storage, top
this.top = 0;
}
size() {
return Object.keys(this.storage).length
// return this.rear
}
push(element) { // 요소를 스택의 최상단에 추가한다.
this.storage[this.top] = element;
this.top++
}
pop() { // 스택 최상단에서 요소를 제거하고 반환한다.
// storage에 값이 추가될 때 키는 this.top-1이 됨.
let rm = this.storage[this.top-1];
delete this.storage[this.top-1]
// 값이 하나 빠졌으니까 this.top도 작아져야지
this.top--
return rm;
}
}
'TIL ( CODESTATES)' 카테고리의 다른 글
자료구조 구현하기 - queue, stack, linked list, hash table (0) | 2020.11.06 |
---|---|
Data Structure - Graph, Tree (0) | 2020.11.05 |
구조 분해 할당 - 객체 (0) | 2020.11.02 |
새삼 너무 감격스러워서 / Kahoot 복습 (자료 구조) (0) | 2020.11.02 |
Data Structure - stack, queue (0) | 2020.10.31 |