[자료구조] 3-2. Queue

 

🔗 공부 과정에서 참고한 자료 

https://happysalmon.tistory.com/77?category=911360

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

 

---

Linked List의 Queue는 이중연결리스트를 사용하여 구현
Linked List로 구현했기 때문에 따로 크기를 지정해 줄 필요가 없다

 

 

 

💻 QueueLinkedList.h

#pragma once

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();	// 모든 값을 출력한다
};

 

 

💻 3-2. Queue.cpp

#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;				// 다 빔
	tail->prev = head;

	printf("clear\n");
}

void QueueLinkedList::PrintAll() {

	Node* temp = head->next;
	while (temp != tail) {

		printf("%d\t", temp->data);
		temp = temp->next;
	}
	printf("\n");
}

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;
}

 

이해한 과정 추가하기