[자료구조] 큐 QUEUE
1. 의미
- 큐(Queue)의 사전적 의미는 무엇을 기다리기 위해 서는 줄, 대기열입니다.
예를들어 우리가 게임을 할 때 '큐를 잡는다, 큐를 기다린다'라는 말의 큐는 바로 줄, 대기열을 의미합니다. 우리가 줄을 서면 가장 앞에있는 사람(가장 먼저 들어온 데이터)이 가장 먼저 들어가죠? 이러한 구조를 선입선출(First In First Out; FIFO)구조라고 합니다.
2. 연산
- 일반적으로 큐 자료구조의 앞을 Front, 뒤를 Rear라고 칭합니다. 그림으로 표현하면 다음과 같습니다.
큐가 비어있는 상태를 front == rear(같음) 상태로 표현합니다.
(초기화시 front = rear = 0으로 초기화)
삽입(Enqueue)연산은 rear의 위치에 데이터를 삽입하고 rear의 위치를 1 증가 시켜줍니다.
이러면 front와 rear가 같은 값이 되므로 다시 큐가 비어있는 상태가 됩니다.
큐의 끝(rear)가 배열의 마지막을 가리키고있는 상태가 큐가 가득 찬 상태입니다.
이렇게 큐를 배열로 구현했을 경우 0번 인덱스는 사용하지 않는 메모리가 되었습니다.
물론 고정적인 배열의 크기도 문제가 됩니다.
이를 해결하기 위해 원형 큐, 링크드 리스트로 구현한 큐... 등 여러가지 큐가 존재합니다.
3. 사용
프로세스 관리
운영체제(OS)의 작업 큐
프린터 출력의 문서 대기...등
입력된 시간 순서대로 처리해야하는 모든 상황에 거의 큐가 사용됩니다.
4. 구현
배열로 구현한 큐)
#include <iostream>
using namespace std;
class queue
{
private:
int *queue_arr; // 큐 배열(동적 할당을 위해 포인터로 선언)
int queue_size; // 큐의 크기
int front, rear;
public:
queue() // 디폴트 생성자 함수
{
front = 0; rear = 0; // front와 rear 위치를 0으로 초기화
queue_size = 5; // 매개변수 없이 객체 생성 시 스택 크기 5로 지정
queue_arr = new int[queue_size]; // 배열 동적 할당
for (int i = 0; i < queue_size; i++)
{
queue_arr[i] = 0; // 큐의 배열은 모두 0으로 초기화
}
}
queue(int size) // 생성자 함수
{
front = 0; rear = 0; // front와 rear 위치를 0으로 초기화
queue_size = size; // 입력한 매개변수 크기만큼 스택 크기 지정
queue_arr = new int[queue_size]; // 배열 동적 할당
for (int i = 0; i < queue_size; i++)
{
queue_arr[i] = 0; // 큐의 배열은 모두 0으로 초기화
}
}
~queue() // 소멸자 함수
{
delete[] queue_arr;
}
void enqueue(int data) // 삽입 함수
{
if (queue_is_full()) // 큐가 가득 차 있는 경우
{
cout << "큐가 가득 차 있습니다." << "\n";
return; // 함수 종료
}
else // 아닐 경우
{
queue_arr[rear++] = data;
// 큐 배열 rear 위치의 데이터를 삽입 후 rear의 크기 1 증가
// 위 코드가 이해가지 않는다면 후위 증감 연산자에 대해 공부할 것
cout << "데이터 삽입 성공!" << "\n";
}
}
void dequeue() // 삭제 함수
{
if (queue_is_empty()) // 큐가 비어있는 경우
{
cout << "큐가 비어있습니다." << "\n";
return; // 함수 종료
}
else // 아닐 경우
{
cout << "반환 된 데이터 : " << queue_arr[front] << "\n"; // 데이터 반환
queue_arr[front++] = 0;
// 큐 배열 front 위치의 데이터를 삭제 후 front 크기 1 증가
}
}
bool queue_is_empty() // 큐가 비어있는지 확인 함수
{
if (front == rear) // front와 rear가 같은 위치라면
return true;
else // 아닐 경우 비어있지 않음
return false;
}
bool queue_is_full() // 큐가 가득 차 있는지 확인 함수
{
if (rear == queue_size - 1) // rear가 큐 배열의 마지막 위치라면
return true;
else // 아닐 경우 가득 차 있지 않음
return false;
}
void print_queue() // 큐 배열 전체 출력 함수
{
cout << "Queue : [ ";
for (int i = 0; i < queue_size; i++)
{
if (i != queue_size - 1)
{
cout << queue_arr[i] << " , ";
}
else
{
cout << queue_arr[i];
}
}
cout << " ] " << "\n";
cout << "front 위치 : " << front << "\n";
cout << "rear 위치 : " << rear << "\n";
}
};
int main()
{
queue *que;
int input_size;
cout << "큐 배열 크기 입력 : ";
cin >> input_size;
if (input_size <= 0)
{
cout << "잘못 된 입력입니다. 디폴트 사이즈(5)로 생성합니다." << "\n";
que = new queue();
}
else
{
que = new queue(input_size);
}
while (1)
{
int input;
cout << "\n" << "[명령어 입력]" << "\n";
cout << "1. ENQUEUE " << "\n" << "2. DEQUEUE " << "\n" << "3. PRINT " << "\n" << "4. EXIT : ";
cin >> input;
switch (input)
{
case 1:
int input_data;
cout << "삽입 할 데이터를 입력하세요 : ";
cin >> input_data;
que->enqueue(input_data);
break;
case 2:
que->dequeue();
break;
case 3:
que->print_queue();
break;
case 4:
cout << "프로그램을 종료합니다." << "\n";
return 0;
default:
cout << "잘못 된 입력입니다. 다시 입력해 주세요" << "\n";
}
}
}
질문 사항은 댓글로 남겨주세요!
'자료구조, 알고리즘' 카테고리의 다른 글
| 정렬 알고리즘 종류 (0) | 2018.09.12 |
|---|---|
| 검색 알고리즘 종류 (2) | 2018.09.11 |
| 자료구조 그래프(Graph) (1) | 2018.09.06 |
| 자료구조 힙(Heap) (0) | 2018.09.05 |
| 자료구조 이진 탐색 트리(Binary Search Tree) (0) | 2018.09.01 |
| 자료구조 트리(Tree) (0) | 2018.08.30 |
| [자료구조] 스택 STACK (0) | 2018.08.19 |
| [BOJ] 1912 연속합 - 동적계획법 풀이 (0) | 2018.08.17 |
