[JS] 자료구조 - 큐 & 스택

🐣 소개

다른 언어들과 달리, Javascript에는 내장된 Stack, Queue, Deque 객체가 없다.
따라서 Array 객체를 사용하여 Stack, Queue, Deque를 구현하게 된다.

Array는 크기를 동적으로 늘였다 줄일 수 있다. 즉, C++과 같은 정적 언어에서의 배열과 달리 원소를 추가하면 길이가 늘어나고, 임의의 인덱스의 요소에도 접근・할당할 수 있다.

(Array는 프로퍼티 키가 숫자열인 객체)

◻ 스택 (Stack)

• 데이터를 집어넣을 수 있는 선형(linear) 자료형
• 나중에 집어넣은 데이터가 먼저 나오는, LIFO(Last In First Out) 구조이다.
• 데이터를 집어넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peek 등의 작업을 할 수 있다.

주요 작업
push() : 스택에 원소 추가
pop() : 스택 맨 위의 원소 삭제하며 반환
peek() : 스택 맨 위의 원소를 반환
size() : 스택의 원소의 총 갯수를 반환
isEmpty() : 스택이 비었는지 확인

class Stack {
  constructor() {
    this.arr = [];
  }
  push(item) {
    this.arr.push(item);
  }
  pop() {
    return this.arr.pop();
  }
  peek() {
    return this.arr[this.arr.length - 1];
  }
  size() {
    return this.arr.length;
  }
  isEmpty() {
    return this.arr.length === 0;
  }
}

const stack = new Stack();
stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.pop(); // [1]

실전 적용

괄호 문자열이 입력되면, 괄호의 쌍이 올바르게 짝지어지는 경우 "YES", 그렇지 않은 경우 "NO" 출력하는 코드를 작성해보자.

const solution = (s) => {
  let answer = "YES";
  let stack = [];

  for (let x of s) {
    if (x === "(") stack.push(x);
    else {
      if (stack.length === 0) return "NO";
      stack.pop();
    }
  }
  if (stack.length > 0) return "NO"; // 모든 원소 다 돌았는데 stack에 남아있으면
  return answer;
};

console.log(solution("(())))")); // NO

관련 문제 모음

• 백준 - 쇠막대기
• 백준 - 요세푸스
• 프로그래머스 - 크레인 인형뽑기

◻ 큐 (Queue)

• 데이터를 집어넣을 수 있는 선형(linear) 자료형
• 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조이다.
• 데이터를 집어넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있다.

주요작업
enqueue() : 큐에 자료를 넣는다.
dequeue() : 큐의 자료를 뺀다
front() : 큐의 가장 앞에 있는 자료를 보는 연산
back(): 큐의 가장 뒤에 있는 자료를 보는 연산
isEmpty() : 큐가 비어있는지 아닌지 알아보는 연산
size() : 큐에 저장되어 있는 자료의 개수를 알아보는 연산

class Queue {
  constructor() {
    this.arr = [];
  }
  enqueue(value) {
    this.arr.push(value);
  }
  dequeue() {
    return this.arr.shift();
  }
  size() {
    return this.arr.length;
  }
  peek() {
    return this.arr[0];
  }
  isEmpty() {
    return this.arr.length === 0;
  }
}

const queue = new Queue();
queue.enqueue(1); // [1]
queue.enqueue(2); // [1, 2]
queue.enqueue(3); // [1, 2, 3]

queue.dequeue(); // [2, 3]
queue.size(); // 2

console.log(queue);

• Javascript 배열에서의 shift() 메서드
  : shift() 메서드는 배열에서 첫 번째 요소를 제거하고, 제거된 요소를 반환한다. 이 메서드는 배열의 길이를 변하게 한다.
• Javascript 배열에서의 unshift() 메서드
  : unshift() 메서드는 새로운 요소를 배열의 맨 앞쪽에 추가하고, 새로운 길이를 반환한다.

실전 적용

프로그래머스 - 이중우선순위큐

const solution = (operations) => {
  let answer = [];
  for (let i = 0; i < operations.length; i++) {
    const num = Number(operations[i].substring(2)); //string 객체의 시작 인덱스로 부터 종료 인덱스 전 까지 문자열의 부분 문자열을 반환 후 Number로 변환
    const char = operations[i].substring(0, 1);
    switch (char) {
      case "I":
        answer.push(num);
        answer.sort((a, b) => a - b); // 오름차순 정렬
        break;
      case "D":
        if (num === 1) {
          //최댓값 삭제
          answer.pop();
        } else {
          //최솟값 삭제
          answer.shift();
        }
        break;
    }
  }
  if (answer.length === 0) {
    return [0, 0];
  }

  return [answer[answer.length - 1], answer[0]];
};

console.log(solution(["I 7", "I 5", "I -5", "D -1"])); // [7, 5]

관련 문제 모음

• 백준 - 큐 구현
• 프로그래머스 - 스택/큐 문제모음

◻ 큐로 우선순위 큐 구현하기

기본 큐의 변형으로, 원소가 우선순위에 따라 추가되는 우선순위 큐를 구현해보자.

class QueueElement {
  constructor(element, priority) {
    this.element = element;
    this.priority = priority;
  }
}
class PriorityQueue {
  constructor() {
    this.items = [];
  }

  enqueue(data, priority) {
    const queueElement = new QueueElement(data, priority);

    if (this.isEmpty()) {
      this.items.push(queueElement);
    } else {
      let added = false;
      for (let i = 0; i < this.items.length; i++) {
        if (queueElement.priority < this.items[i].priority) {
          this.items.splice(i, 0, queueElement);
          added = true;
          break;
        }
      }
      if (!added) {
        this.items.push(queueElement);
      }
    }
  }

  dequeue() {
    return this.items.shift();
  }
}

const pq = new PriorityQueue();
pq.enqueue(100, 2);
pq.enqueue(10, 1);
console.log(pq); // [ { element: 10, priority: 1 }, { element: 100, priority: 2 } ] 

◻ 덱 (Deque)

• 덱은 Double-ended Queue 의 약자
• 스택과 큐를 합친 자료구조로, 양 끝에서 데이터를 넣거나 추출할 수 있다.

주요작업
push_front() : 덱의 앞에 자료를 넣는 연산
push_back() : 덱의 뒤에 자료를 넣는 연산
pop_front() : 덱의 앞에서 자료를 빼는 연산
pop_back() : 덱의 뒤에서 자료를 빼는 연산
front() : 덱의 가장 앞에 있는 자료를 보는 연산
back() : 덱의 가장 뒤에 있는 자료를 보는 연산

class Deque {
  constructor() {
    this.data = [];
    this.rear = 0;
  }

  push_front(element) {
    this.data.unshift(element);
    this.rear = this.rear + 1;
  }

  push_back(element) {
    this.data[this.rear] = element;
    this.rear = this.rear + 1;
  }

  pop_front() {
    if (this.isEmpty() === false) {
      this.rear = this.rear - 1;
      return this.data.shift();
    }
    return false;
  }

  pop_back() {
    if (this.isEmpty() === false) {
      this.rear = this.rear - 1;
      return this.data.pop();
    }
    return false;
  }

  length() {
    return this.rear;
  }

  isEmpty() {
    return this.rear === 0;
  }

  const deque = new Deque();
  deque.push_back(1); // [1]
  deque.push_back(3); // [1, 3]
  deque.push_front(0); // [0, 1, 3]
  deque.pop_back(); // [0, 1]
}

관련 문제모음

• 백준 - 덱 구현
• 백준 - 회전하는 큐