queue, stack - pseudocode, implementation

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;
  }
}