(C++) 자료구조 - 큐(Queue) - 배열(Array), 링크드리스트(Linked List)

안녕하세요.

오늘은 자료구조 큐 입니다.

이것도 스택과 마찬가지로 배열 방식 과 링크드리스트 방식 두가지를 구현해 보도록 하겠습니다.

 

1. 큐(Queue) 란?

 

FIFO (First In First Out)

제일 먼저 들어간 값이 제일 먼저 나오는 자료구조입니다.

 

배열과 링크드리스트의 차이는 스택과 동일하게 

처음 크기를 할당 하는지, 사용할때마다 크기를 줄이고 키우고 하는지 조절하는 것이 가장 큰 차이구요!

 

 

2. 배열을 이용한 큐 구현

 

 배열로 큐를 구현하려고 하면 몇몇 문제점이 있습니다.

index 를 따라서 앞에 있는 값을 빼다보면 언젠가는 index == maxSize 가 오기 때문인데요.

그렇다고 배열에서 값을 뺄때마다 뒤에 있는 값들을 배열 한칸씩 땡기는 것은 매우 비효율적인 과정이구요!

그래서 index 가 maxSize에 도달하면 0으로 초기화 하여

다시 처음부터 돌게 만드는 방법을 사용하는데 이를 환형 큐 (원형 큐) 라고 합니다.!

여기서 또 한가지 문제점이 발생하는데

만약 모든 배열을 사용한다고 하면

값이 비어있는지, 값이 꽉차있는지 구분이 되지 않습니다.

front == rear 가 값이 꽉차있는건지 비어있는 건지 말이죠

그래서 rear의 값을 비워둡니다.

만약 front == rear 라면 큐가 비어있다! 라는 것을 표시하기 위해서요!

그맇고 이렇게 되면 내가 선언한 값에서 배열을 하나 적게 사용하거나

추가로 + 1 을 해주어서 비어있을 값을 하나 만들어줘야 하죠.

아래 방식은 + 1 을 하여 내가 선언한 값이 내가 사용할 크기로 해서 구현하였습니다! 

 

 

class QueueArray
{
private:
	int front;				//Dequeue 했을때 나올 Index
	int rear;				//Enqueue 했을때 들어갈 Index
	int maxSize;				//배열 크기
	int* arrays;				//동적 할당할 배열
public:
	QueueArray(int size = 10);		//생성자(디폴트는 10)
	~QueueArray();				//소멸자
	bool Enqueue(int value);		//값을 넣는다.
	bool Dequeue(int& value);		//값을 뺀다.
	void Clear();				//모든 값을 비운다.
	void PrintAll();			//모든 값을 출력한다.
};

배열 큐의 헤더입니다.

 

Dequeue 했을 때 가장 앞에 있는 값을 꺼내야 하기 떄문에 맨 처음을 기억할 front

Enqueue 했을 때 맨뒤에 넣기때문에 맨 뒤를 기억할 rear 

이렇게 2개의 변수가 필요합니다.

LIFO인 스택은 마지막 값만 기억하는데 큐는 FIFO라서 첫번째와 마지막을 기억하고 있어야 합니다. 

 

또한 스택을 구현할떄와 마찬가지로 생성자의 디폴트 값 10 을 넣어두었고

Dequeue 에는 Call by reference 를 참고하여 &value 값을 넣어 주었습니다.

(C/C++) Call by value 와 Call by reference

 

#include "QueueArray.h"
#include <stdio.h>

QueueArray::QueueArray(int size)
{
	printf("생성자\n");

	maxSize = size + 1;				//size = 내가 사용할 크기 / +1 = 비어있는 값 rear
	arrays = new int[maxSize];			//배열 동적 할당
	front = rear = 0;				//front와 rear 이 같으면 비어있다.
}

QueueArray::~QueueArray()
{
	delete[] arrays;				//배열로 동적할당 했기 때문에 delete[]

	printf("소멸자\n");
}

bool QueueArray::Enqueue(int value)
{
	if ((rear + 1) % maxSize == front)		//큐가 꽉차있으면
		return false;

	*(arrays + rear++) = value;			//값을 넣어준다.
	rear %= maxSize;				//환형을 위해서
	printf("enqueu : %d\t", value);
	printf("front : %d \t rear : %d\n", front,rear);
	return true;
}

