C++ Queue 만들기 (version.4 - LinkedList Queue)

C++로 Queue 구현하기 version 4

 

LinkedList로 큐를 만들어 보겠다.

 

LinkedList로 Queue를 구현하기 위해서는 큐 객체에 맨 앞번째 노드를 가리키는 front라는 이름의 포인터 노드, 맨 뒤 노드를 가리킬 rear, 그리고 총 노드의 개수를 저장할 size 변수로 구성시켜야 할 것이다.

 

대강 이런 느낌의 큐를 만들어서 노드를 연결시켜가며 사용하면 될 것이다.

 

값을 enqueue할 때, front와 rear 포인터 노드를 들어오는 노드에 잘 참조하도록 해야하는데 큐가 비어있을 경우와 그렇지 않을 경우에 다르게 작업해야 한다.

큐가 비어있을때 값이 들어온다면 front와 rear가 모두 처음 들어온 노드를 가리키게 해야 한다. 이후에 들어오는 값들은 rear만 다음 노드를 가리키게끔 해준다.

Node는 값을 보관하는 변수 data와 다음 노드를 가리킬 포인터 노드 next로 구성된다.

 

enqueue() 과정은 다음과 같다

enqueue(10)

enqueue(20)

enqueue(30)

 

이런 식으로 데이터 추가가 진행될 것이다

 

dequeue는 front 참조를 바꿔주면서 진행된다

dequeue()

dequeue()

dequeue()

큐에 데이터가 하나밖에 없을 때 dequeue를 하는 경우에는 front와 rear가 NULL을, 즉 아무것도 가리키지 않게 한다.

 

전반적인 동작 메커니즘은 이렇다. 아래는 소스 코드이다

 

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

void main() 
{
	/*Queue q;
	q.enqueue(10);
	q.enqueue(20);
	q.enqueue(30);
	int x = q.dequeue();
	printf("%d\n", x);
	q.enqueue(40);
	q.enqueue(50);
	printf("%d\n", q.dequeue());*/

	Queue *q = new Queue();
	q->print();
	q->enqueue(10);
	q->print();
	q->enqueue(20);
	q->print();
	q->enqueue(30);
	q->print();
	int x = q->dequeue();
	q->print();
	printf("%d\n", x);
	q->print();
	q->enqueue(40);
	q->print();
	q->enqueue(50);
	q->print();
	printf("%d\n", q->dequeue());
	q->print();

	for (int i = 1; i < 20; i++) {
		q->enqueue(i);
		//printf("%d\n", q->dequeue());
	}

	q->print();
	delete q;

	/*Queue q;
	q.print();
	q.enqueue(10);
	q.print();
	q.enqueue(20);
	q.print();
	q.enqueue(30);
	q.print();
	q.enqueue(40);
	q.print();
	printf("%d\n", q.dequeue());
	printf("%d\n", q.dequeue());
	q.print();*/
}

enqueue, dequeue, print를 해보는 메인함수이다.

 

#include <stdio.h>

class Node {
public:
	int data;
	Node *next;
	Node (int x) {
		data = x;
		next = NULL;
	}
};

class Queue {
	Node *front;
	Node *rear;
	int size;
	bool isFull();
	void resize();
	bool isEmpty();
	void emptyError();
public:
	Queue();
	~Queue();
	void enqueue(int x);
	int dequeue();
	void print();
};

Queue 클래스와 Node 클래스로 구성된 헤더 파일이다. 

 

#include "Queue.h"
#include <stdio.h>
#include <stdlib.h>

Queue::Queue() {
	front = NULL;
	rear = NULL;
	size = 0;
}

Queue::~Queue() {

}

void Queue::print() {
	printf("[");
	Node *tmp = front;
	while (tmp != NULL) {
		printf("%d", tmp->data);
		if (tmp->next != NULL) {
			printf(", ");
		}
		tmp = tmp->next;
	}
	printf("]\n");
}

void Queue::enqueue(int x) {
	Node *tmp = new Node(x);
	if (isEmpty()) {
		front = tmp;
		rear = tmp;
		size = size + 1;
	} else {
		size++;
		rear->next = tmp;
		rear = tmp;
	}
}

int Queue::dequeue() {
	if (isEmpty()) {
		emptyError();
	} else if (size == 1) {
		int value = front->data;
		front = NULL;
		rear = NULL;
		size = 0;
		return value;
	} else {
		int value = front->data;
		front = front->next;
		return value;
	}
}

bool Queue::isEmpty() {
	if (size == 0) return true;
	return false;
}

void Queue::emptyError() {
	printf("Empty\n");
	exit(-1);
}

큐 구현 소스파일이다.

 

이상 LinkedList로 구현한 Queue였다.