큐(Queue)

• 큐의 기본 구조

-큐는 입력과 출력의 방향이 반대다.

-들어온 순서대로 처리가되는 선입선출(FIFO), 이와 반대되는 후입선출(LIFO) 방식의 대표적인 예는 스택(Stack)이 있다.

-큐(Queue)란 단어의 의미는 대기행령, 대기줄이다. 어떤 일을 순차적으로 처리하고자 할때 사용된다.

-큐에서 입력은 Put, 출력을 Get이라 편의상 부르겠다(입력을 Enqueue, 출력을 Dequeue라고 하기도 한다).

• 환형큐(원형큐)
  

-왚과 뒤가 원처럼 이어져 있는 큐 구조

-입력과 출력이 이어지며, Front와 Rear의 위치가 계속 변경되게 된다.

-선형큐의 문제점을 해결하기 위해, 나왔다고 한다.

-입력을 하면 Rear(뒷 부분)가 한칸 뒤로 밀린다.

-출력을 하면 Front(앞 부분)가 한칸 뒤로 밀린다.

-Rear는 빈공간을 가리킨다.

-최대 입력 가능한 데이터 수는, 최대 공간보다 한칸 적다(Rear가 빈공간을 하나 차지하니까!).

Max Data = Max Size - 1;

• 큐의 입력(Put, Enqueue)

//데이터 삽입

void QueueUsingArray::Put(int data)

{

        //Rear의 다음 위치 계산

        int nextIndex = (m_Rear + 1) % SIZE;

 

        //다음 위치가 Front위치라면 입력 중단->큐가 꽉찬 상태

        if (nextIndex == m_Front)

               return;

 

        //현재 Rear위치에 데이터 입력

        m_Queue[m_Rear] = data;

 

        //Rear를 다음 칸으로 이동

        m_Rear = nextIndex;

}

• 큐의 출력(Get, Dequeue)

//데이터 추출

int QueueUsingArray::Get(void)

{

        //Front와 Rear가 같은 위치라면 -> 데이터가 없는 상태

        if(m_Front == m_Rear)

               return -99999;

 

        //데이터 저장

        int result = m_Queue[m_Front];

 

        //Front를 한칸 뒤로 이동

        m_Front = (m_Front + 1) % SIZE;

 

        return result;

}

• 전체 코드

#pragma once

 

#define SIZE 10                                                                    //큐 최대 사이즈

#define NEXT_INDEX(index) (index + 1) % SIZE //다음 위치 계산 매크로

 

class QueueUsingArray

{

private:

        int m_Queue[SIZE];            //큐

        int m_Front;                  //제일 먼저 입력된 데이터의 위치

        int m_Rear;                           //가장 늦게 입력된 데이터의 다음위치 ->빈공간

 

public:

        QueueUsingArray();

        ~QueueUsingArray();

 

        void Init(void);       //초기화

        void Put(int);         //데이터 삽입

        int Get(void);         //데이터 추출

        void Print(void);      //출력

};

#include "stdafx.h"

#include "QueueUsingArray.h"

 

 

QueueUsingArray::QueueUsingArray()

{

        Init();

}

 

 

QueueUsingArray::~QueueUsingArray()

{

}

 

//초기화

void QueueUsingArray::Init(void)

{

        m_Front = 0;

        m_Rear = 0;

}

 

//데이터 삽입

void QueueUsingArray::Put(int data)

{

        //Rear의 다음 위치 계산

        int nextIndex = (m_Rear + 1) % SIZE;

 

        //다음 위치가 Front위치라면 입력 중단->큐가 꽉찬 상태

        if (nextIndex == m_Front)

               return;

 

        //현재 Rear위치에 데이터 입력

        m_Queue[m_Rear] = data;

 

        //Rear를 다음 칸으로 이동

        m_Rear = nextIndex;

}

 

//데이터 추출

int QueueUsingArray::Get(void)

{

        //Front와 Rear가 같은 위치라면 -> 데이터가 없는 상태

        if(m_Front == m_Rear)

               return -99999;

 

        //데이터 저장

        int result = m_Queue[m_Front];

 

        //Front를 한칸 뒤로 이동

        m_Front = (m_Front + 1) % SIZE;

 

        return result;

}

 

//출력

void QueueUsingArray::Print(void)

{

        int index = m_Front;

        printf("FRONT->");    

        while (index != m_Rear)

        {

               printf(" %d ->", m_Queue[index]);

 

               index = (index + 1) % SIZE;

        }

 

        printf("REAR\n");

}