연결리스트 기반으로 구현한다고 쳐도
여전히 스택과 큐는 차이점이 있는데
바로 stack은 push/pop이 이뤄지는 위치가 동일한 반면, 큐는 enqueue/dequeue가 이뤄지는 위치가 다르다는것이다.
우선 연결리스트 기반 큐의 헤더파일을 소개한다 !
ListBaseQueue.h
#ifndef ListBaseQueue_h
#define ListBaseQueue_h
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node{
Data data;
struct _node *next;
}Node;
typedef struct _LQueue{
Node *front;
Node *rear;
}LQueue;
typedef LQueue Queue;
void QueueInit(Queue*pq);
int QIsEmpty(Queue*pq);
void Enqueue(Queue*pq,Data data); // enqueue 연산 담당 함수
Data Dequeue(Queue*pq); //dequeue 연산 담당 함수
Data QPeek(Queue*pq);
#endif /* ListBaseQueue_h */이다!
이를 기반으로 기능을 생각해보자
우선, 초기화를 해야한다.
초기화 시 F,R은 Null을 가리켜야 하므로 !
QueInit 함수는
void QueueInit(Queue * pq)
{
pq -> front = NULL;
pq -> rear = NULL;
}이다
그리고 F가 가리키는 노드를 대상으로 dequeue 연산이 진행되니 "연결 리스트 기반의 큐가 비었다면, F에 Null이 저장된다"라고 생각할 수 있다.
그러므로 QIsEmpty 함수는
int QIsEmpty(Queue * pq)
{
if(pq->front == NULL) //F에 Null이 저장되어 있다면
return TRUE; //큐가 텅 빈 것이니 True를 반환한다 !
else
return FALSE;
}이다 !
이제 Enqueue 함수를 정의할 차례이다.
이 함수를 정의 할때에는 추가과정이 둘로 나뉘는데 바로 처음 노드를 추가할때와 그 이후이다.
-
처음 추가할 경우
F와 R이 모두 Newnode를 가리키도록 해야한다. -
이후 추가하는 경우
F는 변함없는 대신 R이 새 노드를 가리키고, 노드간의 연결을 위해 가장 끝에 있는 노드가 새 노드를 가리키어야 한다 !
이를 기반으로 Enqueue 함수를 짜보자 !
void Enqueue(Queue * pq, Data data)
{
Node * newNode = (Node*)malloc(sizeof(Node)); // Newnode 동적할당
newNode->next = NULL;
newNode->data = data;
if(QIsEmpty(pq)) //Queue가 비었을때
{
pq->front = newNode;
pq->rear = newNode;
}
else
{
pq->rear->next = newNode; //pq->rear->next 는 마지막노드가 가리키는 다음 노드
pq->rear = newNode; // 꼬리가 새노드를 가리키게 한다.
}
}이다 ! 생각한 그대로라서 생각보다 간단한 코드다 !
이제 마지막으로 Dequeue함수를 정의할 차례인데..
Enqueue함수와 마찬가지로 삭제도 두가지 경우로 나누어질꺼야..! 라고 생각한다면!!
그렇지 않다 !!! ! !!! !
노드의 삭제 과정에서는 신경 쓸 것은 오.로.지 F뿐이다.
dequeue연산과정을 생각해보자
- F가 다음 노드를 가리키게 한다.
- F가 이전에 가리키던 노드를 소멸시킨다.
하나씩..삭제하다보면 F와 R이 같은 노드를 가리키는 상황이 발생하는데 이때 F가 다음노드를 가리키면 마지막노드의 다음노드는 Null이 저장되어 있으므로 !
F는 Null을 가리킨다.
반면... R은 쓰레기값을 가지는데 ..
이것은 문제가 되지 않는다!
왜냐하면 QIsEmpty 함수를 정의 할 때에도 F에 저장된 값만을 참조 하여 T/F를 반환하였기때문에 굳이 과정을 둘로 나눠 R에 Null을 넣지 않아도 된다.
그러므로 !
Data Dequeue(Queue * pq)
{
Node * delNode;
Data retData;
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
delNode = pq->front; //삭제할 노드의 주소 값 저장(first를 먼저 삭제하니깐 !!)
retData = delNode->data;
pq->front = pq->front->next;
free(delNode);
return retData;
}이다!
QPeek는 간단히 예외 확인 후 pq->front->data;를 반환 해주면 된다.
이제 이를 기반으로 ListBaseQueue.c 파일을 보여주겠다.
#include <stdio.h>
#include <stdlib.h>
#include "ListBaseQueue.h"
void QueueInit(Queue * pq)
{
pq -> front = NULL;
pq -> rear = NULL;
}
int QIsEmpty(Queue * pq)
{
if(pq->front == NULL) //F에 Null이 저장되어 있다면
return TRUE; //큐가 텅 빈 것이니 True를 반환한다 !
else
return FALSE;
}
void Enqueue(Queue * pq, Data data)
{
Node * newNode = (Node*)malloc(sizeof(Node)); // Newnode 동적할당
newNode->next = NULL;
newNode->data = data;
if(QIsEmpty(pq)) //Queue가 비었을때
{
pq->front = newNode;
pq->rear = newNode;
}
else
{
pq->rear->next = newNode; //pq->rear->next 는 마지막노드가 가리키는 다음 노드
pq->rear = newNode; // 꼬리가 새노드를 가리키게 한다.
}
}
Data Dequeue(Queue * pq)
{
Node * delNode;
Data retData;
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
delNode = pq->front; //삭제할 노드의 주소 값 저장(first를 먼저 삭제하니깐 !!)
retData = delNode->data;
pq->front = pq->front->next;
free(delNode);
return retData;
}
Data QPeek(Queue * pq)
{
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
return pq->front->data;
}다음은 큐를 테스트 하기위한 main이다 .
ListBaseQueueMain.c
#include <stdio.h>
#include "ListBaseQueue.h"
int main(void)
{
// Queue의 생성 및 초기화 //
Queue q;
QueueInit(&q);
// 데이터 넣기 //
Enqueue(&q, 1); Enqueue(&q, 2); Enqueue(&q, 3); Enqueue(&q, 4); Enqueue(&q, 5);
// 데이터 꺼내기 //
while(!QIsEmpty(&q)) // queue가 비어 있지 않는 이상 계속 와이이이일~~
printf("%d ", Dequeue(&q));
return 0;
}상세 그림들은 추후에 그려서 추가 하겠다 !!!
