자료 구조 Queue와 구현하기 (C++)

설명 :

Deletion을 Dequeue. Insertion을 Enqueue라고도 부른다.

queue의 구조

큐는 "줄을 서다"라는 의미를 가지고 있다.

선입선출, 먼저 들어온 것이 먼저 나간다라는 구조를 생각하면 된다.. (First In, First Out)

흡사 은행 창구나 식당을 생각하면 된다. 먼저 무언가 요청하면 먼저 실행된다.

 

실생활 어느 곳에 쓰이는 지 예시를 들어보면,

대표적인 것으로 게임을 돌릴 때 "큐를 잡는다"라고 한다.

게임에서도 먼저 돌리면 먼저 잡게 해주는 큐 구조이다.

 

원형 큐

선형 큐(원래 큐 형태)의 단점을 보완하기 나온 형태이다.

선형 큐를 구현하면 문제점이 나오게 될 것이다.

선형 큐

그것은 바로 빈 공간이다. 데이터를 들여보내는 Enequeue와 내보내는 Dequeue를 하면,

어떤 데이터 안에 빈 공간이 있을 수 있다. 그러나 이것을 차 있다고 생각할 것이다.

그러면 이를 해결하기 위하여 두 가지 방법이 존재한다.

 

1. 예시의 3의 데이터를 앞으로 두칸 땡기면 된다

=> 데이터가 3뿐만 아니라 여러 개 있다면 구현하기 힘들며, 비효율적이다.

 

2. 원형 큐를 사용하면 된다.

=> 사용하기 편함. 효율적임

코드 : 

queue.cpp :

#include <iostream>
#define maxsize 5;

using namespace std;

class Queue {

private:
int front;
int rear;
int size;
int *values;
int number;
public:

Queue() //생성자 함수
{
size = maxsize;

values = new int[size]; //최대크기만큼 동적 배열 생성

front = 0; //앞을 나타내는 변수

rear = 0; //뒤를 나타내는 변수

number = 0; //현재 들어가 있는 데이터의 수를 나타내는 변수
}

bool isEmpty() //자료 구조가 비어 있는지 확인하는 함수
{

if (number == 0) //현재 데이터가 0개 들어가 있다면
{
return true;
}

else //아니라면
{
return false;
}
}

bool isFull() //자료 구조가 가득 차있는지 확인하는 함수
{
if (number == size) //현재 데이터가 최대크기만큼 들어가 있다면
{
return true;
}

else
{
return false;
}
}

void push(int value) //자료 구조에다가 데이터를 넣는 함수
{
if (isFull() == true) //자료 구조에 데이터가 가득 차 있다면
{
cout << "Queue is Full" << endl; //출력
}

else
{
values[rear] = value; //배열의 rear번쨰 인덱스에 value 값을 저장

rear = (rear + 1) % size; //size 개수만큼 원을 나눠서 차례대로 돌아가는 원형 큐 아이디어

number = number + 1; //데이터를 추가해줬으니 현재 데이터 개수를 나타내는 변수에 1 추가하기
}
}

void pop() //자료 구조에다가 데이터를 빼는 함수
{
if (isEmpty() == true) //자료 구조에 데이터가 비어있다면
{
cout << "Queue is Empty" << endl; //출력
}

else
{
front = (front + 1) % size; //size 개수만큼 원을 나눠서 차례대로 돌아가는 원형 큐 아이디어

number = number -1 ; //데이터를 뺴주었으니 현제 데이터 개수를 나타내는 변수에 1 빼기
}
}

void print()
{
if (isEmpty() == true) //자료 구조에 데이터가 비어있다면
{
cout << "There is nothing" << endl; //출력
}

else
{
int j = front; //가장 처음 부분을 j에 저장

for (int i = 0; i < number; i++)
{
cout << values[j] << " "; //배열의 값 출력

j = (j + 1) % size; //원형 구조로 돈다
}

cout << endl;
}
}
};

 

main.cpp :

#include<iostream>
#include "queue.cpp"


using namespace std;

int main()
{
    Queue q;

    q.push(1);

    q.push(2);

    q.push(3);

    q.push(11);

    q.push(20);

    q.push(30);     //가득 차서 집어 넣을 수 없음

    q.print();

    q.pop();

    q.pop();

    q.pop();

    q.print();

    return 0;
}

 

출력 결과 :