3. Queue

데이터를 차례로 줄 세워 놓은 형태의 자료구조이다.

주요특징이라 함은 FIFO 구조라는 점.

• 접근,삭제는 맨앞이나, 맨뒤에서만 가능하다.

사진 출처- https://ko.wikipedia.org/wiki/%ED%81%90_%28%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0%29

Queue ADT의 기능을 표현하면 다음과 같다.

• enqueue(데이터): 큐의 맨 뒤에 데이터를 삽입한다.
• dequeue(): 큐의 맨 앞의 데이터를 제거한다.
• front(): 큐의 맨앞 데이터를 리턴한다.
• size(): 큐의 크기(담긴 데이터 수)를 리턴한다.
• empty(): 큐가 비었는지 안비었는지 판단한다.

dequeue 나 front 연산시에, 큐가 빌 경우에 대한 예외 처리를 해주어야한다.
단, 배열로 구현 시 enqueue 연산에도 큐가 꽉찰 경우에 대한 예외처리를 해주어야한다.

Built in 배열로 구현한 Queue

환형 구조를 생각하여 구현을 한다.
사용하는 필드는 다음과 같다.

• N: 배열의 최대 크기
• n: 저장된 원소의 개수
• arr: 데이터들을 저장할 동적 배열, 사실 상 실제 큐의 역할
• f: 맨 앞 데이터의 인덱스
• r: 맨 뒤 데이터의 인덱스

#include <iostream>

using namespace std;

class Queue {
private:
	int N;
	int n;
	int* arr;
	int f;
	int r;

public:
	Queue(int size):N(size) { //초기화
		n = 0;
		arr = new int[N];
		f = 0;
		r = 0;
	}

	~Queue() {
		delete[] arr;
	}

	int size() {
		return n;
	}

	bool empty() {
		return (size() == 0);
	}

	int front() {
		if (empty()) {
			return -1;
		}
		return arr[f];
	}

	void enqueue(int data){
		if (size() >= N) {
			cout << "Queue is full!" << endl;
			return;
		}

		arr[r] = data;
		r = (r + 1) % N; //마지막 인덱스에서 다음으로 이동시켰을 때, 0번째로 이동시키기 위함.
		n++;
	}

	void dequeue() {
		if (empty()) {
			cout << "Queue is empty!" << endl;
		}
		f = (f + 1) % N; //마지막 인덱스에서 다음으로 이동시켰을 때, 0번째로 이동시키기 위함.
		n--;

	}
};

int main() {
	Queue q(5);
	q.enqueue(1);
	q.enqueue(2);
	q.enqueue(3);
	q.enqueue(4);
	q.enqueue(5);
	q.enqueue(6);
	q.dequeue();
	cout <<q.front();
}

---

Linked List로 구현한 Queue

사용하는 필드는 다음과 같다.

• n: 저장된 원소의 개수
• front_node: 맨 앞 노드의 주소
• rear_node: 맨 뒤 노드의 주소

front_node를 head, rear_node를 tail이라고 생각하자.

#include <iostream>

using namespace std;

class Node {
private:
	int data;
	Node* next;
	friend class Queue;

public:
	explicit Node(int d):data(d) {
		next = nullptr;
	}
};

class Queue {
private:
	int n;
	Node* front_node;
	Node* rear_node;

public:
	Queue() {
		n = 0;
		front_node = nullptr;
		rear_node = nullptr;
	}

	~Queue() {
		while (!empty()) dequeue();
	}

	int size() {
		return n;
	}

	bool empty() {
		return(size() == 0);
	}

	int front() {
		if (empty()) {
			return -1;
		}
		return front_node->data;
	}

	void enqueue(int data) {
		Node* newnode = new Node(data);
		if (empty()) {
			front_node = rear_node = newnode;
		}
		else {
			rear_node->next = newnode;
			rear_node = newnode;
		}
		n++;
	}

	void dequeue() {
		if (empty()) {
			cout << "Queue is empty!!" << endl;
			return;
		}
		Node* old = front_node;
		if (size() == 1) {
			front_node = rear_node = nullptr;
		}
		else {
			front_node = front_node->next;
		}
		delete old;
		n--;
	}
};

int main() {
	Queue q;
	q.enqueue(1);
	q.enqueue(2);
	q.enqueue(3);
	cout << q.size() << endl;
	q.dequeue();
	q.dequeue();
	q.dequeue();
	q.dequeue();

}