큐(Queue)

🥪

🥅목표

큐(Queue)의 기본 연산을 이해한다.

Kotlin과 Python으로 Queue를 구현할 수 있다.

📖개념

---

컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식이다.

🧮연산

---

큐(Queue)는 FIFO(First-In-First-Out)을 따른다.

• add(item) : item을 리스트의 끝부분에 추가한다.

• remove(): 리스트의 첫 번째 항목을 제거한다.

• peek(): 큐에서 가장 위에 있는 항목을 반환한다.

• isEmpty(): 큐가 비어있을 때에 true를 반환한다.

⚒️구현

---

Kotlin으로 구현한 큐 예시 코드는 아래와 같다.

class Queue<T> {
    private val items = mutableListOf<T>()

    fun add(item: T) = items.add(item)
    fun remove() = items.removeAt(0)
    fun peek() = items[0]
    fun isEmpty() = items.isEmpty()
}

위 코드에서는 제네릭(<T>)을 이용하여 다양한 타입의 데이터를 저장할 수 있다.

큐의 기본 연산인 add, remove, peek, isEmpty이 구현되어 있으며, 각각 큐에 아이템을 추가하고, 첫 번째 아이템을 제거하며 반환하고, 첫 번째 아이템을 반환하며, 큐가 비어있는지 확인한다.

이 코드를 사용하여 큐를 만들 때, 우선 Queue 클래스의 객체를 만든다.

val myQueue = Queue<String>()

위 코드에서는 큐 내부에서 사용할 데이터의 타입을 String으로 사용하도록 선언했다(다른 타입을 사용하고자 할 경우, 이를 해당 타입으로 수정하면 됩니다.)

이제, 큐에 데이터를 추가(add)하고, 데이터를 제거(remove)하고, 큐가 비어있는지 확인(isEmpty)하는 등의 기본적인 연산을 수행할 수 있습니다.

myQueue.add("Hello, World!")
myQueue.add("안녕하세요!")
println(myQueue.peek()) // Hello, World!
myQueue.remove()
println(myQueue.peek()) // 안녕하세요!
println(myQueue.isEmpty()) // false

위 코드에서는 먼저 "Hello, World!"와 "안녕하세요!"라는 두 데이터를 큐에 추가한다.

그 다음, 큐에서 가장 먼저 들어간 데이터를 반환하는 peek() 함수를 호출하여 "Hello, World!"를 출력한다. 이후, remove() 함수를 호출하여 큐에서 첫 번째 데이터인 "Hello, World!"를 제거한다. peek() 함수를 한 번 더 호출하여 큐의 첫 번째 데이터가 "안녕하세요!"로 변경되었음을 확인한다. 마지막으로, isEmpty() 함수를 호출하여 큐가 비어있지 않음을 확인한다.

Python으로 구현한 큐

Python queue는 collection 라이브러리를 import하고, deque를 사용하는 것을 추천한다.

from collections import deque

q = deque()
q.append("Hello, World!")
q.append("안녕하세요!")
print(q[0]) // Hello, World!
q.popleft()
print(q[0]) // 안녕하세요!
if len(q) >0:
    print("queue is not Empty") // queue is not Empty

🔡사용사례

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 너비 우선 탐색(BFS == Breadth Frist Search) 구
  • 처리해야 할 노드의 리스트를 저장하는 용도로 큐를 사용한다.
  • 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
  • 노드를 접근한 순서대로 처리할 수 있다.
  • 노드

• 캐시(Cache)구현

• 우선순위가 같은 작업 예약(ex - 인쇄 대기열)

• 선입선출이 필요한 대기열(ex - 티켓 카운터)

• 콜센터 고객 대기시간

• 시스템 메시기 처리

• 프로세스 관리

Uploaded by N2T