[딩코딩코 2025 코딩테스트 필수 알고리즘] - 13. 큐

본 글은 딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』
강의를 듣고 정리한 내용입니다.
강의와 수업 자료에 수록된 일부 코드와 이미지를 참고하여 발췌·활용하였습니다.

코딩테스트 준비를 체계적으로 하고 싶으시다면, 아래 링크에서 강의를 확인해 보세요

👉 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 보러 가기

본 게시물은 파트너스 활동의 일환으로 작성되었으며, 구매 시 소정의 수수료를 받을 수 있습니다.

---

큐(Queue)

큐란 한쪽 끝으로 자료를 넣고, 반대쪽에서 자료를 뺄 수 있는 선형구조 이다. 이런 자료 구조를 FIFO, First In First Out 이라고 부른다**.**

이런 자료구조가 왜 필요할까? 바로, 순서대로 처리되어야 하는 일에 필요하기 때문이다.

큐의 기능

큐라는 자료구조에서 제공하는 기능은 다음과 같다.

1. enqueue(data) : 맨 뒤에 데이터 추가하기
2. dequeue() : 맨 앞의 데이터 뽑기
3. peek() : 맨 앞의 데이터 보기
4. isEmpty() : 큐가 비었는지 안 비었는지 여부 반환해주기

큐의 구현

이제 큐라는 자료구조를 구현해보자. 큐는 스택과 다르게 시작과 끝의 노드를 모두 가지고 있어야 한다. 따라서, self.head, self.tail 을 가지고 시작한다.

enqueue

만약 현재 큐가 아래와 같다고 해보자. queue = [4] → [2] 큐에 3을 enqueue 하면 [4] → [2] → [3] 가 되어야 한다.

어떻게 화살표를 이어줘야할까? head 와 tail 관점에서 봐보자.

tail 이 가리키는 Node 의 next 에 새롭게 추가되는 new_node 를 연결해줘야 한다. 즉, tail.next = new_node 로 해줘야 한다.

그리고 tail 을 새롭게 추가된 new_node 로 옮겨준다.

위 과정을 코드로 작성해보자.

def enqueue(self,value):
	new_node = Node(value)
	self.tail.next = new_node
	self.tail = new_node

하지만 위와 같이 코드를 작성하면 에러가 발생한다. 바로, 초기 상태를 신경쓰지 않아서 그렇다.

아무것도 큐에 들어가 있지 않은 상태라면, head,tail 모두 None 이다. 그 상태로 queue.enqueue(3) 을 실행하면

new_node = Node(value) # 3
self.tail.next = new_node 

self.tail.next = new_node 에서 문제가 생긴다.

self.tail 은 None 인데 next 를 하니까 에러가 생긴다.

그래서 빈 경우 예외를 처리해줘야 한다.

def enqueue(self, value):              
        new_node = Node(value)             
				**if self.is_empty():                # 만약 비어있다면,**
            self.head = new_node           # head 에 new_node를
            self.tail = new_node           # tail 에 new_node를 넣어준다.
            return

        self.tail.next = new_node          
        self.tail = new_node		

즉, 처음 들어온 노드가 head 이자 tail 이 되도록 설정해줘야 한다.

dequeue

현재 큐가 아래와 같다고 해보자.

[3] → [4] → [5]

큐에 dequeue 하면 어떻게 되어야 할까? 제일 앞에 있는 [3] 이 빠져야 한다.

즉, 다음과 같이 되어야 한다. head tail [4] → [5]

그러기 위해서는 head에 [4] 를 지정하고, [3] 을 반환해주면 된다.

즉, 현재 head 의 값을 다른 변수에 저장해 둔 다음, head 가 지칭하는 노드를 현재 head 의 다음값으로 지정한다. 그리고 아까 저장해둔 head 를 반환해주면 된다.

코드로 구현해보자.

def dequeue(self):
	if self.is_empty():
		return "Queue is empty!"
	
	delete_head = self.head
	self.head = self.haed.next
	
	return delete_head.data

peek

peek 함수는 제일 위에 있는 노드를 반환해주면된다.

def peek(self):
	if self.is_empty():
		return "Queue is empty!"
	
	return self.head.data

is_empty

비어있는지 아닌지는 linked_list 의 제일 위에 있는 노드를 확인해보면 된다.

def is_empty(self):
	return self.head is None