[자료구조] - LinkedQueue 구현 (C++)

1. 개요

 

 이번에 정리할 내용은 LinkedQueue에 관한 내용이다. Queue는 구현 방법에 따라 CircularQueue와 LinkedQueue 등으로 나눌 수 있는데 이 블로그에서는 LinkedQueue에 대한 설명만 진행할 것이다. 사실 Queue의 기능을 구현하는 방법은 정말 다양하지만 대표적인 두 방법으로 배열과 나머지연산을 활용하는 CircularQueue와 연결리스트로 구현하는 LinkedQueue가 있으니 CircularQueue도 꼭 공부해보기를 바란다.

 

2.이론

 

 큐는 '나오는 방식이 조금 다른 스택' 이라고 생각하면 편하다. Stack과 같은 경우는 먼저 들어간 데이터가 가장 나중에 나오는 FILO 구조이지만, Queue와 같은 경우 가장 먼저 들어간것이 가장먼저 나오는 FIFO(First In First Out)의 구조이다. 혹시 스택이 기억 안나는 분을 위해 링크를 걸도록 하겠다.

 

스택: https://apape1225.tistory.com/16?category=821837

[자료구조] - Stack의 구현( C, C++ )

 큐와 같은 경우 다음과 같이 그릴 수 있다.

---

 

 

---

 얼핏 보면 LinkedList와 같아 보이지만, 기능은 다르다. Front는 맨 첫 노드를 가리키는 노드이고 Rear는 맨 마지막 노드를 가리킨다. 그리고 LinkedList의 기능은 다음과 같다.

---

1. Insert

2. Delete

---

- Insert

 

 Insert는 말 그대로 노드를 추가하는 기능이다. 단, Rear부분에서 노드의 추가가 이루어져야 한다. 그림으로 설명하면 다음과 같다.

---

 

---

 중요한 부분은 첫 상태에서의 노드 추가와 노드를 추가한 후, Rear포인터가 마지막 노드를 가리킬 수 있도록 링크를 조작해주는 것이다.

 

- Delete

 

 Delete도 말 그대로 노드를 삭제해주는 기능이다. 중요한점은 Front부분에서 삭제가 이루어져야 한다는 것이다. 그림으로 표현하면 다음과 같다.

---

 

---

 

3. 코드 구현

 

 이번 LinkedQueue 또한 Class로 구현하였다. OOP적인 프로그래밍을 연습한다는 취지이다.(물론 제일 중요한 OOP적인 디자인은 시도도하지 않았지만 ㅠㅠ) 다음은 이 자료구조에서 사용한 헤더와 구조체이다.

 

-LinkedQueue.h

 

#pragma once
#include <cstdio>

typedef struct Node{
	int data;
	Node *link;
} Node, *NodePtr;

class LinkedQueue
{
private:
	NodePtr front, rear;
	int count;
	void deleteAllQueue();
public:
	LinkedQueue();
	~LinkedQueue();
	bool insertQueue(int n);
	int deleteQueue();
	int getAmount() { return count; }
	void printQueue();
};

 

 다음은 메소드의 정의이다. 여기서 핵심은 insertQueue()와 deleteQueue()이다. 나머지는 이들을 보조해주거나 이 자료구조를 test하는 main() 함수에서 편하게 시험할 수 있도록 도와주는 함수이다. 다음은 구현부분이다.

 

-LinkedQueue.cpp

 

#include "LinkedQueue.h"

LinkedQueue::LinkedQueue()
{
	front = rear = nullptr;
	count = 0;
}

LinkedQueue::~LinkedQueue()
{
	deleteAllQueue();
	printf("모든 큐가 삭제되었습니다!\n");
}

bool LinkedQueue::insertQueue(int n) {
	NodePtr pNew = new Node;
	if (pNew) {
		pNew->data = n;
		if (front && rear) {
			rear = rear->link = pNew;
			pNew->link = nullptr;
		}
		else {
			front = rear = pNew;
		}
		count++;
	}
	return (int)pNew;
}

int LinkedQueue::deleteQueue() {
	if (front) {
		NodePtr pDel = front;
		int buff = pDel->data;
		front = pDel->link;
		delete pDel;
		count--;
		return buff;
	}
	else
		return NULL;
}

void LinkedQueue::deleteAllQueue() {
	while (front != rear) {
		NodePtr pDel = front;
		front = pDel->link;
		delete pDel;
	}
	delete front;
}

void LinkedQueue::printQueue() {
	if (front && rear) {
		NodePtr buff = front;
		for (int i = 0; i < count; i++)
			printf("------");
		printf("\n");
		while (buff != rear) {
			printf("%d --> ", buff->data);
			buff = buff->link;
		}
		printf("%d", buff->data);
		printf("\n");
		for (int i = 0; i < count; i++)
			printf("------");
		printf("\n");
	}
}

 

 다음은 main() 함수이다.

 

- main() 함수

 

 이 main() 함수에서는 이 자료구조를 시험해보는 함수이다. 다음과 같이 작성하였다.

 

#include "LinkedQueue.h"

LinkedQueue::LinkedQueue()
{
	front = rear = nullptr;
	count = 0;
}

LinkedQueue::~LinkedQueue()
{
	deleteAllQueue();
	printf("모든 큐가 삭제되었습니다!\n");
}

bool LinkedQueue::insertQueue(int n) {
	NodePtr pNew = new Node;
	if (pNew) {
		pNew->data = n;
		if (front && rear) {
			rear = rear->link = pNew;
			pNew->link = nullptr;
		}
		else {
			front = rear = pNew;
		}
		count++;
	}
	return (int)pNew;
}

int LinkedQueue::deleteQueue() {
	if (front) {
		NodePtr pDel = front;
		int buff = pDel->data;
		front = pDel->link;
		delete pDel;
		count--;
		return buff;
	}
	else
		return NULL;
}

void LinkedQueue::deleteAllQueue() {
	while (front != rear) {
		NodePtr pDel = front;
		front = pDel->link;
		delete pDel;
	}
	delete front;
}

void LinkedQueue::printQueue() {
	if (front && rear) {
		NodePtr buff = front;
		for (int i = 0; i < count; i++)
			printf("------");
		printf("\n");
		while (buff != rear) {
			printf("%d --> ", buff->data);
			buff = buff->link;
		}
		printf("%d", buff->data);
		printf("\n");
		for (int i = 0; i < count; i++)
			printf("------");
		printf("\n");
	}
}

 

3. 결어

 

 다음엔 Tree에대해 정리할 것이다. Tree다음엔 본격적인 알고리즘 정리할 생각이다.