Queue (큐)

출처 : http://www.infocodify.com/cpp/cpp_queue

- 선형적 자료 구조

- 선입선출(First- In, First - Out) 방식의 구조

  (마지막에 삽입된 데이터가 가장 처음으로 출력된다.)

---

Array Queue (배열 기반의 큐) 문제점

- 배열의 특성과 큐의 데이터 삽입 위치를 생각하면 문제점이 발생한다.

  배열은 연속된 메모리 구조, 큐의 선입선출의 특성과 데이터 추가 위치를 보면 앞에서 빠져나간 메모리 공간을

  재사용 하기 어려운 문제가 발생한다. 재사용 하기 위해선 같은 크기의 메모리를 할당하고 기존의 메모리를 복사 후 

  삭제하는 방식으로 이뤄져야 하는데 이는 매우 비효율적이며 큐를 직접 구현하기에 배열 기반은 적합하지 않다.

 

  하.지.만 !! 재사용을 효율적으로 하면서 배열 기반의 큐를 제작하기 위한 Circle Queue (원형 큐) 방식이 존재한다.

 

Circle Queue (원형 큐)

출처 : https://www.studytonight.com/code/python/ds/circular-queue-in-python.php

- 정적 배열로 이뤄져있어야 하며, 배열의 크기 중 하나의 공간은 더미(Dummy)가 되어야 한다.

  더미가 필요한 이유는 데이터의 추가, 삭제를 위해 반드시 필요하기 때문이다.  

  즉, 배열의 공간은 자신이 실제 넣고자 하는 크기의 데이터보다 1을 더해서 만들어줘야 한다.

- (Head == Tail) 공백 상태

void push(const T& data)
{
    if (full() == true)
    {
    	assert(false);
    }    
    
    // 배열의 전체 갯수로 나머지 연산
    int iHead = (m_iHead + 1) % (SIZE + 1);
    m_array[iHead] = data;
    m_iHead = iHead;
    ++m_iSize;
}

T front() const
{
    if (empty() == true)
    {
    	assert(false);
    }
    
    int iTail = (m_iTail + 1) % (SIZE + 1);
    
    return m_array[iTail];
}

T pop()
{
    if (empty() == true)
    {
    	assert(false);
    }
	
    int iTail = (m_iTail + 1) % (SIZE + 1);
    T data = m_array[iTail];
    m_iTail = iTail;
    --m_iSize;
    	
    return data;
}

---

코드 첨부 파일

main.cpp

0.00MB

Queue.h

0.00MB