업데이트
*2023.03.16 복습 겸 c++ 업데이트
큐의 정의
큐는 터널을 지난다고 생각하면 된다. 먼저 들어간 차가 출구로 먼저 나오듯이 큐도 먼저 들어간 원소가 먼저 나오게 된다. (스택은 이미 조금 알고 있어서 아직 정리하지 않았지만 스택과 반대이다)
먼저 들어가고 먼저 나온다고 해서 큐를 FIFO(First In Frist Out)이라고 부르기도한다.
(위에서 얘기한 스택은 FILO(First In Last Out)이라고 부르기도한다.)
큐의 성질
1. 원소의 추가나 삭제가 O(1)이다
우선 기본 용어를 알고 가면 좋을 것 같다.
큐에서는 원소가 추가되는 곳을 rear(뒤쪽)이라고 하고 제거되는 쪽을 front(앞쪽)이라고 한다.
가장 앞쪽에 있는 원소가 제거되거나 가장 뒤쪽에서 원소가 추가되므로 시간복잡도가 O(1)이다.
2. 제일 앞/뒤쪽 원소의 확인이 O(1)이다
가장 앞 혹은 가장 뒤만 확인하기 때문에 O(1)이다. 1번 성질과 동일한 이유이므로 생략.
3. 제일 앞/뒤쪽이 아닌 나머지 원소들의 확인 및 변경이 원칙적으로 불가능하다.
원래는 큐에는 인덱스로 원소에 접근하는 기능이 존재하지 않는다.
그러나 배열을 가지고 직접 만들게 된다면 해당 기능을 구현할 수는 있다.
구현 설명
q = []
head = 0
tail = 0
def push(x) :
q[tail++] = x
def pop() :
head++
def front() :
return q[head]
def back() :
return q[tail - 1]파이썬에서 큐를 직접 구현해야된다면 이렇게 구현하면 될 것 같다.
q라는 배열에 가장 앞쪽 인덱스를 표현해주는 head 변수와 가장 뒤쪽 인덱스를 표현해주는 tail 변수 이 때 tail은 코드 작성자의 임의대로 현재 마지막 원소가 있는 위치를 나타내주게 만들수도 있고 원소가 들어갈 위치를 나타내게 만들수도 있다. 필자는 후자의 경우로 만들었다.
push함수는 tail의 인덱스에 원소를 넣고 +1을 해준다.
pop함수는 실제로 배열에서 원소를 빼는 것이 아닌 head의 수만 올려서 빠진 것처럼 만든다.
front 와 back 함수는는 head 와 tail - 1의 인덱스를 가지는 원소를 반환한다.
이걸로 기본적인 큐의 기능은 완성이다.
파이썬 라이브러리(queue)
파이썬은 기본적으로 queue 라이브러리를 사용할 수 있다.
import queue
queue = queue.Queue()
queue.put(0)
queue.put(1)
queue.get()
queue.qsize()간단한 설명을 넣자면,
import queue로 라이브러리를 불러오고
queue.Queue()로 큐 자료구조를 가지고 있는 변수를 만들어주며
put 함수로 원소를 집어넣고
get 함수로 원소를 제거하고
qsize 함수로 큐의 크기 즉, 원소의 개수를 알 수 있다.
FIFO 구조이므로 이 코드에서 get을 사용했을 때는 0이 제거될 것이다.
이것으로 기본적인 큐의 정의와 성질 그리고 구현하는 법을 알아보았다.
테스트해보는 연습문제로는
백준 10845번: 큐 https://www.acmicpc.net/problem/10845
백준 2164번: 카드2 https://www.acmicpc.net/problem/2164
백준 1966번: 프린터 큐 https://www.acmicpc.net/problem/1966
를 찾았다.
12/19 내용 추가
일반적으로 파이썬 사용자들이 큐를 사용할 때는 queue가 아닌 deque를 사용한다고해서 찾아보았습니다.
파이썬 라이브러리(deque)
우선 deque가 무엇이냐면 더블 큐 라고 보시면 됩니다 앞으로 삽입,삭제 가 가능하고 뒤로도 삽입,삭제가 가능합니다. 따라서 스택의 역할도 할 수 있고 큐의 역할도 할 수 있게 됩니다.
from collections import deque
a = deque()이게 deque 사용의 기본입니다.
deque의 장점은 위에서 말했지만 양쪽 모두 사용 가능합니다. 따라서
pop()은 오른쪽 값 , popleft()는 왼쪽 값을 반환하며 삭제할 수 있습니다.
append()로 오른쪽에 추가 , appendleft()로 왼쪽에 추가할 수 있습니다.
리스트처럼 a[2] = 3 같이 인덱스로 중간내용을 수정할 수도 있으며
insert(idx, 값) 으로 원하는 위치에 값을 추가하고
remove(값) 으로 원하는 값을 지울 수 있습니다.(같은 값이 있을 경우 왼쪽부터)
큐는 생각보다 자주 쓰이는 듯 하고 파이썬에서는 다양하게 이용할 수 있는 deque가 있으니 활용법을 알아두면 유용하게 쓰일 것 같습니다.
2023.03.16
여기서부터는 옛날 마지막 글 이후로 c++ 공부를 위해 알고리즘을 c++로 하고 있기에 c++기준으로 업데이트합니다.
전체적인 큐의 정의 및 내용은 위에 설명한 바와 같고 c++에서는 만들기에 따라 다르겠지만 STL을 기준으로
push
pop 을 사용하고
front 와 tail을 사용해서 각각 맨앞과 맨뒤의 원소를 확인할 수 있습니다.
예시로
#include <bits/stdc++.h>
using namespace std;
queue<int> Q; //일반적인 정수 큐
queue<pair<int, int> Q2; //pair를 이용한 큐
Q.push(1);
Q2.push({1,3});
Q.pop();
Q2.pop();과 같은 방식으로 사용됩니다.
c++에서도 deque가 있습니다.
사용할 수 있는 함수로는
push_front
push_back
pop_front
pop_back
이 있습니다. 아무래도 앞과 뒤 모두에 간섭할 수 있는 deque의 특징상 존재해야하는 함수입니다.
특이하게도 deque는 c++에서 인덱스로도 접근이 가능하고 insert와 erase함수도 사용 가능한데 vector와 중첩되는 부분이 되게 많습니다. vector와 다르게 맨 앞과 맨 뒤의 추가 제거가 O(1)이니 더 상위호환이라고 생각할 수도 있지만 찾아본 결과 그렇지 않았습니다.
vector는 메모리 구조상 연속되어 있지만 deque는 연속되어서 존재하지 않기 때문에 맨 앞과 맨뒤의 추가 제거가 필요하지 않다면 vector가 더 효율적입니다.
추가적으로 공부하다보니 우선순위 큐 라는 것도 존재하는 것 같은데 이것에 대해서는 나중에 더 자세히 알아보도록 하겠습니다.
중구난방 초보의 글 읽어주셔서 감사합니다.
