[알고리즘 공부] 실전 알고리즘 6강-큐

바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/

---

정의

큐는 먼저들어간 원소가 먼저 나오는 FIFO(First in First Out) 자료구조 이다.

성질

1) 원소의 추가는 O(1)
2) 운소의 제거는 O(1)
3) 제일 앞/뒤의 원소 확인이 O(1)
4) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로는 불가능하다.

---

구현

큐는 배열 혹은 연결리스트로 구현을 할 수 있다.

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

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

void push(int x) 
{
	dat[tail++] = x;
}

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으로 구현

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

int main(void) {
  queue<int> Q;
  Q.push(10); // 10
  Q.push(20); // 10 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 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(); // 30 40
  cout << Q.front() << '\n'; // 30
}

1) queue이 empty상태 일때 front, back, pop을 호출하면 runtime error가 발생하게 된다.