C로 만드는 자료구조- 연결 리스트로 구현한 큐

연결 리스트로 구현한 큐

연결 리스트로 구현한 큐의 장점은 미리 큐의 최대 크기를 정하지 않아도 된다는 점이다. 미리 최대 크기를 정하지 않기 때문에 배열 큐에서 빈공간이 있어도 리어 노드 앞에 공간이 없어 인큐 연산을 못하는 경우가 생기지 않기 때문에 메모리를 좀더 효울적으로 사용이 가능하다.

연결 리스트 큐의 구현

얀결 리스트를 이용해 스택을 구현할 때와 마찬가지로 연결 리스트를 사용하는데 연결 리스트를 통째로 사용하기 보다는 큐의 프런트 노드와 리어 노드에 대한 접근만 하면 되기 때문에 프런트 노드와 리어 노드를 가리키는 포인터만 사용한다.

각 함수 중간에 LQ가 있는데 LinkedQueue을 의미한다.

소스 파일 구성은 다음과 같다.

파일 이름	내용
linkedqueue.h	구조체 및 함수 선언
linkedqueue.cpp	함수 구현
linkedqueuemain.cpp	main 함수 실행

1.linkedqueue.h

#pragma once
#pragma once
#include<iostream>

using namespace std;
#define TRUE 1
#define FALSE 0

typedef struct QueueNode {
	int data;
	struct QueueNode* pLink;
};

typedef struct LinkedQueue {
	int currentSize;
	QueueNode* pFront;
	QueueNode* pRear;
};

LinkedQueue* createLQ(); // 큐 생성
int enqueueLQ(LinkedQueue* pQueue, QueueNode element); // 큐 enqueue
QueueNode* dequeueLQ(LinkedQueue* pQueue); // 큐 dequeue
QueueNode* peekLQ(LinkedQueue* pQueue); // 큐 peek
void deleteLQ(LinkedQueue* pQueue); // 큐 삭제
int isEmptyLQ(LinkedQueue* pQueue); // 빈 큐인지 확인
void displayLQ(LinkedQueue* pQueue);// 큐 자료 출력

- QueueNode는 큐에 저장되는 각각의 자료들을 의미하며 실제 값인 data와 큐 내에서 다음 노드를 가리키는 포인터 pLink를 포함한다.
- LinkedQueue는 실제 큐를 의미하며 연결 리스트로 구현하기 때문에 최대 자료 저장 개수는 필요하지 않고 현재 저장된 자료 개수(currentSize)와 큐의 프런트 노드와 리어 노드를 가리키는 포인터 (pFront,pRear)을 포함한다.

전체적인 형태는 다음과 같다.

연결 리스트로 구현하는 큐는 크기의 한계가 없기 때문에 스택이 가득 찼는지 아닌지를 알려주는 함수는 필요가 없다. 추가적으로 #define을 이용해 TURE은 1,FALSE는 0 값으로 정의해주었다.

2.linkedqueue.cpp

- createLQ()

LinkedQueue* createLQ() {
	LinkedQueue* pReturn = new LinkedQueue;
	if (pReturn != NULL) {
		memset(pReturn, 0, sizeof(LinkedQueue));

	}
	else {
		cout << "메모리 할당 오류" << endl;
	}
	return pReturn;
}

LinkeQueue에 대해 객체를 선언 후 메모리를 할당 한다. 메모리 할당 후 memset()을 통해 내부 변수에 대해 초기화를 해준다. 이때 currentSize=0, pFront=NULL,pRear=NULL이 된다.

- enqueue()

연결 리스트를 이용한 큐에서는 인큐 연산을 하기 위해서 확인해야하는 조건은 딱히 없다. 큐 크기의 한계가 없기 때문이다. 인큐 연산을 할 때 2가지 경우의 수가 있는데 하나는 큐가 공빅인 경우, 공백이 아닌 경우가 있다. 추가적으로 반환형은 TRUE/FALSE이다.

