큐
- 먼저 들어간 원소가 먼저 나옴 (FIFO)
시간복잡도
-
원소 추가 : O(1)
-
원소 제거 : O(1)
-
제일 앞/뒤의 원소 확인 : O(1)
-
제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
큐 구현
-
스택과 마찬가지로 배열 또는 링크드리스트로 구현 가능
배열로 큐 구현하기
-
큐를 구현할 때는 원소를 담을 큰 배열 1개와 앞쪽, 뒤쪽을 가리킬 변수 2개인 head, tail이 필요하다.
-
head : 가장 앞에 있는 원소의 인덱스, tail : 가장 뒤에 있는 원소의 인덱스+1
-
push할떄 tail이 1증가하고, pop할땐 head가 1증가한다.
- 55가 삽입될때 : tail이 1증가, head는 그대로
- 17이 삽입될때 : tail이 1증가, head는 그대로
- 55가 삭제될때 : head가 1증가, tail은 그대로, 기존 head에 있던 데이터는 메모리에서 삭제시키지 않고 그대로 둠
- push할떄 tail이 1증가하고, pop할땐 head가 1증가하므로,
배열에서 큐의 원소들이 들어있는 장소는 점점 오른쪽으로 밀린다.
-
큐의 크기(사이즈) : tail - head 로, 쉽게 구할 수 있음
스택의 한계 - 불필요한 공간 낭비
-
배열에서 큐의 원소들이 들어있는 장소는 점점 오른쪽으로 밀린다.
(큐에서 삭제한 데이터는 실제로는 메모리에서 삭제되진 않고 남아있음)
-
계속 밀리다보면 결국 배열의 앞쪽에 사용하지 않고 있는 공간이 많음에도 불구하고 더 이상 삽입을 할 수 없다. (쓸모없는 공간 낭비)
=> 원형 큐가 해결해줌
원형 큐(Circular queue)
- 큐의 원소가 들어갈 배열을 원형으로 만듦
- head, tail이 배열 끝 인덱스일때 원소가 추가되면 다시 0번 인덱스부터 원소가 채워지도록 구현
- 관념적으로는 배열이 원형인 것이고, 실제 구현을 할땐 head나 tail이 7번지인 상태에서 0번지로 다시 오도록 구현
선형 배열 큐 vs 원형 큐
-
그냥 선형 배열로 구현한 큐는 앞쪽에 공간이 많음에도 불구하고 새 원소를 추가할 수 없는 상황이 발생.
-
원형 큐는 head와 tail이 다시 앞 쪽으로 돌아오기 때문에 원소의 개수가 배열의 크기보다 커지지 않는 한 문제가 없다.
=> STL 말고 직접 구현해서 쓸거면 원형 큐로 구현하는게 좋다.
But, 코딩테스트에서는 짜피 push의 최대 회수가 정해져있다.
그러면 배열의 크기를 push의 최대 회수보다 크게 둬서 굳이 원형큐를 만들지 않아도 된다.
선형 배열에서의 큐 구현
메소드 종류
- push, pop : 맨 뒤 삽입, 맨 앞 삭제
- front, back : 제일 앞/뒤 원소값 리턴
- tail 이 가리키는 인덱스는 큐의 맨 마지막 원소가 있는 인덱스의 다음 인덱스라는 점을 유의하자.
#include <bits/stdc++.h>
using namespace std;
const int MX = 1000005;
int dat[MX]; // 배열로 구현한 큐. 큐에 저장될 데이터를 배열로 저장
int head = 0, tail = 0;
void push(int x){
dat[tail] = x;
tail++;
}
void pop(){
head++;
}
int front(){
return dat[head];
}
int back(){
return dat[tail-1];
}
void test(){
push(10); push(20); push(30);
cout << front() << '\n'; // 10
cout << back() << '\n'; // 30
pop(); pop();
push(15); push(25);
cout << front() << '\n'; // 30
cout << back() << '\n'; // 25
}
int main(void) {
test();
}STL queue
- 종류 : push(), pop(), front(), back(), empty(), size()
queue<int> Q //Q라는 이름의 int 요소들로 구성된 큐 선언
Q.push(값) //큐 Q에 값을 넣는다. 리턴 값이 없다.
Q.pop() //큐 Q의 front를 삭제한다. 리턴 값이 없다.
Q.front() //큐 Q의 front를 리턴한다. front는 삭제되지 않는다. (peek기능)
Q.back() //큐 Q의 back를 리턴한다. back는 삭제되지 않는다. (peek기능)
Q.size() //큐 Q의 크기(구성 요소 갯수)를 리턴한다.
Q.empty() //큐 Q가 비어있으면(요소가 없으면) 를 1(True)리턴하고 비어있지 않으면 0(False)를 리턴한다.-
큐가 비어있는데 front, back, 또는 pop 을 호출하면 runtime error 가 발생
-
코딩테스트 단골문제로 BFS, flood fill이 나오는데 둘다 큐로 구현해서 STL queue 를 쓸일이 자주있다.
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
queue<int> q;
q.push(10);
q.push(20);
q.push(30); // 10 20 30
cout << q.size() << '\n'; // 3
if(q.empty())
cout << "q is empty\n";
else
cout << "q is not empty\n"
q.pop();
cout << q.front() << '\n'; //
cout << q.back() << '\n';
q.push(40);
q.pop();
cout << q.front() << '\n';
}