bool QueueArray::Dequeue(int& value)
{
	if (front == rear)				//큐가 비어있으면
		return false;

	value = *(arrays + front++);			//값을 넣어준다.
	front %= maxSize;				//환형을 위해서
	printf("dequeu : %d\t", value);
	printf("front : %d \t rear : %d\n", front, rear);
	return true;
}

void QueueArray::Clear()
{
	front = rear;					//같으면 큐는 비어있다.
	printf("clear\n");
}

void QueueArray::PrintAll()
{
	for (int i = front; i != rear; i = ++i % maxSize)
	{
		printf("%d\t", *(arrays + i));
	}
	printf("\n");
}

배열 큐의 CPP 입니다.

위에서도 설명 드렸듯이

rear 는 빈 공간을 가르키고

front 와 rear 가 같다면 큐는 빈게 됩니다! 

또한 빈공간을 위해  size + 1 로 maxSize 값을 초기화 하였습니다.

 

#include "QueueArray.h"

int main()
{
	QueueArray *arrayQueue = new QueueArray(3);

	arrayQueue->Enqueue(10);
	arrayQueue->Enqueue(20);
	arrayQueue->Enqueue(30);
	arrayQueue->Enqueue(40);
	arrayQueue->PrintAll();

	int temp;
	arrayQueue->Dequeue(temp);
	arrayQueue->Dequeue(temp);
	arrayQueue->PrintAll();

	arrayQueue->Enqueue(50);
	arrayQueue->Enqueue(60);
	arrayQueue->PrintAll();
	arrayQueue->Clear();
	arrayQueue->PrintAll();
	
	delete arrayQueue;

}

배열 큐 결과

 

생성자에서 크기를 3으로 초기화 했기 때문에 3개의 값만 들어간 것을 볼 수 있습니다.

(사실 비어있는 값 rear 를 위해서 배열의 크기가 1개 더 크지만요!)

Enqueue 했을떄는 rear 이 증가하고 Dequeue 했을떄는 front가 증가하는 것도 볼 수 있습니다!

 

3. 링크드 리스트를 이용한 큐 구현

 

링크드리스트의 큐는 이중연결리스트 를 사용하여 구현합니다.

넣는 위치는 꼬리 이전, 빼는 위치는 머리 다음 이기때문에

아무래도 앞 뒤 정보를 가지고 있는 이중 연결 리스트가 구현하기 더 편해서 그렇습니다!

단일 연결리스트로 구현 못하는 것은 아니지만 조금 비효율 적이죠 ㅎㅎ

맨 뒤 노드를 찾아서 꺼낼때 앞에있는 노드를 찾아서 연결해야 하니까요!

(C) 자료구조 - 단일 연결 리스트(Singly Linked List)

위 글에 DeleteNode 함수를 보고 오시면 이해 되실 겁니다!

 

c로 구현한 이중연결리스트에 대한 글은 아래 있습니다.

(C) 자료구조 - 이중 연결 리스트(Doubly Linked List)

 

class QueueLinkedList
{
	struct Node					
	{
		int data;			//값
		Node* prev;			//이전 노드 정보
		Node* next;			//다음 노드 정보
	};

private:
	Node* head;				//머리 더미
	Node* tail;				//꼬리 더미

public:
	QueueLinkedList();			//생성자
	~QueueLinkedList();			//소멸자
	bool Enqueue(int value);		//값을 넣는다.
	bool Dequeue(int& value);		//값을 뺀다
	void Clear();				//모든 값을 비운다.
	void PrintAll();			//모든 값을 출력한다.
};

링크드리스트 큐의 헤더입니다.

 

링크드리스트로 구현했기 때문에 따로 크기를 지정해 줄 필요가 없습니다.

 

#include "QueueLinkedList.h"
#include <stdio.h>

QueueLinkedList::QueueLinkedList()
{
	printf("생성자\n");

	head = new Node();			//머리 노드 할당
	tail = new Node();			//꼬리 노드 할당
	head->prev = head;			//머리 이전은 머리
	head->next = tail;			//머리 다음은 꼬리
	tail->prev = head;			//꼬리 이전은 머리
	tail->next = tail;			//꼬리 다음은 꼬리
}

