자바스크립트로 보는 큐

Doozuu·2025년 12월 27일
queue자바스크립트큐

알고리즘&자료구조 (JS)

목록 보기
26/32

큐(Queue)는 어떤 자료구조인가?

큐는 선입선출(FIFO)의 규칙을 가지는 자료구조이다.
즉, 가장 먼저 넣은 것이 가장 먼저 나오는 구조이다. (일반적으로 매장에서 물건을 팔 때 가장 오래전에 들어온 물건을 먼저 파는 것과 동일하다고 생각하면 된다.)


큐는 언제 쓰이는가?

  • 가장 먼저 들어온 것을 먼저 처리해야 할 때
  • BFS 탐색할 때

큐는 어떻게 구현할 수 있는가?

자바스크립트에서 push, shift 메서드를 사용하면 일반 배열로 큐를 구현할 수 있지만, 시간 복잡도 이슈가 있다.
push는 단순히 배열 마지막에 요소를 추가하기 때문에 O(1)의 시간 복잡도를 가지지만, shift는 맨 앞의 요소를 제거하고 다른 요소들을 하나씩 앞으로 이동해야 하기 때문에 O(n)의 시간 복잡도를 가지게 된다.
따라서 직접 클래스로 구현하는 것이 좋다.
이때 맨 뒤로 값을 추가하고 맨 앞의 값을 반환하므로 맨 앞과 맨 뒤의 위치를 저장하는 변수가 각각 있어야 한다.

  • 필요한 프로퍼티 : 값을 저장할 객체(storage), 맨 앞을 가리키는 인덱스(front), 맨 뒤를 가리키는 인덱스(rear)
  • 필요한 메서드 : 큐 사이즈(size), 데이터 추가(enqueue), 데이터 삭제(dequeue), 그외 비어있는 여부를 나타내는 empty, 맨 앞의 요소를 반환하는 head, 맨 뒤의 요소를 반환하는 back 등의 메서드도 추가할 수 있다.

enqueue는 맨 뒤에 값을 추가하고 맨 뒤의 인덱스를 증가하는 방식으로 구현할 수 있고, dequeue는 맨 앞의 값을 제거하여 반환하고 맨 앞의 인덱스를 증가하는 방식으로 구현할 수 있다.

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

    size(){
        return this.rear - this.front;
    }

    enqueue(val){
        this.storage[this.rear] = val;
        this.rear++
    }

    dequeue(){
        if(this.size() === 0){
            return undefined
        }

        const val = this.storage[this.front];
        delete this.storage[this.front];
        this.front++;
     
        if(this.front === this.rear){
            this.front = 0;
            this.rear = 0;
        }
     
        return val;
        
    }
}

const queue = new Queue()

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
console.log(queue.dequeue())
console.log(queue.dequeue())
console.log(queue.dequeue())
console.log(queue.size())

관련 문제 풀어보기

[백준] 큐

문제에서 주어진 조건대로 아래 6가지 연산을 구현한다.

  • push X: 정수 X를 큐에 넣는 연산이다.
  • pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 큐에 들어있는 정수의 개수를 출력한다.
  • empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
  • front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

주의 : 프로퍼티 이름이 메서드 이름과 겹치면 덮어씌워지기 때문에 프로퍼티 이름을 this.front 대신 this.head로 사용해주었다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input.shift();
const answer = [];

class Queue{
  constructor(){
    this.storage = {};
    this.head = 0;
    this.rear = 0;
  }

  size(){
    return this.rear - this.head;
  }

  empty(){
    return Number(this.size() === 0);
  }

  push(val){
    this.storage[this.rear] = val;
    this.rear++;
  }

  pop(){
    if(this.empty()) return -1;

    const removed = this.storage[this.head];
    delete this.storage[this.head];
    this.head++;

    if(this.head === this.rear){
      this.head = 0;
      this.rear = 0;
    }

    return removed;
  }

  front(){
    if(this.empty()) return -1;
    return this.storage[this.head];
  }

  back(){ 
    if(this.empty()) return -1;
    return this.storage[this.rear - 1];
  }
}

const queue = new Queue();

for(let i=0;i<N;i++){
  const command = input[i];

  if(command === "pop"){
    answer.push(queue.pop())
  }else if(command === "size"){
    answer.push(queue.size())
  }else if(command === "empty"){
    answer.push(queue.empty())
  }else if(command === "front"){
    answer.push(queue.front())
  }else if(command === "back"){
    answer.push(queue.back())
  }else{
    const [c, n] = command.split(' ');
    if(c === "push") queue.push(Number(n));
  }
}

console.log(answer.join('\n'));

[백준] 요세푸스 문제

