[자료구조] 스택과 비슷한 자료구조 큐에 대해서

(00) :: Introduciton

대학교 학부 시절때 공부했던 이론 내용들을 리마인드 하기 위해서 작성된 게시글입니다.

정확하지 않은 내용이 포함되어 있는 경우, 댓글로 남겨주시면 수정할 수 있도록 하겠습니다.

이 게시글은 한 번에 완성되는 게시글이 아니며 내용을 지속적으로 추가할 예정입니다.

 

(01) :: Define a Concept

큐 자료구조는 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조로 먼저 들어간 원소가 제일 먼저 나오는 선입선출 방식으로 동작합니다. 다른 말로는 FIFO(First In, First Out) 자료구조라고 부르기도 합니다.

예시) 공항수속

---------------------------------
|  3(F) |   4   |   7   |  2(R) |
---------------------------------

F = Front
R = Rear

 

(02) :: Property

큐도 스택과 마찬가지로 특정 위치에서만 원소를 삭제하거나 뺄 수 있게 제한을 둔 덕분에 다양한 특성을 갖고 있습니다.

#1 원소를 추가나 제거하는 경우 O(1) 비용 밖에 들지 않는다.
#2 제일 앞(Front), 뒤(Rear)의 원소 확인하는 경우도 O(1) 비용 밖에 들지 않는다.
#3 제일 앞/뒤가 아닌 나머지 원소들의 확인이나 변경이 원칙적으로 불가능하다.

#1과 #2의 경우 스택과 거의 유사하기 때문에 생략합니다.

다른 점은 스택은 맨 위에 있는 포지션(Top)을 다루지만, 큐는 맨 앞, 맨 뒤 포지션(Front, Rear)을 다룹니다.

Front, Rear 명칭을 Head, Tail로 부르기도 합니다.

 

#3도 스택과 마찬가지로 배열을 활용하면 다른 위치의 원소 확인이 가능하도록 만들 수는 있으나 실제로 많이 사용되지는 않습니다.

 

(03) :: Queue, How it works?

큐의 특성 부분에서 다룬 큐의 2가지 기능에 대해서 알아봅시다.

#1 원소를 추가나 제거하는 경우 = O(1)
#2 제일 앞(Front), 제일 뒤(Rear)의 원소 확인하는 경우 = O(1)

 

#1의 경우 값을 추가하고 Front와 Rear의 위치를 변경해 주면 됩니다.

1. 크기 4의 큐를 만든다.
---------------------------------
|   X   |   X   |   X   |   X   |
---------------------------------

2. 3을 추가한다.
---------------------------------
| 3(F,R)|   X   |   X   |   X   |
---------------------------------
F = Front
R = Rear

3. 2를 추가한다.
-------------------------------
| 3(F) | 2(R) |   X   |   X   |
-------------------------------
F = Front
R = Rear

 

#2의 경우 큐의 Front, Rear의 위치를 통해 값에 접근해서 조회하면 됩니다.

4. Front에 접근해 데이터를 출력합니다. (Rear도 동일합니다.)
-------------------------------
| 3(F) | 2(R) |   X   |   X   |
-------------------------------
F = Front
R = Rear

-- 출력 결과 --
------------------
| 터미널 출력: 3 |
------------------

 

(04) :: Queue, How to use in Java?

- 자바 API 활용한 사용 방법

- 실제 구현

 

(FF) :: Reference

참고자료는 다음과 같습니다.

# -- Thanks to --
#1 blog.encrypted.gg