본문 바로가기
자료구조

큐(Queue)

개발하는꼬마 2019. 7. 14. 09:50

큐는 뒤에서 데이터의 입력, 앞에서 데이터 삭제가 일어나는 자료구조이다. 데이터의 접근을 큐에 꼭대기와 바닥에서 일어나게 함으로 자료의 접근을 제한한다고 할 수 있다. 

 

큐는 오직 인큐와 디큐를 이용하여 자료의 갱신이 가능하다.

인큐란 자료를 넣어서 저장하는 행동이고 디큐는 자료를 빼서 삭제하는 행동이다.

데이터의 삽입이 항상 뒤에서 일어나기 때문에 데이터의 삭제는 가장 나중에 들어온 자료에서 일어난다.

이러한 과정을 선입선출(FIFO)라고 한다.

 

큐는 실제 프로그램을 구현하는데도 많이 사용한다. 예를 들어 인쇄순서, 식권 프로그램 등이 있다.

 

다음은 선형으로 구현한 큐이다.

선형으로 구현한 큐

다음은 선형으로 배열을 이용하여 큐를 구현할 때 필요한 함수들이다.

  • enque : 원소를 맨 뒤에 삽입하는 함수, 큐가 꽉 차있다면 원소를 넣지 않음, 원소를 하나씩 넣어줄 때마다 새로 갱신한 원소가 rear가 되도록 만듬
  • deque : 원소를 맨 앞에서 삭제하는 함수, 큐가 비어있다면 원소를 삭제하지 않음, 원소를 하나씩 삭제할 때마다 삭제한 원소 바로 다음 원소가 front가 되도록 만듬, 큐의 front을 이동해서 원소가 삭제된 것처럼 보이는 것이지 실질적 삭제가 아님
  • empty : 비어있는 큐인지 확인하는 함수
  • full : 꽉 차있는 큐인지 확인하는 함수
  • peek_front : front의 값을 반환하는 함수
  • peek_rear : rear의 값을 반환하는 함수
  • size : 큐의 들어있는 원소의 갯수를 반환하는 함수
  • show : 큐의 들어있는 원소들을 출력하는 함수
#include <iostream>
using namespace std;

//큐 클래스
class Queue {
private:
	int* mat; //큐의 원소가 담길 공간
	int num; //큐의 크기
	int front; //front를 나타내는 변수
	int rear; //rear를 나타내는 변수
	int cnt; //현재 원소의 갯수
public:
	//생성자
	Queue(int num) {
		this->num = num;
		mat = new int[num]; //mat를 num만큼 할당
		front = -1; //처음 rear의 위치는 -1
		rear = front; //처음 rear의 위치는 front의 위치와 같다
		cnt = 0; //현재 원소의 갯수는 0개
	}
	void Enque(int n); //인큐
	int Deque(int& n); //디큐, 참조를 이용하여 pop한 값을 저장
	bool empty(); //비어있는 큐인지 반환
	bool full(); //큐가 꽉 차있는지 반환
	int peek_front(int& n); //front 원소를 반환
	int peek_rear(int& n); //rear의 원소를 반환
	int size(); //현재 큐안에 원소들이 몇 개있는지 반환
	void show(); //큐의 모든 원소를 출력
};

//인큐
void Queue::Enque(int n) {
	if (full()) { //큐가 꽉 차있으면
		cout << "원소를 넣을 수 없습니다." << '\n';
	}
	else { //큐에 넣을 공간이 있으면
		if (front == -1) { //큐가 비어있는 상태에서 삽입할 때
			front = 0; //처음에는 0번지를 가리키도록 한다.
		}
		rear++; //rear값 증가
		mat[rear] = n; //넣으려는 값 삽입
		cnt++; //원소 갯수 증가
	}
}

//디큐, 참조를 이용하여 pop한 값을 저장
int Queue::Deque(int& n) {
	if (empty()) { //큐가 비어있다면
		cout << "아무런 원소도 없습니다." << '\n';
		return 0;
	}
	else { //디큐할 원소가 있다면
		n = mat[front]; //front값 저장
		front++; //다음 위치로 front를 이동
		cnt--; //원소 갯수 감소
		return 1;
	}
}

//비어있는 큐인지 반환
bool Queue::empty() {
	if (num == 0) { //비어있다면
		return true;
	}
	else { //안 비어있다면
		return false;
	}
}

//큐가 꽉 차있는지 반환
bool Queue::full() {
	if (num == rear + 1) { //rear값이 맨 마지막 위치에 놓여 다음에 이동할 곳이 없으면
		return true;
	}
	else { //rear가 이동할 곳이 있으면
		return false;
	}
}

