[Data Structure] Queue

Queue

Queue(큐)는 Stack과 더불어 가장 기본이 되는 Data Structure입니다. DS를 처음 접하는 분이라면 이름만 듣고는 다소 생소할 수 있으나, 사실은 일상 생활에서도 쉽게 접할 수 있는 개념이니 잘 따라와 주세요!

 

---

 

특징

Queue는 Stack과는 조금 다른 특징을 가지고 있습니다. 바로 FIFO 인데요, FIFO는 First In, First Out 이라는 뜻 입니다. 이러한 방식은 일상생활에서도 쉽게 볼 수 있습니다. 편의점 알바를 해보신 분들이라면 "선입선출"이라는 말을 들어보신 적이 있으실 것 입니다. 바로 이것이 FIFO의 대표적인 예시입니다.

또 다른 예를 들어 볼까요? 어떠한 프린터가 있다고 생각해 봅시다. 이 프린터에 1부터 n까지 문서를 출력해달라고 요청이 들어왔습니다. 그렇게 되면 프린터는 어떻게 일을 처리해야 할까요? 당연히 가장 먼저 출력 요청을 한 1번부터 출력을 하게 될 것입니다. 만약 Stack 방식으로 출력을 하면 먼저 신청한 사람은 화가 나겠죠? 이를 그림으로 나타내면 다음과 같습니다.

Queue를 따르는 프린터

대기 번호는 입력 순서입니다. 출력 순서는 말 그대로 출력하는 순서이구요. 그렇게 되면 입력되는 대로 출력이 된다고 이해할 수 있겠죠? 이게 바로 Queue의 가장 큰 특징인 FIFO 입니다.

---

각종 연산들

Queue에도 Stack과 비슷한 연산들이 있습니다. Stack처럼 원소를 넣고 뺄 때 사용할 수 있는 Push()와 Pop()이 대표적이며, 그 외의 연산들도 Stack과 닮아있습니다. 어떤 연산들이 있을 수 있는지 볼까요?

1. CreateQueue()

이 연산은 Queue를 만들어주는 연산입니다. Stack과 마찬가지로 기본적으로 초기에 생성된 Queue는 비어있습니다.

2. Push()

이 연산은 Queue에 원소를 추가할 때 사용합니다. Queue의 맨 뒤에 값이 추가됩니다.

3. Pop()

이 연산은 Queue의 맨 앞 원소(front)를 꺼낼 때 사용합니다.

4. Full_check()

이 연산은 Queue가 꽉 차 있는지 확인하는 연산입니다. 꽉 차있다면 True를, 그렇지 않다면 False를 반환합니다.

5. Empty_check()

이 연산은 Queue가 비어있는지 확인하는 연산입니다. 비어있다면 True를, 그렇지 않다면 False를 반환합니다.

---

Queue와 Stack은 넣고 빼는 방식에서 차이가 있을 뿐, 기본적인 연산은 큰 차이가 없습니다. 만약 직접 구현하게 된다면 해당 부분을 조금 신경써서 구현하되, 전체적은 뼈대는 동일하게 작성해 주시면 됩니다.

Queue는 일반적으로 생각했을 때, 매우 당연해 보이는 구조입니다. 이 때문인지 많은 알고리즘이 Queue를 채택하고 있습니다. Queue는 Data Structure의 가장 기본이 되는 구조 중 하나이지만, 이를 제대로 알아야 앞으로 배우는 Computer Science가 더 편안하게 느껴질 수 있을 것 입니다!