[JS] 자바스크립트 스택 구현하기

1. 배열로 스택 구현하기

그냥 JS 배열 메서드를 사용하면 스택을 활용할 수 있다.

 

2. 객체로 스택 구현하기

class Stack {
  #storage;

  constructor() {
    this.#storage = {};
    this.length = 0;
  }

  push(item) {
    this.#storage[this.length++] = item;
  }

  pop() {
    if (!this.length) return;
    
    const item = this.#storage[--this.length];
    delete this.#storage[this.length - 1];

    return item;
  }
}

 

3. 링크드리스트로 스택 구현하기

push(item)

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

class Stack {
  constructor() {
    this.top = null;
    this.length = 0;
  }

  push(item) {
    // 1. 새로운 노드 생성
    const node = new Node(item);

    // 2. 새로운 노드의 next의 참조를 top 노드로 설정
    node.next = this.top;

    // 3. top 참조 변경
    this.top = node;

    this.length++;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

pop()

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

class Stack {
  constructor() {
    this.top = null;
    this.length = 0;
  }

  push(item) {
	/* ... */
  }

  pop() {
    // 스택이 비어 있는 경우
    if (!this.length) return;

    // 1. top의 data 저장
    const item = this.top.data;

    // 2. top 참조 변경
    this.top = this.top.next;

    this.length--;

    // 3. 이전 top data 반환
    return item;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.pop()); // 3
console.log(stack.pop()); // 2
console.log(stack.pop()); // 1
console.log(stack.pop()); // undefined

최종코드

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

class Stack {
  constructor() {
    this.top = null;
    this.length = 0;
  }

  push(item) {
    const node = new Node(item);
    node.next = this.top;
    this.top = node;

    this.length++;
  }

  pop() {
    if (!this.length) return;

    const item = this.top.data;
    this.top = this.top.next;

    this.length--;

    return item;
  }
}