[TIL] 자료구조 - Stack, Queue, Graph

Today I Learned

Stack & Queue

• 자바스크립트에는 stack, queue가 별도로 구현되어 있지 않기 때문에 배열을 활용하여 유사한 형태로 구현한다. stack을 만들 때는 push()와 pop() 메서드를, queue를 만들 때는 push()(=enqueue)와 shift()(=dequeue) 메서드를 사용할 수 있다.
• 만약 베열을 사용하지 않고 Stack과 Queue 클래스를 만든다면 아래와 같이 만들 수 있다.

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

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

  push(val) {
    const newNode = new Node(val);

    if (this.size === 0) {
      this.bottom = newNode;
      this.top = this.bottom;
    } else {
      this.top.next = newNode;
      this.top = newNode;
    }

    return ++this.size;
  }

  pop() {
    if (this.size === 0) return undefined;
    
    let targetNode = this.bottom;
    
    if (this.bottom === this.top) {
      this.bottom = null;
      this.top =null;
    } else {
      let prevNode = targetNode;
      while (targetNode.next) {
        prevNode = targetNode;
        targetNode = targetNode.next;
      }
      this.top = prevNode;
      this.top.next = null;
    }

    this.size--;
    return targetNode.value;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  enqueue(val) {
    const newNode = new Node(val);

    if (this.size === 0) {
      this.front = newNode;
      this.rear = this.front;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }

    return ++this.size;
  }

  dequeue() {
    if (this.size === 0) return undefined;
    
    const targetNode = this.front;

    if (this.front === this.rear) {
      this.front = null;
      this.rear = null;
    } else {
      this.front = this.front.next;
    }
    this.size--;
    return targetNode.value;
  }
}

Graph : Adjacency Matrix & Adjacency List

• 인접 행렬은 배열로 되어 있어 검색이 빠르나 정점을 추가/삭제하기 어렵다.
• 인접 배열은 정점 추가/삭제는 쉬우나 검색이 인접 행렬보다 더 오래 걸린다.

// Unweighted Graph

class AdjacencyMatrix {
  constructor() {
    this.matrix = [];
    this.vertexNames = [];
  }
  addVertex(vertex) {
    if (!this.hasVertex(vertex)) {
      this.vertexNames.push(vertex);
      const currentLength = this.matrix.length;
      for (let i = 0; i < currentLength; i++) {
        this.matrix[i].push(0);
      }
      this.matrix.push(new Array(currentLength+1).fill(0));
    }
  }
  addEdge(fromVertex, toVertex) {
    const fromIdx = this.vertexNames.indexOf(fromVertex);
    const toIdx = this.vertexNames.indexOf(toVertex);
    if (fromIdx !== -1 && toIdx !== -1) {
      this.matrix[fromIdx][toIdx] = 1;
    }
  }
  hasVertex(vertex) {
    return this.vertexNames.includes(vertex);
  }
  hasEdge(fromVertex, toVertex) {
    const fromIdx = this.vertexNames.indexOf(fromVertex);
    const toIdx = this.vertexNames.indexOf(toVertex);
    if (this.matrix[fromIdx][toIdx] === 1) {
      return true;
    } else {
      return false;
    }
  }
  removeEdge(fromVertex, toVertex) {
    const fromIdx = this.vertexNames.indexOf(fromVertex);
    const toIdx = this.vertexNames.indexOf(toVertex);
    if (fromIdx !== -1 && toIdx !== -1) {
      this.matrix[fromIdx][toIdx] = 0;
    }
  }
  // removeVertex(vertex)
}

class AdjacencyList {
  constructor() {
    this.list = {};
  }
  addVertex(vertex) {
    if (!this.list[vertex]) {
      this.list[vertex] = [];
    }
  }
  addEdge(fromVertex, toVertex) {
    if (this.hasVertex(fromVertex) && this.hasVertex(toVertex)) {
      if (!this.hasEdge(fromVertex, toVertex)) {
        this.list[fromVertex].push(toVertex);
      }
    }
  }
  hasVertex(vertex) {
    return (vertex in this.list);
  }
  hasEdge(fromVertex, toVertex) {
    if (!this.hasVertex(fromVertex)) return false;
    return this.list[fromVertex].includes(toVertex);
  }
  removeVertex(vertex) {
    if (this.hasVertex(vertex)) {
      delete this.list[vertex];
      for (let v in this.list) {
        this.list[v] = this.list[v].filter(el => el !== vertex);
      }
    }
  } 
  removeEdge(fromVertex, toVertex) {
    if (this.hasVertex(fromVertex) && this.hasVertex(toVertex)) {
      if (this.hasEdge(fromVertex, toVertex)) {
        const targetIdx = this.list[fromVertex].indexOf(toVertex);
        this.list[fromVertex].splice(targetIdx, 1);
      }
    }
  }
}