[알고리즘&자료구조] 큐 - C++/파이썬

큐란?

원소가 넣은 순서대로 나오는 자료구조(First in First out-FIFO)

위 그림처럼 1->2->3의 순서로 들어가면 1->2->3의 순서로 나온다.

큐는 대기줄을 생각하면 되는데 예를 들어 게임 접속 대기열을 큐라고 하는 것을 떠올리면 된다.

*큐는 맨 앞과 맨 뒤의 원소들만 고려하기 때문에 나머지 원소들에 대해서는 알 수 없다.

큐 메소드

큐의 메소드로 다음과 같은 것들이 있다:

• front - 맨 앞의 원소 반환
• back - 맨 뒤의 원소 반환
• empty - 큐가 비어있는지 확인: 비어있으면 0 아니면 1
• pop - 맨 앞의 원소 삭제
• push - 맨 뒤에 원소 삽입
• size - 큐의 길이 반환

언어마다 차이가 있을 수 있으나 위 메소드들은 거의 필수적으로 있다고 봐도 무방하다.

스택의 언어별 사용 - C++/파이썬

C++

큐 헤더를 통해 사용 - #include <queue>

#include <queue>

int main() {
    std::queue<int> q;
    q.push(1); // q: 1
    q.push(2); // q: 2 1
    q.pop(); // q: 2
    q.push(2);
    cout << q.front() << endl; // 1 출력
    cout << q.back() << endl; // 2 출력
    cout << q.size() << endl; // 2 출력
    cout << q.empty() << endl; // 0 출력
}

파이썬

collections 라이브러리의 deque 클래스 사용

*deque는 정확히는 양쪽에서 원소를 삽입하고 삭제할 수 있는 double-ended queue지만 편의를 위해 보통 이 클래스를 사용한다. (리스트를 사용할 수도 있지만 속도면에서 deque가 더 빠르다||queue 라이브러리도 있긴 하다.)

from collections import deque

q = deque()
q.appendleft(1) # [1]
q.appendleft(2) # [2, 1]
q.pop() # [2]
q.appendleft(3) # [3, 2]
print(len(q)) # 2
print(q[0]) # 3
print(q[-1]) # 2
# empty의 대체방법 #
# 추천
if q: # q = [1] 일때
	print('Not Empty')
if not q: # st = [] 일때
	print('Empty')
# 비추천
if len(q) == 0:
	print('Empty')
if len(q) > 0:
	print('Not Empty')

두 언어의 메소드 차이

*파이썬의 경우 front는 0, back은 -1 인덱스를 통해, size는 len 함수를 통해 같은 효과를 얻을 수 있다. deque은 양쪽에서 데이터를 관리할 수 있어서 appendleft가 push와 같은 역할을 한다.

**파이썬은 기본적으로 조건문에 바로 넣어 bool을 판별할 수 있어 empty가 존재하지 않는다. 추천 방법이 파이썬과 더 맞는 방법이기에 이를 사용하기를 권장한다.

***C++의 pop은 아무것도 반환하지 않지만 파이썬의 pop은 맨 앞의 원소(삭제할 원소)의 값을 반환한다.(top+pop으로 이해)

****deque 클래스는 위의 클래스 말고도 더 많은 클래스가 존재하니 필요에 따라 따로 찾아보길 권장한다.

메소드별 유의 사항

pop, front, back등의 메소드들은 스택에 원소가 없을 경우 에러가 나기 때문에 empty를 통해 먼저 확인하는 작업이 필요할 수 있다.

*파이썬의 q[-1]와 q[0]도 스택에 원소가 없으면 에러가 난다.

큐 문제 - 백준

큐 - www.acmicpc.net/problem/10845 풀이 - coder38611.tistory.com/131

요세푸스 문제 - www.acmicpc.net/problem/1158 풀이 - coder38611.tistory.com/130