처음에 큐로 어떻게 풀어야 할 지 아이디어를 얻지 못 하다가 힌트를 찾아보고 dequeue, enqueue를 반복하면 원형처럼 풀 수 있다는 것을 알게되었다.
(K - 1 번 만큼 꺼내서 뒤에 다시 넣으면 원형으로 돌리는 것과 같음.)
그런데 dequeue, enqueue가 최대 N*K 만큼 발생하여 메모리 초과가 발생했다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [N, K] = input[0].split(' ').map(Number);
const answer = [];

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

  size(){
    return this.rear - this.front;
  }

  enqueue(val){
    this.storage[this.rear] = val;
    this.rear++
  }

  dequeue(){
    if(this.size() === 0) return undefined;
    const val = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;

    if(this.front === this.rear){
      this.front = 0;
      this.rear = 0;
    }

    return val;
  }
}

const queue = new Queue();

for(let i=1;i<=N;i++){
  queue.enqueue(i);
}

for(let i=0;i<N;i++){
  for(let j=1;j<K;j++){
    const val = queue.dequeue()
    queue.enqueue(val)
  }
  answer.push(queue.dequeue())
}

console.log('<' + answer.join(', ') + '>');

다른 방식으로 인덱스를 규칙을 이용해 구하는 방식으로 풀었더니 성공했다.
splice도 시간복잡도 면에서 좋지는 않지만 입력 범위가 최대 5000이라 O(n)은 범위 안에 들어서 가능했다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [N, K] = input[0].split(' ').map(Number);
const answer = [];
const queue = Array.from({length:N}, (_,i) => i+1);
let idx = 0;

for(let i=0;i<N;i++){
  idx = (idx - 1 + K) % queue.length
  answer.push(queue[idx])
  queue.splice(idx,1)
}

console.log('<' + answer.join(', ') + '>');

[백준] 뱀

규칙

  • 벽에 부딪히거나 몸과 부딪히면 끝
  • 벽은 상하좌우 테두리
  • (0,0)에서 시작, 초기 길이는 1, 오른쪽으로 출발
  • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
  • 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
  • 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
  • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

풀이 방식

  1. 빈칸 : 0, 뱀 : 1, 사과 : 2로 보드에 저장한다.
  2. 뱀의 초기 위치 정보를 큐에 저장한다.
  3. 뱀 머리를 꺼내서 다음 머리 위치를 계산한다.
  • 만약 다음 위치가 벽이거나 뱀의 몸이면 종료한다.
  • 이동 가능하면 뱀 꼬리에 추가한다.
  • 이동하는 위치에 사과가 없으면 꼬리를 제거하고 빈칸으로 표시한다.
  1. 방향 전환이 있으면 오른쪽/왼쪽에 따라 방향을 전환한다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
let idx = 0;
const N = +input[idx++];
const board = Array.from({length: N}, () => Array(N).fill(0));
const K = Number(input[idx++]);

for(let i=0;i<K;i++){
  const [x,y] = input[idx++].split(' ').map(Number)
  board[x-1][y-1] = 2;
}

const L = Number(input[idx++]);
const turns = {};
for (let i = 0; i < L; i++) {
  const [t, d] = input[idx++].split(' ');
  turns[Number(t)] = d;
}

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

  size(){
    return this.rear - this.front
  }

  enqueue(val){
    this.storage[this.rear] = val;
    this.rear++;
  }

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

    const val = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;
    
    return val;
  }

  head(){
    return this.storage[this.front]
  }

  back(){
    return this.storage[this.rear - 1]
  }
}

const snake = new Queue();

let time = 0;
let dir = 0;
const direction = [[0,1],[1,0],[0,-1],[-1,0]]; 

snake.enqueue([0,0])
board[0][0] = 1

while(true){
  const [x, y] = snake.back();
  const [dx, dy] = direction[dir];

  const nx = x+dx;
  const ny = y+dy;

  time++

  if(nx < 0 || nx >= N || ny < 0 || ny >= N) break;
  if(board[nx][ny] === 1) break;

  const isApple = board[nx][ny] === 2; 
  
  snake.enqueue([nx,ny])
  board[nx][ny] = 1;

  if(!isApple){
    const [tx,ty] = snake.dequeue();
    board[tx][ty] = 0;
  }

  if(turns[time]){
    if(turns[time] === "D") dir = (dir+1)%4
    else dir = (dir+3)%4
  }
}

console.log(time);

[백준] 좋은 친구

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [N,K] = input.shift().split(' ').map(Number);
const count = Array(21).fill(0)
let answer = 0;

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

  size(){
    return this.rear - this.front
  }

  enqueue(val){
    this.storage[this.rear] = val;
    this.rear++
  }
  
  dequeue(){
    if(this.size() === 0) return undefined;

    const val = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;

    return val
  }

  head(){
    return this.storage[this.front]
  }
}

const queue = new Queue();

for(let i=0;i<N;i++){
  const len = input[i].length
  answer += count[len]
  queue.enqueue(len)
  count[len]++

  if(queue.size() > K){
    const old = queue.dequeue()
    count[old]--
  }
}

console.log(answer);
profile
Doozuu
모든게 새롭고 재밌는 프론트엔드 새싹
이전 포스트

동적 프로그래밍(DP)

다음 포스트

자바스크립트로 보는 덱

0개의 댓글