[Data Structure] 큐(Queue)

큐(Queue)란?

✅ 큐

- 한 쪽에서 삽입 작업이 이루어지고 다른 한 쪽에서는 삭제 작업이 이루어지는 선형 자료구조

- 먼저 들어온 데이터가 먼저 나가는 자료구조

- FIFO (First-In First-Out) 

 

✅ 큐의 구조

- 삽입 : rear (후단) → 삽입 연산 (enQueue)

- 삭제 : front (전단) → 삭제 연산 (deQueue)

🔥rear와 front를 백준 문제를 풀면서 헷갈렸다.

linear queue로 먼저 생각하고 풀었었는데 front와 rear를 헷갈리지 않도록 첨부해둔다.

---

큐를 적용한 문제풀이

✅백준 18258. 큐 2

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

소스코드 ("더보기"누르면 소스코드 보임)

❌비쥬얼 스튜디오로 돌렸을 때는 답이 맞는데 1. 시간초과 2. 공간 부족으로 처참하게 실패 중이다.

STL 안쓰고 직접 구현하고 싶은데 도대체 어떻게 해야 할까,,,,

#include <iostream>
#include <string>
using namespace std;
const int MAX_SIZE = 100000; 

class ArrayQueue {
private:
	int front; //삭제연산(첫 번째 요소의 앞)
	int rear; //삽입연산(마지막 요소)
	int data[MAX_SIZE]; //요소의 배열
public:
	ArrayQueue() {
		front = rear = -1;
	}
	bool isEmpty() {
		return rear == front;
	}
	//empty
	void empty() {
		if (isEmpty())
			cout << 1 << '\n';
		else
			cout << 0 << '\n';
	}
	//push : 정수 X를 큐에 넣는 연산
	void push(int x) {
		data[rear + 1] = x;
		rear++;
	}
	//pop : 큐에서 가장 앞에 있는 정수를 뺴고, 그 수를 출력
	void pop() {
		if (isEmpty())
			cout << -1 << '\n';
		else
		{
			cout << data[front + 1] << '\n';
			front++;
		}
	}

	//front : 가장 앞에 있는 정수를 출력, empty면 -1을 출력
	void getFront() {
		if (isEmpty())
			cout << -1 << '\n';
		else
			cout << data[front + 1] << '\n';
	}
	//back : 큐의 가장 뒤에 있는 정수를 출력, empty면 -1을 출력
	void getBack() {
		if (isEmpty())
			cout << -1 << '\n';
		else 
			cout << data[rear] << '\n';
	}
	//size : 큐에 들어있는 정수의 개수를 출력
	void size() {
		cout << rear - front << '\n';
	}
};

int main() {
	//명령의 수
	int n;
	cin >> n;

	ArrayQueue q; //객체 생성

	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		if (s == "push") {
			int x;
			cin >> x;
			q.push(x);
		}
		if (s == "pop") {
			q.pop();
		}
		if (s == "size") {
			q.size();
		}
		if (s == "empty") {
			q.empty();
		}
		if (s == "front") {
			q.getFront();
		}
		if (s == "back") {
			q.getBack();
		}

	}

	return 0;
}

⭕<vector>를 사용해서 어찌저찌 풀었다. 다른 사람의 코드를 거의 받아적었다고 할 수 있지만,,, 

cin.tie(0)이랑 ios::sync_with_stdio(false)를 쓰는 이유는 C버퍼를 쓰지 않고 (즉, 동기화하지 않고) C++만의 버퍼만을 써서 빠르게 하기 위함이다. 본 문제는 시간 문제를 신경써야 하기 때문

위에서 다뤘던 문제 1과 2를 해결했다. 시간초과는 동기화를 해제해서 해결했고 공간 문제는 vector를 써서 해결했다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; //명령어 수
	int n; //push 매개변수
	int rear, front = 0;
	string answer;
	vector<int> a;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> answer;
		if (answer == "push") {
			cin >> n;
			a.push_back(n);
		}
		else if (answer == "pop") {
			rear = a.size();
			if (rear == front)
				cout << -1 << "\n";
			else {
				cout << a[front] << "\n";
				front++;
			}
		}
		else if (answer == "size") {
			rear = a.size();
			cout << rear - front << "\n";
		}
		else if (answer == "empty") {
			rear = a.size();
			if (rear == front)
				cout << 1 << "\n";
			else
				cout << 0 << "\n";
		}
		else if (answer == "front") {
			rear = a.size();
			if (rear == front)
				cout << -1 << "\n";
			else
				cout << a[front] << "\n";
		}
		else if (answer == "back") {
			rear = a.size();
			if (rear == front)
				cout << -1 << "\n";
			else
				cout << a.back() << "\n";
		}
	}
}