1) 공백 큐인 경우
노드를 추가 한 후 포인터 pFront, pRear 이 모두 새로 추가된 노드를 가리키게 하면 된다.
큐안에 노드가 단 하나이기 때문에 그 노드가 프런트 노드, 리어 노드 둘다 해당되기 때문이다.

QueueNode* pNode = new QueueNode; // 새로운 노드 메모리 할당
*pNode = element; // 새로운 노드 메모리에 추가할 자료 대입
pQueue->pFront = pNode; // pFront와 새로운 노드를 연결
pQueue->pRear = pNode; // pRear과 새로운 노드를 연결

2) 공백 큐가 아닌 경우
공백 큐가 아닌 경우 새로운 노드를 추가하고 링크를 재설정해줘야 한다. 프런트 노드는 바뀌지 않기 때문에 변경할 필요는 없고 리어 노드가 새로운 노드가 되기 때문에 포인터 pRear와 새로운 노드, 기존 노드간의 링크를 다시 설정해야한다.

QueueNode* pNode = new QueueNode; // 새로운 노드 메모리 할당
*pNode = element; // 새로운 노드 메모리에 추가할 자료 대입
pQueue->pRear->pLink = pNode; // 기존 리어 노드의 링크를 새로운 노드와 연결 --- (1)
pQueue->pRear = pNode; // pRear과 새로운 노드를 연결 --- (2)

그림으로 나타내면 다음과 같다.

코드 구현은 다음과 같다.

int enqueueLQ(LinkedQueue* pQueue, QueueNode element) {
	int ret = FALSE;
	QueueNode* pNode = new QueueNode;
	if (pQueue != NULL) {

		*pNode = element;
		
		if (isEmptyLQ(pQueue) == TRUE) {
			pQueue->pFront = pNode;
		}
		else {
			pQueue->pRear->pLink = pNode;
		}
		pQueue->pRear = pNode;
		pQueue->currentSize++;
		ret = TRUE;
	}
	return ret;
}

- dequeue()

먼저 디큐연산을 하기 위해 필요한 조건은 큐가 공백 큐인지 아닌지 알아야 한다. 이때 isEmptyLQ() 함수를 이용한다. 공백 큐가 아니면 다음 단계로 간다. 디큐 연산도 2가지 경우가 있다. 큐에 저장된 노드가 단 1개인 경우와 2개이상인 경우이다. 추가적으로 반환형은 QueueNode* 이다. 반환되는 노드는 main함수에서 메모리 해제를 해줄 것이다.

1) 노드가 1개만 있는 경우
pReturn에 프런트 노드를 전달하고 더 이상 큐에 노드가 존재하지 않기 때문에 pFront, pRear 모두 NULL값으로 초기화 해준다.

pReturn = pQueue->pFront; // 프런트 노드 값 전달
pQueue->pFront = NULL; // 값 초기화
pQueue->pRear = NULL; // 값 초기화

2) 노드가 2개 이상인 경우
노드가 2개 이상이기 때문에 프런트 노드를 반환 후 링크들을 재설정 해야한다. 리어 노드는 건들지 않기 때문에 변경할 필요가 없고 새로운 프런트 노드와 pFront 간에 링크를 설정 해주어야한다.

pReturn = pQueue->pFront; // 프런트 노드 값 전달
pQueue->pFront = pReturn->pLink; // 새로운 프런트 노드와 pFront 연결

그림으로 나타내면 다음과 같다.

코드 구현은 다음과 같다.

QueueNode* dequeueLQ(LinkedQueue* pQueue) {
	QueueNode* pReturn = new QueueNode;
	if (pQueue != NULL) {

		if (isEmptyLQ(pQueue) == FALSE) {
			pReturn = pQueue->pFront;
			if (pQueue->currentSize == 1) {
				pQueue->pFront = NULL;
				pQueue->pRear = NULL;
			}
			else {
				pQueue->pFront = pReturn->pLink;
			}
			pQueue->currentSize--;
		}
		else {
			cout << "공백 큐 입니다." << endl;
		}
	}
	return pReturn;
}

- peek()