QueueLinkedList::~QueueLinkedList()
{
	Clear();				//값을 모두 비워준다.
	delete head;				//머리 노드 삭제
	delete tail;				//꼬리 노드 삭제

	printf("소멸자\n");
}

bool QueueLinkedList::Enqueue(int value)
{
	Node* newNode = new Node();		//생성된 노드
	newNode->data = value;			//생성된 노드 값 할당
	tail->prev->next = newNode;		//생성된 노드 위치는 꼬리 이전노드의 다음
	newNode->prev = tail->prev;		//생성된 노드 이전은 꼬리 이전노드
	newNode->next = tail;			//생성된 노드의 다음은 꼬리
	tail->prev = newNode;			//꼬리 이전은 생성된 노드

	printf("enqueue : %d\n", newNode->data);
	return true;
}

bool QueueLinkedList::Dequeue(int& value)
{
	if (head->next == tail)			//큐가 비어있으면
		return false;

	Node* deleteNode = head->next;		//지울 노드는 맨 앞 노드
	value = deleteNode->data;		//값을 빼낸다.

	deleteNode->next->prev = head;		//지울 노드 다음노드의 이전은 머리를 가르킨다.
	head->next = deleteNode->next;		//머리 다음은 지울노드의 다음을 가르킨다.
	delete deleteNode;			//지울 노드를 지운다.
	printf("dequeue : %d\n", value);

	return true;
}

void QueueLinkedList::Clear()
{
	Node* temp = head->next;		//찾는 노드
	Node* deleteNode;			//지울 노드
	while (temp != tail)			//리스트 끝까지 돈다.
	{
		deleteNode = temp;		//현재 노드를 지울 노드로 지정한다.
		temp = temp->next;		//현재 노드는 다음 노드로 넘어간다.
		delete deleteNode;		//지울 노드를 지워준다.
	}
	head->next = tail;			//다 비었으니 head 다음은 tail
	tail->prev = head;			//tail 이전은 head


	printf("clear\n");
}

void QueueLinkedList::PrintAll()
{
	Node* temp = head->next;
	while (temp != tail)
	{
		printf("%d\t", temp->data);
		temp = temp->next;
	}
	printf("\n");
}

 

링크드리스트 큐의 CPP 입니다.

 

위에서 설명드린대로

Enqueue 할떄는 꼬리노드 이전에 Dequeue 할때는 머리노드 다음을

사용 하는 것을 볼 수 있습니다.순환 할 필요가 없기 떄문에 좀 더 자연스럽게 구현 할 수 있었습니다.

중간 노드도 비워야 하기때문에 소멸자에서 Clear 함수도 호출해 주는것을 볼수 있구요!

 

#include "QueueLinkedList.h"

int main()
{
	QueueLinkedList* LinkedQueue = new QueueLinkedList();

	LinkedQueue->Enqueue(10);
	LinkedQueue->Enqueue(20);
	LinkedQueue->Enqueue(30);
	LinkedQueue->Enqueue(40);
	LinkedQueue->PrintAll();

	int temp;
	LinkedQueue->Dequeue(temp);
	LinkedQueue->Dequeue(temp);
	LinkedQueue->PrintAll();

	LinkedQueue->Clear();
	LinkedQueue->PrintAll();

	delete LinkedQueue;
}

링크드 리스트 큐 결과

 

추가 될때는 뒤에서 부터 뺄때는 앞에서부터

잘 작동하는 것을 확인 하였습니다!

 

감사합니다.

 

다른 자료구조

단일 연결 리스트(Singly Linked List)

이중 연결 리스트(Doubly Linked List)

스택(Stack) - 배열(Array), 링크드리스트(Linked List)

큐(Queue) - 배열(Array), 링크드리스트(Linked List)

이진트리(Binary Tree) - 링크드리스트(Linked List)

이진트리(Binary Tree) - 링크드리스트(Linked List)

우선순위 큐(Priority Queue) - 힙(Heap) - 배열(Array)