INDEX
3-7. printQueueContents(큐에 있는 원소들 출력)
1. 개요
FIFO(First In First Out) 방식을 취하고 있는 자료구조이다. 스택(Stack)의 업그레이드 버전이라고 생각하면 쉽다. 왜냐하면 입출구를 공유하는 스택과는 다르게 큐는 입구와 출구가 다르기 때문이다. 큐는 단방향 구조인 동시에 rear부분에서 enqueue(데이터 삽입)와 front부분에서 dequeue(데이터 출)가 발생하는 특징이 있다.
2. 배열? 연결리스트?
큐를 구현함에 있어 두 가지 선택지가 있다. 배열을 사용할 것이냐, 연결 리스트를 사용할 것이냐 이다. 먼저 정답부터 말하면 연결리스트를 사용해야 한다. 배열은 입력받은 데이터를 직관적으로 차례대로 입력받기 편할지 몰라도 크기 조정에 있어 막대한 비용이 요구된다. 배열을 사용할 경우 큐의 크기가 늘거나 줄어들 때 resizing이 필요하다. 이 과정은 O(n) 만큼의 비용이 발생하기 때문에 상당히 비효율적이다.
반면에 연결 리스트는 동적으로 메모리를 할당하고 데이터의 요소들을 순차적으로 저장하기 때문에 enqueue, dequeue 모두 시간 복잡도가 O(1)인 장점이 있다. 따라서 배열보다 메모리를 훨씬 효과적으로 관리할 수 있는 것이다.
3. 구현
C언어로 큐를 만들어볼 것이다.
일단 큐를 만들기 위해서는 다음과 같은 구성으로 출발할 것이다.
- 큐의 구조 정립(Node, Queue)
- 큐 초기화(initQueue)
- 큐가 비어 있는지 확인(isEmpty)
- 데이터 삽입(enqueue)
- 데이터 반환(dequeue)
- 큐 내용물 출력(printQueueContents)
3-1. Node(노드)
typedef struct Node{
int data; // 노드에 저장되는 정수 데이터
struct Node* next; // 다음 노드를 가리키는 포인터
} Node; // 즉 Node라는 구조체는 data, next를 포함한다.Node 구조체는 두 가지 멤버가 있다. Node 자체가 운반하고 있는 data 값, Node가 가리키고 있는 next(next는 자신이 추가되고 난 다음에 최초로 들어오게 된 노드를 가리킨다)가 그것이다.
헷갈리면 안 된다!! next는 나보다 먼저 들어온 바로 앞 노드를 가리키는 것이 아니라 나 바로 직전에 들어온 노드를 가리키는 것이다. 하나 익숙하지 않은 것은 Node 구조체 안에 Node형의 next 포인터 변수를 다시 선언한 것이다. 이런 복잡한 구조가 나오게 된 이유는 Node가 가리키는 next도 Node이기 때문이다. 따라서 next는 가리키는 대상이 Node인 동시에 Node의 멤버이어야 하기 때문에 "자기 참조 구조체"인 것이다. 아래의 예시를 보면 더 쉽게 이해할 수 있을 것이다.
#include <stdio.h>
#include <stdlib.h>
typedef struct Person{ // Person은 age와 그 다음 사람인 next포인터를 멤버로 갖는다.
int age;
struct Person* next;
}Person;
int main(){
Person p1, p2;
p1.age=10;
p1.next=&p2; // p1의 next는 p2를 가리킨다.
p2.age=20;
p2.next=NULL; // p2 다음 사람은 존재하지 않으므로 next를 NULL을 가리키게 함.
printf("%d", p1.next->age);
}결국 p1.next->age와 p2.age는 같은 의미를 갖고 있는 것이다.
3-2. Queue(큐)
typedef struct Queue{
Node* front; // 큐의 맨 앞에 있는 노드를 가리키는 포인터
Node* rear; // 큐의 맨 뒤에 있는 노드를 가리키는 포인터
int count; // 현재 큐에 저장된 노드의 개수
} Queue;큐는 오직 앞(front)과 뒤(rear)만 트래킹 한다.
front와 rear을 Node의 포인터로 선언함으로써 (큐) -> (rear, front) -> (data, next)의 방식으로 한번에 접근할 수 있다.
현재 큐에 들어 있는 노드의 개수에 따라 enqueue, dequeue의 반응이 달라지기 때문에 count변수를 따로 만들어준다. 정확한 상황은 이후에 만날 수 있다.
3-3. initQueue(초기화)
void initQueue(Queue* queue){ // 포인터를 매개변수로 받음
queue -> front = queue -> rear = NULL; // 앞과 뒤를 모두 NULL로 설정해 큐를 비어 있는 상태로 만듬
queue -> count = 0; // 큐 안에 노드가 없음을 나타냄
}큐가 새로이 초기화 됐기 때문에 큐의 front, rear 모두 NULL로 초기화되고 count 또한 0으로 초기화된다.
3-4. isempty(비어 있는지 확인)
int isEmpty(Queue* queue){
return queue -> count == 0; // 큐가 비어있으면 statement가 참이므로 1 반환
}큐가 비어 있으면 queue->count==0이 참이므로 1 리턴, 거짓이면 0 리턴.
3-5. enqueue(데이터 삽입)
void enqueue(Queue* queue, int data){
/*새로운 노드를 동적으로 할당하여 메모리에 생성함.
*할당된 메모리 주소를 newnode 포인터에 저장함.
*큐의 크기는 정적이 아니기 때문에 malloc을 사용해줌.*/
Node *newnode=(Node*)malloc(sizeof(Node));
/*새로 생성한 노드(newnode)의 data멤버에 매개변수로
*전달된 data값을 저장함. 이로써 새로운 노드에 데이터가 설정됨.*/
newnode -> data = data;
/*새로운 노드의 next 포인터를 NULL로 설정함으로써 새로운 노드가
*큐의 맨 뒤에 위치하며 다음 노드가 없음을 나타냄.*/
newnode -> next = NULL;
if(isEmpty(queue)){ // 큐의 count 멤버가 0이면
/* 아무 노드도 없는 경우이므로 queue->front를
* 새로운 노드인 newnode로 설정함으로써 큐의 첫 번째 노드를 가리키게함. */
queue -> front = newnode;
}
else{
/* 큐가 비어 있지 않으면 기존의 맨 뒤 노드(queue->rear)의
* next 포인터를 새로운 노드인 newnode로 설정.*/
queue -> rear -> next = newnode;
}
queue -> rear = newnode; // queue->rear포인터를 큐의 맨 뒤 노드를 가리키게 함
queue -> count++; // 큐 안의 노드 개수를 1 증가시킴
}노드의 개수가 한 개 증가할 것이기 때문에 newnode를 생성해 준다. 새로운 노드의 data멤버에 data를 대입한다. 말이 약간 이상하긴 하지만 newnode->data에 나오는 data는 Node의 멤버 변수이고 인자로 전달받은 data는 새로운 노드에 할당될 데이터 값이다.
아직 newnode의 next가 어디를 가리켜야 할지 모르므로 NULL을 가리키게 해 준다.
만약 queue가 비어 있으면 front를 newnode로 설정하고 비어 있지 않으면 queue의 rear의 next를 이제 막 따끈따끈(?)하게 들어온 newnode로 연결시켜 준다.
조건문을 탈출하고 나서 큐가 비어 있든 차 있든 공통으로 거쳐야 하는 작업인 rear를 nexnode로 바꾸어주는 작업을 한다. 마지막으로 count를 1 증가시킨다.
3-6. dequeue(데이터 반환)
int dequeue(Queue* queue){
int data;
Node* ptr;
if(isEmpty(queue)){
printf("Error : Queue is empty!!\n");
return 0;
}
// queue의 front를 ptr로 경로 설정
ptr=queue->front;
// 반출할 데이터를 (int)data에 저장
data=ptr->data;
// front가 원래 지정하고 있던 next를 큐의 front로 바꾸어줌
queue->front=ptr->next;
free(ptr);
queue->count--;
return data;
}반출할 값 data를 선언하고 사라질 front를 대신해서 ptr를 사용한다. 반출할 노드가 없으면(큐가 비어 있으면) 함수를 탈출한다.
큐의 front 노드를 ptr에 저장한다. 즉 front의 next, data 멤버 정보는 모두 ptr로 넘어간 것이다. 반출할 데이터를 ptr->data로 끌어와 저장하고 큐의 front를 ptr(현재의 front)의 next로 대체해 준다. 이제 노드의 이동, 데이터의 이동이 완료되었으니 ptr의 메모리를 풀어주고 count를 하나 줄임과 동시에 얻은 data를 반환한다.
3-7. printQueueContents(큐에 있는 원소들 출력)
void printQueueContents(Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty.\n");
return;
}
Node* currentnode = queue->front; // 큐의 front에서부터 시작
printf("Queue Contents: ");
while (currentnode != NULL) {
printf("%d ", currentnode->data); // 노드의 데이터 출력
currentnode = currentnode->next; // 다음 노드로 이동
}
printf("\n");
}front에서부터 시작해서 next 노드로 계속 넘어가면서 node의 data값만 출력해 준다. 이 과정을 currentnode가 NULL일 때까지 반복해 준다. <3-5 enqueue> 과정에서 rear노드를 NULL로 만들어줬기 때문이다.
3-8. 주석 제거한 전체 코드
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node* next;
} Node;
typedef struct Queue{
Node* front;
Node* rear;
int count;
} Queue;
void initQueue(Queue* queue){
queue -> front = queue -> rear = NULL;
queue -> count = 0;
}
int isEmpty(Queue* queue){
return queue -> count == 0;
}
void enqueue(Queue* queue, int data){
Node *newnode=(Node*)malloc(sizeof(Node));
newnode -> data = data;
newnode -> next = NULL;
if(isEmpty(queue)){
queue -> front = newnode;
}
else{
queue -> rear -> next = newnode;
}
queue -> rear = newnode;
queue -> count++;
}
int dequeue(Queue* queue){
int data;
Node* ptr;
if(isEmpty(queue)){
printf("Error : Queue is empty!!\n");
return 0;
}
ptr=queue->front;
data=ptr->data;
queue->front=ptr->next;
free(ptr);
queue->count--;
return data;
}
void printQueueContents(Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty.\n");
return;
}
Node* currentnode = queue->front;
printf("Queue Contents: ");
while (currentnode != NULL) {
printf("%d ", currentnode->data);
currentnode = currentnode->next;
}
printf("\n");
}
int main(void)
{
int i;
Queue queue;
initQueue(&queue);
for (i = 1; i <= 10; i++)
{
enqueue(&queue, i);
}
while (!isEmpty(&queue))
{
printQueueContents(&queue);
printf("%d\n", dequeue(&queue));
}
printf("\n");
return 0;
}'자료구조&알고리즘 > 자료구조' 카테고리의 다른 글
| [자료구조] 덱(Deque)의 개념과 연결 리스트로 구현(C언어) (0) | 2024.01.21 |
|---|---|
| [자료구조] 스택을 활용해서 두 자리 수 이상의 연산이 가능한 계산기 만들기(C언어) (2) | 2024.01.02 |
| [자료구조] 연결 리스트(C언어) (0) | 2023.12.24 |
