[자료구조][알고리즘] 큐

휘·2024년 4월 16일

알고리즘 자료구조 큐

자료구조/알고리즘

목록 보기

4/6

큐

먼저 들어간 데이터가 먼저 나오는 FIFO 형식의 자료구조

큐의 메서드

enqueue
dequeue
peek
isEmpty
count

구현 방식

여러가지 방법이 있지만, 가장 많이 사용하는 방법은 배열+포인터 혹은 원형큐이다.

배열과 포인터를 쓰는 게 가장 간편해보이지만, 공간을 효율적으로 사용할 수 없다는 단점이 있다. 따라서 원형큐를 사용하는 방법이 best이다.

원형큐를 구현하는 방법은, 포인터가 가리키는 곳에 데이터를 놓고 점점 포인터의 인덱스를 증가시켜주면 된다.

front: 가장 먼저 들어온 인덱스
Rear: 가장 마지막에 들어온 원소의 인덱스 + 1

하지만, 원형큐도 큐의 사이즈를 잡아주지 않는다면 문제가 된다. 그렇다면, 링크드리스트를 활용해야한다.

백준 2164
시도한 방법 1: 배열 -> 이 방법은 시간 초과가 난다.

import Foundation

let n = Int(readLine()!)!
var queue = Array(1...n)

while queue.count > 1 {
    queue.removeFirst()
    queue.append(queue.removeFirst())
}

print(queue.first!)

N의 범위가 1 ≤ N ≤ 500,000이다. 근데, removeFirst 자체가 O(n)이고 removeFirst가 while문을 돌기 때문에 총 시간복잡도는 O(n^2)이 된다. 그렇게 되면 최대 연산이 250,000,000,000여서 모든 케이스에 대해 1초 이내에 수행하기 어렵다.

시도한 방법2: 배열+포인터

import Foundation

let n = Int(readLine()!)!
var queue = Array(1...n)
var front = 0

while true {
    if queue.count - front == 1 {
        break
    }
    
    front += 1 // 첫 번째 카드를 버리기
    queue.append(queue[front]) // 다음 카드를 배열의 끝으로 이동
    front += 1 // 다음 카드로 인덱스를 이동
}

print(queue[front])

출처
SeSAC 메모리스

휘

이전 포스트

[자료구조][알고리즘] 스택

다음 포스트

[자료구조][알고리즘] 큐