자료구조 - Queue(feat. Java, Python)

큐(Queue)란?

큐는 배열을 기반으로 만든 자료구조이다. 가장 먼저 넣은 요소를 가장 먼저 꺼낼 수 있다는 것이 특징이다.

예시로 터널에 들어간 차량, 음식점 줄서기 등이 있다.

 

 

개인적으로 자료구조에서 인간적으로 합당하다고 생각하는 구조이다...

들어가기에 앞서 큐에서 자주 사용하는 용어 2개를 소개한다.

• Enqueue : 큐에 요소 넣는 기능
• Dequeue : 큐에 요소 꺼내는 기능

특징

몇가지 특징을 짧게 알아보자

1. FIFO : First input First out 의 약자로 선입선출 이라고 많이 말한다. 큐의 가장 큰 특징이자 중요한 개념이다.
2. 큐는 꼬리 쪽으로만 요소가 들어가고 헤드 쪽으로만 요소가 나가게 된다.
3. 컴퓨터 버퍼에서 주로 사용한다.

 

 

Python Queue

파이썬에서는 큐는 내부구현이 되어있다. 큐를 잘 이해하려면 list만을 활용하여 구현을 해보는 것이 방법이다.

간단하게 구현해 보았다.

class Queue(list):
  enqueue = list.append

  # 값 보여주면서 가장 처음인 요소 제거
  def dequeue(self):
    return self.pop(0)

  # 가장 처음 요소 출력
  def peek(self):
    return self[0]

 

Java Queue

자바 Collection에 구현되어 있는 큐를 쉽게 사용할 수 있다. 큐를 사용할 때는 LinkedList가 import 되어 있어야 사용이 가능해 진다. 즉, 내부 로직은 LinkedList로 만들어져 있다.

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> queue = new LinkedList<>();

Queue 요소 추가/제거

요소를 추가하기 위해서는 add(),offer() 사용하면 된다.

 

 

 

Method	설명
add(E e)	배열의 꼬리에 요소 추가
offer(E e)	배열의 꼬리에 요소 추가

 

공식문서 따르면 요소를 추가히기 위해서 두 가지 방식을 사용하면 되고, 차이점으로는 add()는 Throws exception 즉, 현재 사용 가능한 공간이 없는 경우 IgalledStateException을 던진다. 하지만 offer()는 현재 사용 가능한 공간이 없는 경우 false만 반환한다.

Queue<Integer> queue = new LinkedList<>();

queue.add(1);
queue.add(2);
queue.offer(3);

System.out.println(arr); // [1,2,3]

값을 제거하기 위해서는 remove(), poll(), clear()가 있다.

 

Method	설명
remove()	큐가 비어 있는 경우 NoSuchElementException 에러 발생
poll()	큐가 비어 있을 경우 null 반환
clear()	큐 비우기

 

Queue<Integer> queue = new LinkedList<>();

queue.add(1);
queue.add(2);
queue.offer(3);

System.out.println(arr); // [1,2,3]

queue.remove(); // [2, 3]
queue.poll(); // [3]

 

끝으로

큐가 내부로직이 LinkedList인 것을 보아 LinkedList를 구현을 통해 이해하고, 내부로직을 활용한다면 Queue또한 자동적으로 이해가 갈 것이라고 생각한다. 다음 포스팅에는 LinkedList를 보다 심도있게 다룰 예정이다.

 

Referance

참고 자료
초보몽키 개발블로그
이것이 자바다
공식문서