[바킹독의 실전 알고리즘] 0x06강 - 큐

큐

• 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조
• ex. 공항에서 입국소속 하는 줄
• FIFO(First in First Out)
  • 먼저 들어간 원소가 먼저 나옴

성질

1. 원소의 추가 / 제거 O(1)
   • 스택 - top: 원소가 추가되고 제거되는 곳/ 원소가 위 아래로 배치된 것
   • 큐 - rear: 추가되는 곳(뒤쪽), front: 제거되는 곳(앞쪽)
2. 제일 앞 / 뒤의 원소 확인 O(1)
3. 제일 앞 / 뒤가 아닌 나머지 원소들의 확인 / 변경 원칙적으로 불가능

구현

• 배열(더 쉬움)
• 연결 리스트

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

head와 tail은 0번지에서 시작해 계속 증가
dat 배열에서 dat[head] ~ dat[tail-1]번지 = 큐의 원소들이 들어있는 자리
큐의 크기 = tail - head

push -> tail 증가, pop -> head 증가
=> dat 배열에서 큐의 원소들이 들어있는 장소 점점 오른쪽으로 밀림

원형 큐(Circular Queue)
삭제 발생 -> 앞쪽에 쓸모 없는 공간 존재, 새 원소 추가할 수 X 상황
=> 해결: 큐의 원소가 들어갈 배열을 원형으로 만듦
-> head나 tail이 7인 상태에서 1이 더해질 때 0번지로 다시 오도록 구현
= head, tail이 MX가 될 경우 0으로 만듦

#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;
}

void pop() {
	head++;
}

int front() {
	return dat[head];
}

int back() {
	return dat[tail-1];
}

void test() {

}

int main(void) {
	test();
}

 

---

STL queue

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	queue<ing> Q;
    Q.push(10); // 10
    Q.push(20); // 20
    Q.push(30); // 30
    cout << Q.size() << '\n'; // 3
    if(Q.empty()) cout << "Q is empty\n";
    else cout << "Q is not empty\n"; // Q is not empty
    Q.pop(); // 20 30
    cout << Q.front() << '\n'; // 20
    cout << Q.back() << '\n'; // 30
    Q.push(40); // 20 30 40
    Q.pop(40); 30 40
    cout << Q.front() << '\n'; // 30
}

---