//front 원소를 반환
int Queue::peek_front(int& n) {
	if (cnt == 0) { //원소가 아무것도 없으면 front는 -1이거나 큐의 크기와 같다.
		cout << "아무런 원소도 없습니다." << '\n';
		return 0;
	}
	else { //원소가 들어 있으면
		n = mat[front]; //front값 저장
		return 1;
	}
}

//rear의 원소를 반환
int Queue::peek_rear(int& n) {
	if (cnt == 0) { //원소가 아무것도 없으면 rear는 -1이거나 큐의 크기와 같다.
		cout << "아무런 원소도 없습니다." << '\n';
		return 0;
	}
	else { //원소가 들어 있으면
		n = mat[rear]; //rear값 저장
		return 1;
	}
}

//현재 큐안에 원소들이 몇 개있는지 반환
int Queue::size() {
	return cnt;
}

//큐의 모든 원소를 출력
void Queue::show() {
	for (int i = front; i <= rear; i++) {
		cout << mat[i] << ' ';
	}
	cout << '\n';
}

int main() {
	int num;
	cout << "원하는 큐의 크기 : "; cin >> num;
	Queue que(num);
	while (1) {
		int what;
		int n;
		cout << "1. 삽입, 2. 삭제, 3. front값 보기, 4. rear값 보기, 5. 스택의 들어있는 원소의 갯수, 6.전체 원소 출력, 7.종료 : "; cin >> what;
		switch (what) {
		case 1:
			cout << "원하는 값 입력 : ";  cin >> n;
			que.Enque(n);
			break;
		case 2:
			if (que.Deque(n)) {
				cout << "디큐 한 값은 " << n << '\n';
			}
			break;
		case 3:
			if (que.peek_front(n)) {
				cout << "front 값은 " << n << '\n';
			}
			break;
		case 4:
			if (que.peek_rear(n)) {
				cout << "rear 값은 " << n << '\n';
			}
			break;
		case 5:
			cout << "현재 들어있는 원소의 갯수는 " << que.size() << "입니다.\n";
			break;
		case 6:
			que.show();
			break;
		case 7:
			return 0;
		}
		cout << "\n\n";
	}
}

하지만 선형 큐에는 문제가 있다. 원소가 다 차지 않았는데 rear의 값이 맨 마지막 원소를 가리키면 앞에 큐에 빈 공간이 생기더라도 원소의 삽입이 안된다는 것이다. 

선형 큐에 문제점

이러한 문제점으로 큐를 구현할 때는 원형 큐를 이용한다. 원형 큐를 구현하는 경우 rear가 마지막 원소를 가리키더라도 front보다 앞에 빈 공간이 있으면 원소의 삽입이 가능하다.

원형 큐에서 rear가 마지막 원소를 가리키는 경우

 

 

 

원형 큐의 원소를 삽입하는 경우1

 

 

 

원형 큐의 원소를 삽입하는 경우2(포화 상태)

front를 지정할 때 삭제할 위치는 front % 큐의 넣을 수 있는 총 원소의 갯수로 지정하고 rear를 지정할 때 삽입할 위치는rear % 큐의 넣을 수 있는 총 원소의 갯수로 지정한다. 

 

front가 0번지, rear가 마지막번지(n개를 선언했다면 n-1번지)가 아니더라도 큐가 꽉 찰 수 있다는 것을 명심하자

 

원형으로 큐를 구현할 때 사용할 함수들은 선형으로 구현할 때와 같다.

#include <iostream>
using namespace std;

//큐 클래스
class CircleQueue {
private:
	int* mat; //큐의 원소가 담길 공간
	int num; //큐의 크기
	int front; //front를 나타내는 변수
	int rear; //rear를 나타내는 변수
	int cnt; //현재 원소의 갯수
public:
	//생성자
	CircleQueue(int num) {
		this->num = num;
		mat = new int[num]; //mat를 num만큼 할당
		front = 0; //처음 rear의 위치는 -1
		rear = front; //처음 rear의 위치는 front의 위치와 같다
		cnt = 0; //현재 원소의 갯수는 0개
	}
	void Enque(int n); //인큐
	int Deque(int& n); //디큐, 참조를 이용하여 pop한 값을 저장
	bool empty(); //비어있는 큐인지 반환
	bool full(); //큐가 꽉 차있는지 반환
	int peek_front(int& n); //front 원소를 반환
	int peek_rear(int& n); //rear의 원소를 반환
	int size(); //현재 큐안에 원소들이 몇 개있는지 반환
	void show(); //큐의 모든 원소를 출력
};

