C++:: 큐(Queue)

참고 내용

https://blog.encrypted.gg/934

정의와 성질

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

큐(Queue) :  한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조

1. 원소 추가 / 제거 / 맨 앞,뒤 원소 확인 O(1)

2. 맨 앞, 뒤가 아닌 나머지 원소들 확인/변경 원칙적으로 불가능

구현

head : 맨 앞 원소를 가리킴 

tail : 맨 뒤 + 1 위치를 가리킴

head - tail => queue의 크기

 

원소 넣음 > head 증가 > queue의 끝까지 증가시 에러 발생

원형 큐 사용

 

1) push함수

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

2) pop 함수

void pop(){
	head++;
}

3) front 함수

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

4) back 함수

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

STL예제

선언, push, pop, top, empty, size 사용법 확인

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

int main(void) {
  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
}

STL 

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

int main() {
    queue<int> Q;
    Q.push(10);
    Q.pop();
    Q.front();
    Q.back();
    Q.size();
    Q.empty();
}