Soongle's Morgorithm
큐(Queue) 본문
큐의 정의
큐(queue)는 스택과 마찬가지로 제한적으로 접근할 수 있는 나열 구조이다.
그 접근 방법은 언제나 목록의 끝(front & back)에서만 일어난다.
스택은 한 쪽 끝에서만 자료를 넣거나(back) 뺄(front) 수 있는 선형 구조(FIFO - First In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 오래 전에 푸쉬한 자료부터 나오게 된다.
Queue Library(큐 라이브러리)
스택과 마찬가지로 큐를 구현할 수 있는 방법에는 여러가지가 있다. 배열을 선언하여 만드는 방법과, 라이브러리를 호출하여 이미 구현된 큐와 그 멤버함수를 활용하는 방법이 있다.
큐 라이브러리를 사용하고자 할 때 작성해야할 헤더는 아래와 같다.
#include <queue>스택과 마찬가지로 큐 라이브러리는 C++ 언어에서만 사용이 가능하다.
큐 라이브러리를 통해 큐를 선언하는 방법은 아래와 같다.
queue<요소의 자료형(ex. int, char, double, struct, etc)> 변수명;
-------------예 시---------------
queue<int> que;
queue<int> que[100];
queue<char> que;
queue<(struct)str> que;큐의 멤버함수는 스택과는 달리 6개로 구성되어있다. push, pop, size, empty는 동일하지만, 값을 읽어오는 명령어가 두 가지로 나뉜다. 자세한 명령어 설명은 아래와 같다.
| 명령 | 코드 |
| 큐에 데이터를 삽입한다. | que.push(data) |
| 큐의 front(가장 오래전에 삽입된) 데이터를 삭제한다. | que.pop() |
| 큐의 front 데이터를 읽어온다. | que.front() |
| 큐의 back(가장 최근에 삽입된) 데이터를 읽어온다. | que.back() |
| 큐의 size(삽입된 요소의 갯수)를 반환한다. | que.size() |
| 큐가 비어있는지를 반환한다. | que.empty() |
큐 연습하기
큐에 대한 사용법을 알았으니 큐를 사용하여 코드를 작성해보자! 아래의 문제를 큐를 사용해 해결해보자.
문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
입력 예시
15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front
출력 예시
1
2
2
0
1
2
-1
0
1
-1
0
3
(문제 출처 - 백준온라인(10845번 문제))