[Data Structure] 큐

개요

• front에서 원소가 Pop되고, rear에서 원소가 Push되는 순서 리스트
• 선입선출(First In First Out, FIFO)
• 일반적인 선형 큐는 공간이 남는 문제가 있음 => modulo 연산으로 원형 큐 구현
  • (front + 1) % capacity
  • (rear + 1) % capacity
  • 선형 큐와 달리 front가 가리키는 곳은 비어있고, front의 한 칸 앞부터 값이 실제로 저장됨 => 원형 큐는 한 칸 버려야 함

큐에서 구현할 기능

• 생성자: 큐 capacity 초기화 및 큐 배열 할당
• 소멸자: 큐 배열 삭제
• IsEmpty: front == rear일 때 공백
• Front
• Rear
• Enqueue: 크기가 부족한 경우 2배로 늘려서 데이터 옮김
• Dequeue: front를 한 칸 앞으로 옮겨서 삭제한 것처럼 처리
• Print: front 다음 칸부터 시작해서 rear가 되면 멈춤

원형 큐 크기 확장

다음과 같이 꽉 찬 원형 큐가 있다고 했을 때, 배열을 두 배로 확장하면

와 같은 모양이 된다. 이걸 다시 정리해주면

와 같은 모양이 되어 성공적으로 원형 큐의 크기를 확장할 수 있다. 절차를 자세히 정리하면

• 크기가 두 배가 되는 새로운 배열 newQueue 생성
• 두 번째 부분 (queue[front + 1] ~ queue[capacity - 1] 사이 원소들)을 newQueue의 0에서부터 복사해 넣음
• 첫 번째 부분 (queue[0] ~ queue[rear] 사이 원소들)을 newQueue의 capacity - front - 1에서부터 복사해 넣음
  • capacity - front - 1 => (capacity - 1) - (front + 1) + 1

코드

#pragma once

#include <iostream>

template <typename T>
class Queue
{
public:
	Queue(int queueCapacity = 10)
	{
		capacity = queueCapacity; // 용적 초기화
		queue = new T[capacity]; // 큐 배열 생성
		front = rear = 0; // front, rear 인덱스 초기화
	}

	~Queue()
	{
		delete[] queue; // 큐 배열 해제
	}

	bool IsEmpty() const
	{
		if (front == rear)
			return true;
		else
			return false;
	}

	T& Front() const
	{
		if (IsEmpty()) throw "Queue is empty!";
		
		return queue[(front + 1) % capacity];
	}

	T& Rear() const
	{
		if (IsEmpty()) throw "Queue is empty!";

		return queue[rear];
	}

	void Enqueue(const T& item)
	{
		// 큐의 공간이 부족한 경우 2배 늘린 후 옮김
		// 기존 데이터들은 새로운 큐의 왼쪽부터 차례대로 붙임
		if ((rear + 1) % capacity == front) // rear가 front의 바로 뒤에 있으면 꽉 찼다고 판단
		{
			T* newQueue = new T[capacity * 2]; // 두 배 늘린 새로운 큐 생성
			
			// 기존 queue의 값을 newQueue로 복사
			int start = (front + 1) % capacity;
			if (start < 2) // 값이 중간에 끊기지 않고 연속적으로 있는 경우
			{
				memcpy(newQueue, queue + start, sizeof(T) * (rear - start + 1));
			}
			else // 중간에 끊어지는 경우
			{
				int rightSideSize = capacity - front - 1;
				memcpy(newQueue, queue + start, sizeof(T) * rightSideSize); // (capacity - 1) - (front - 1) + 1
				memcpy(newQueue + rightSideSize, queue, sizeof(T) * (rear + 1));
			}

			// newQueue에 맞게 새롭게 설정		
			front = 2 * capacity - 1;
			rear = capacity - 2;
			capacity *= 2;
			delete[] queue;
			queue = newQueue;
		}

		rear = (rear + 1) % capacity;
		queue[rear] = item;

		std::cout << front << " " << rear << std::endl;
	}

	void Dequeue()
	{
		if (IsEmpty()) throw "Queue is empty!";

		front = (front + 1) % capacity;
	}

	void PrintQueue()
	{
		if (IsEmpty()) throw "Queue is empty!";

		int currentIdx = (front + 1) % capacity;

		while (true) // 한 바퀴 돌아서 front가 되면 종료
		{
			//std::cout << "Idx: " << currentIdx << std::endl;
			std::cout << queue[currentIdx] << " ";
			if (currentIdx == rear) break;
			currentIdx = (currentIdx + 1) % capacity;
		}
		std::cout << std::endl;
	}

private:
	T* queue;
	int capacity, front, rear;
};