피크 연산은 디큐연산과 동일하지만 반환되는 노드를 제거 하지 않기 때문에 링크를 따로 재설정할 필요가 없다는 점이 차이점이다.

그림으로 나타내면 다음과 같다.

코드 구현은 다음과 같다.

QueueNode* peekLQ(LinkedQueue* pQueue){

	QueueNode* pReturn = new QueueNode;
	if (pQueue != NULL) {
		if (isEmptyLQ(pQueue) == FALSE) {
			pReturn = pQueue->pFront;
		}
		else {
			cout << "공백 큐 입니다." << endl;
		}
	}
	return pReturn;
}

나머지 함수 구현 코드는 다음과 같다.

void deleteLQ(LinkedQueue* pQueue) {
	
	QueueNode *pNode = NULL;
	QueueNode *pDelNode = NULL;
	pNode = pQueue->pFront;
	if (pQueue != NULL) {
		for (int i = 0; i < pQueue->currentSize; i++) {
			pDelNode = pNode;
			pNode = pNode->pLink;
			delete pDelNode;
		}
	}
	delete pQueue;

}
int isEmptyLQ(LinkedQueue* pQueue) {
	int ret = FALSE;
	if (pQueue != NULL) {
		if (pQueue->currentSize == 0) {
			ret = TRUE;
		}
	}
	return ret;
}
void displayLQ(LinkedQueue* pQueue) {
	if (pQueue != NULL) {
		QueueNode *pNode = NULL;
		pNode = pQueue->pFront;
		cout << "현재 자료 개수: " << pQueue->currentSize << endl;
		for (int i = 0; i < pQueue->currentSize; i++) {
			cout << "[" << i << "] - [" << pNode->data<< "]" << endl;
			pNode = pNode->pLink;
		}
	}
}

display()함수를 구현 할때 인큐 연산을 하면서 기존 리어 노드와 새로운 노드를 링크로 연결한 것을 이용한다.

3.linkedqueueMain.cpp

메인 함수 실행 코드는 다음과 같다.

#include "stdafx.h"
#include "linkedqueue.h"

int main()
{
	LinkedQueue *pQueue = NULL;
	QueueNode* pNode = NULL;
	QueueNode Node;
	pQueue = createLQ();
	
	if (pQueue != NULL) {
	
		Node.data = 1;
		enqueueLQ(pQueue, Node);
	

		Node.data = 2;
		enqueueLQ(pQueue, Node);
		Node.data = 3;
		enqueueLQ(pQueue, Node);
		Node.data = 4;
		enqueueLQ(pQueue, Node);
		

		displayLQ(pQueue);

		pNode = dequeueLQ(pQueue);
		if (pNode != NULL) {
			cout << "dequeue: " << pNode->data << endl;
			delete pNode;
		}
		displayLQ(pQueue);

		pNode = peekLQ(pQueue);
		if (pNode != NULL) {
			cout << "peek: " << pNode->data << endl;
		}
		displayLQ(pQueue);

		Node.data = 5;
		enqueueLQ(pQueue, Node);
		displayLQ(pQueue);
	}
	else {
		cout << "메모리 오휴다 정신차려라" << endl;
	}
	return 0;
}

여기서 주의해야 할 점은 앞서 말했듯이 디큐 연산 후 반환되는 노드(pNode)에 대해 메모리 해제를 해줘야 한다는 점이다. 위 코드에서는 delete pNode;를 통해 메모리 해제를 해주었다.

실행결과는 다음과 같다.

728x90

저작자표시 비영리

'컴퓨터 공학 > 자료구조' 카테고리의 다른 글

C로 만드는 자료구조- 연결 리스트로 구현한 이진 트리 (0)	2020.09.25
C로 만드는 자료구조- 큐를 이용한 평균 대기 시간 구하기 (0)	2020.09.18
C로 만드는 자료구조-배열로 구현한 큐+(원형 큐) (0)	2020.09.06
C로 만드는 자료구조- Queue란? (0)	2020.09.06
C로 만드는 자료구조-배열로 구현한 스택 (0)	2020.08.29