[JS] Stack,Queue,Deque 자료구조

Stack

• 한쪽에서만 자료를 넣고 뺄 수 있는 선형 자료구조
• 후입선출 (Last In First Out)

const myStack = [];
myStack.append(1);
myStack.push(2);
myStack.pop(); // 2

Queue

• 한쪽에서 삽입, 다른 한쪽에서 삭제 작업이 이루어지는 선형 자료구조
• 선입선출 (First In First Out)

const myQueue = [];
myQueue.push(1);
myQueue.push(2);
myQueue.shift(); // 1

Deque

• 양쪽에서 삽입과 삭제가 가능한 자료구조
• 스택과 큐의 연산을 모두 지원
• 삽입과 삭제의 시간복잡도는 O(1)로 유지해야함

JS code 구현

• shift를 이용한 구현은 시간복잡도 O(N)
• 연결리스트를 이용한 구현

class Node{
  constructor(value){
  	this.value = value;
    this.next = null;
    this.prev = null;
  }
}

앞에서 추가/제거

class Deque{
  constructor(){
  	this.init();
  }
  init(){
  	this.count = 0; // 인덱스의 갯수
    this.front = null; // 맨 앞의 노드
    this.rear = null; // 맨 뒤의 노드
  }
  unshift(value){ // 맨 앞에 추가
    const node = new Node(value);
    
    if(!this.front){
      this.front = node;
      this.rear = node;
    } else {
      const cachedPrevFront = this.front;
      cachedPrevFront.prev = node;
      this.front = node;
      node.next = cachedPrevFront;
    }
    
    this.count += 1;
    return this.count;
  }
  
  shift(){
  	if (this.count ===0) return null;
    const value = this.front.value;
    if (this.count ===1){
      this.init();
    } else {
      this.front = this.front.next;
      this.front.prev = null;
      this.count -= 1;
    }
    
    return value;
  }
}

뒤에서 추가/제거

class Deque {
  // ... 위의 내용 생략
  
  push(value){
    const node = new Node(value);
    
    if (this.count ===0){
      this.front = node;
      this.rear = node;
    } else {
      const cachedPrevRear = this.rear;
      cachedPrevRear.next = node;
      node.prev = cachedPrevRear;
      this.rear = node;
    }
    this.count += 1;
    
    return this.count;
  }
  
  pop(){
  	if (this.count ===0) return null;
    const value = this.rear.value;
    
    if (this.count ===1) {
      this.init();
    } else {
      this.rear = this.rear.prev;
      this.rear.next = null;
      this.count -= 1;
    }
    
    return value;
  }
}