자료구조 - 선형 구조 : 큐

Algoritm에 대해 학습하며, Java를 통해 구현해봅니다.

이 포스팅은 BOJ(Beakjoon Online Judge)의 @jh05013 님 께서 관리하고 계신
단계별로 풀어보기를 기준으로 작성됩니다.

이 포스팅이 올라가는 저장소 : https://github.com/hwk0911

hwk0911 - Overview

혹시 이 포스팅을 보고 알고리즘 공부를 시작하시거나, 복습하시는 분들은
노트와 펜을 준비하시고 직접 그려보면서 하시면 좋습니다.

자료구조의 두 번째 큐(Queue)에 대해 알아본다.

key )

1. 큐의 정의에 대해 알아본다.
2. 큐의 구조에 대해 알아본다.
3. 큐의 작동에 대해 알아본다.

1. 큐 (Queue) 

Queue.jpg

자료구조의 두 번째 큐에 대해 알아본다.

Queue는 Stack과 마찬가지로, 컴퓨터의 가장 기본적인 자료 구조의 한 가지다.
Stack(Last In First Out)과 다르게, First In First Out(FIFO)의 구조를 갖는다.

첨부 한 사진은 사람들이 줄 서 있는 사진인데, 이것이 스택의 기본적인 모습이다.
새치기 없이 줄을 선 순서대로 작업을 한다.

우리 실생활에서 볼 수 있는 예시로, 줄 서기 외에도 프린터의 출력 처리 또는 윈도 시스템의
메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는
상황에서 사용되게 된다.

2. 큐(Queue)의 구조

Stack에서의 입력, 출력은 push, pop으로 표현하였다. 
또, 데이터를 입력받는 위치를 top으로 표현하였다.

하지만 Queue는 입력을 put, 출력을 get으로 표현한다.
또, 데이터를 입력받는 위치를 rear, 데이터를 출력하는 위치를 front라 표현한다.

만약 Queue가 가득 차 데이터를 입력받지 못하는 상황을 Overflow,
반대의 상황, 즉 데이터가 존재하지 않아 출력하지 못하는 상황을 Underflow라 한다.

Queue의 구조를 살펴보자.

Queue.png

Front는 출력할 위치를 나타내고, Rear는 다음 데이터가 들어 올 위치를 나타낸다.

이것이 큐의 기본적인 구조다.
Stack은 한 쪽이 막혀있는 구조고, Queue는 양 쪽이 모두 뚫려있는 구조다.

+이 외에, 선형, 환형 큐 등 파생된 형태가 있지만, 이것은 후에 서술하겠다.

3. 큐(Queue)의 작동

Queue.gif

(저 어설픈 gif파일이 27개의 캡쳐가 들어갔다....)

Rear != 0 && Front == Rear인 경우,
Front = 0, Rear = 0으로 정렬 한다.

Front == 0 && Rear == Queue.length인 경우 Queue는 가득 찬 상태를 의미한다.

Front != 0 && Rear = Queue.length인 경우 새로운 데이터를 입력 받기위해
Front만큼 모든 원소를 앞으로 당긴다.
Rear = Rear - Front, Front = 0

4. 추천 문제

문제 : https://www.acmicpc.net/problem/18258

18258번: 큐 2