큐의 개요

• rear: 뒤
• front: 앞
• 선형 배열에서 만든 큐는 삭제가 될 때마다 쓸모없는 공간이 계속 생김 -> 새 원소를 추가할 수 없는 경우 발생 -> 원형 큐로 구현하는 게 좋음

큐의 성질

1. 원소의 추가: O(1)
2. 원소의 제거: O(1)
3. 제일 상단의 원소 확인이 O(1)
4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능❗️
   (cf. 배열로 스택을 구현할 경우 가능하기도 함)

스택의 구현

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

STL queue

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
}

❗️queue가 비어 있는데 front()와 back()을 부르면 runtime error