//인큐
void CircleQueue::Enque(int n) {
	if (full()) { //큐가 다 찼다면
		cout << "큐가 다 찼습니다." << '\n';
	}
	else { //큐가 다 차지 않았다면
		rear = (rear + 1) % num; //rear의 값을 (rear + 1) % num으로 결정
		mat[rear] = n;
		if (cnt == 0) { //처음 넣어준 원소이면
			front = rear; //front의 값을 rear로 놓는다.
		}
		cnt++; //갯수 늘리기
	}
}

//디큐, 참조를 이용하여 pop한 값을 저장
int CircleQueue::Deque(int& n) {
	if (empty()) { //큐가 비었다면
		cout << "큐가 비었습니다." << '\n';
		return 0;
	}
	else { //큐가 비어있지 않으면
		front = (front + 1) % num; //front의 값을 (front + 1) % num으로 결정
		n = mat[front]; //n에 저장
		cnt--; //갯수 줄이기
		return 1;
	}
}

//비어있는 큐인지 반환
bool CircleQueue::empty() {
	if (cnt == 0) {
		return true;
	}
	else {
		return false;
	}
}

//큐가 꽉 차있는지 반환
bool CircleQueue::full() {
	if (cnt == num) {
		return true;
	}
	else {
		return false;
	}
}

//front 원소를 반환
int CircleQueue::peek_front(int& n) {
	if (cnt == 0) {
		cout << "큐가 비었습니다." << '\n';
		return 0;
	}
	else {
		n = mat[front];
		return 1;
	}
	
}

//rear의 원소를 반환
int CircleQueue::peek_rear(int& n) {
	if (cnt == 0) {
		cout << "큐가 비었습니다." << '\n';
		return 0;
	}
	else {
		n = mat[rear];
		return 1;
	}
}

//현재 큐안에 원소들이 몇 개있는지 반환
int CircleQueue::size() {
	return cnt;
}

//큐의 모든 원소를 출력
void CircleQueue::show() {
	int iter = front; //처음 출력할 원소를 front로 지정
	for (int i = 0; i < cnt; i++) { //원소의 갯수만큼 반복
		cout << mat[iter] << ' '; //iter번째 원소 출력
		iter++; //iter증가
		if (iter == num) { //iter가 원소의 총 갯수와 같으면
			iter = 0; //iter는 0으로 초기화
		}
	}
}

int main() {
	int num;
	cout << "원하는 큐의 크기 : "; cin >> num;
	CircleQueue que(num);
	while (1) {
		int what;
		int n;
		cout << "1. 삽입, 2. 삭제, 3. front값 보기, 4. rear값 보기, 5. 스택의 들어있는 원소의 갯수, 6.전체 원소 출력, 7.종료 : "; cin >> what;
		switch (what) {
		case 1:
			cout << "원하는 값 입력 : ";  cin >> n;
			que.Enque(n);
			break;
		case 2:
			if (que.Deque(n)) {
				cout << "디큐 한 값은 " << n << '\n';
			}
			break;
		case 3:
			if (que.peek_front(n)) {
				cout << "front 값은 " << n << '\n';
			}
			break;
		case 4:
			if (que.peek_rear(n)) {
				cout << "rear 값은 " << n << '\n';
			}
			break;
		case 5:
			cout << "현재 들어있는 원소의 갯수는 " << que.size() << "입니다.\n";
			break;
		case 6:
			que.show();
			break;
		case 7:
			return 0;
		}
		cout << "\n\n";
	}
}

 

다음은 연결리스트를 이용해 구현한 큐이다.

연결 리스트를 이용할 때는 자료의 갯수에 영향을 받지 않는 장점이 있다.

원소를 새로 삽입한 것을 rear 포인터로 가리키게 하고 원소를 삭제할 시 삭제하는 노드 바로 다음 노드를 front로 가리키게 한다.

 

연결 리스트를 이용한 큐의 구현

다음은 연결리스트를 이용하여 큐를 구현할 때 필요한 함수들이다.

  • enque : 원소를 맨 뒤에 삽입하는 함수, 원소를 하나씩 넣어줄 때마다 새로 갱신한 원소가 rear가 되도록 만듬
  • deque : 원소를 맨 앞에서 삭제하는 함수, 큐가 비어있다면 원소를 삭제하지 않음, 원소를 하나씩 삭제할 때마다 삭제한 원소 바로 다음 원소가 front가 되도록 만듬
  • empty : 비어있는 큐인지 확인하는 함수
  • peek_front : front의 값을 반환하는 함수
  • peek_rear : rear의 값을 반환하는 함수
  • size : 큐의 들어있는 원소의 갯수를 반환하는 함수
  • show : 큐의 들어있는 원소들을 출력하는 함수
#include <iostream>
using namespace std;

class Node {
public:
	int data; //노드가 가지고 있는 data
	Node* ptr; //다음 노드를 가리키는 포인터
	
	Node() {
		data = 0;
		ptr = NULL;
	}
};

class Queue {
public:
	Node* front; //큐에서 맨 앞에 요소를 가리키는 포인터
	Node* rear; //큐에서 맨 뒤에 요소를 가리키는 포인터
	int cnt; //노드의 갯수

	Queue() {
		front = NULL;
		rear = NULL;
		cnt = 0;
	}
	void enque(int data); //데이터를 삽입하는 함수
	bool deque(int& n); //데이터를 삭제하는 함수, 참조를 이용하여 삭제한 데이터를 반환
	bool empty(); //큐가 비었는지 판별하는 함수
	int showfront(); //front가 가지고 있는 data를 반환하는 함수
	int showrear(); //rear가 가지고 있는 data를 반환하는 함수
	int size(); //큐에 있는 원소의 갯수 보기
	void show(); //큐에 모든 원소를 출력해주는 함수
};

//데이터를 삽입하는 함수
void Queue::enque(int data) {
	Node* newNode = new Node[1];
	newNode->data = data;
	if (cnt == 0) { //큐에 처음 들어오는 원소이면 front와 rear의 위치가 같다.
		front = newNode;
		rear = newNode;
	}
	else {
		rear->ptr = newNode; //맨 마지막 노드에 삽입
		rear = newNode; //rear는 새로 삽입한 노드를 가리키게 한다.
	}
	cnt++; //노드 갯수 증가
}

//데이터를 삭제하는 함수
bool Queue::deque(int& n) {
	if (empty()) { //아무런 노드도 없으면
		cout << "삭제할 원소가 없습니다.\n";
		return false;
	}
	else {
		Node* temp = front;
		n = front->data; //삭제할 데이터를 n에 넣는다.
		front = front->ptr; //맨 처음 노드를 두 번째 노드로 설정
		delete temp; //노드 삭제(맨 처음 노드)
		cnt--; //노드 갯수 줄이기
		return true;
	}
}

//큐가 비었는지 판별하는 함수
bool Queue::empty() {
	if (cnt == 0) { //노드의 갯수가 0이면
		return true;
	}
	else { //노드가 한개라도 있으면
		return false;
	}
}

//front가 가지고 있는 data를 반환하는 함수
int Queue::showfront() {
	return front->data; //첫번째 노드의 데이터 반환
}

//rear가 가지고 있는 data를 반환하는 힘수
int Queue::showrear() {
	return rear->data; //마지막 노드의 데이터 반환
}

//큐에 있는 원소의 갯수 보기
int Queue::size() {
	return cnt; //갯수 반환
}

//큐에 모든 원소를 출력해주는 함수
void Queue::show() {
	Node* temp = front;
	cout << "프런트 : ";
	while(temp) { //마지막 노드를 만날때 까지 반복
		cout << temp->data << ' ';
		temp = temp->ptr;
	}
	cout << ": 리어\n";
}

int main() {
	Queue* q = new Queue;
	while (1) {
		int what;
		int n;
		cout << "1. 삽입, 2. 삭제, 3. front값 보기, 4. rear값 보기, 5. 스택의 들어있는 원소의 갯수, 6.모든 원소 출력하기, 7. 종료: "; cin >> what;
		switch (what) {
		case 1:
			cout << "원하는 값 입력 : ";  cin >> n;
			q->enque(n);
			break;
		case 2:
			if (q->deque(n)) {
				cout << "디큐 한 값은 " << n << '\n';
			}
			break;
		case 3:
			cout << "front 값은 " << q->showfront() << '\n';
			break;
		case 4:
			cout << "rear 값은 " << q->showrear() << '\n';
			break;
		case 5:
			cout << "현재 들어있는 원소의 갯수는 " << q->size() << "입니다.\n";
			break;
		case 6:
			q->show();
			break;
		case 7:
			return 0;
		}
		cout << "\n\n";
	}
}

 

저작자표시 비영리

'자료구조' 카테고리의 다른 글

트리(이진트리순회)  (0) 2019.08.02
스택(Stack)  (0) 2019.07.05
단순 연결 리스트(Single linked list)  (0) 2019.07.05

'자료구조' Related Articles

티스토리툴바