C Data Structure - 리스트 기반 큐

리스트 기반 큐는 뭐 간단하다. 그냥 일반 큐인데 연결 리스트로 이루어진 큐이다.

기본 형태는 다음과 같다.

매우 간단하다. 그래서 행복하다 

기본적으로 배열 기반의 큐와 똑같이 동작한다. 그러나 배열 기반 큐와 다른 점은 크기가 정해져 있지 않고 동적이고 가변이기 때문에 뭐, 꽉 찬 것으로 보이지만 비어있네, 마네 뭐 이런 배열 기반 큐의 치명적인 단점을 생각할 필요가 없다.

Front 노드 포인터를 통해서 가장 먼저 들어온 노드를 가리키며, 삭제 연산을 진행할 때마다 Front 노드 포인터를 한 노드씩 옮긴다. 그리고 Rear 노드 포인터를 통해서 가장 마지막에 추가된 노드를 가리키며, 삽입 연산을 진행할 때마다, Rear 노드 포인터를 새로운 노드로 갱신한다. 

삽입 연산

 

삭제 연산

 

꽉참/비어짐 확인 연산

꽉 찼는지는 연결 리스트이므로 확인할 필요가 없으니, 비어져있는 상태만 확인하면 되는데 이 역시 매우 간단하다.

Front  노드  포인터가 NULL인지를 확인하면 된다.

메모리 관리

이번에는 연결 리스트 기반 스택으로 관리한다.

코드 및 실행 결과

#include <stdio.h>
#include <stdlib.h>
 
#define STACK_LEN 10
 
#define TRUE 1
#define FALSE 0
 
// 공통 노드 정의
struct node
{
    int data;
    struct node* next;
};
 
// 스택으로 메모리 관리.
struct array_stack
{
    struct node* stack_array[STACK_LEN];
    int top_index;
};
typedef array_stack stack;
 
void StackInit(stack* s);
int SIsEmpty(stack* s);
int SIsFull(stack* s); // 증가시키고 대입이기 때문에 현 index에서 증가시키고 대입이 가능한지를 확인해야함.
void SPush(stack* s, struct node* data); // 증가시키고 대입.
struct node* SPop(stack* s);
struct node* SPeek(stack* s);
void ShowStack(stack* s);
 
struct node* CreateNodeAuto(stack* s);
void RemoveAllNodeAuto(stack* s);
 
// 리스트 기반 큐 자료구조(원형일 필요가 없음)
struct list_queue
{
    struct node* front;
    struct node* rear;
    int count;
};
typedef struct list_queue queue;
 
void QueueInit(queue* q);
int QisEmpty(queue* q);
struct node* Dequeue(queue* q);
void Enqueue(queue* q, stack* s, int data);
void ShowQueue(queue* q);
 
// Main
int main(void)
{
    stack s;
    queue q;
 
    QueueInit(&q);
    StackInit(&s);
 
    printf("큐/스택 생성 시작 --- \n");
 
    Enqueue(&q, &s, 1); ShowQueue(&q);
    Enqueue(&q, &s, 2); ShowQueue(&q);
    Enqueue(&q, &s, 3); ShowQueue(&q);
    Enqueue(&q, &s, 4); ShowQueue(&q);
    Enqueue(&q, &s, 5); ShowQueue(&q);
 
    printf("큐 제거 시작 --- \n");
 
    ShowQueue(&q);
    while (!QisEmpty(&q))
    {
        Dequeue(&q);
        ShowQueue(&q);
    }
    fputc('\n', stdout);
 
    printf("스택 제거 시작 --- \n");
    RemoveAllNodeAuto(&s);
    return 0;
}
 
 
// 메모리 관리 스택 관련 함수
 
void StackInit(stack* s)
{
    int i = 0;
    s->top_index = -1;
    for (i = 0; i < STACK_LEN; i++) // 순회를 위해서 모두 초기화
        s->stack_array[i] = NULL;
    return;
}
int SIsEmpty(stack* s)
{
    if (s->top_index == -1)
        return TRUE;
    else
        return FALSE;
}
int SIsFull(stack* s) // 증가시키고 대입이기 때문에 현 index에서 증가시키고 대입이 가능한지를 확인해야함.
{
    if ((s->top_index) + 1 < STACK_LEN)
        return FALSE;
    else
        return TRUE;
}
void SPush(stack* s, struct node* data) // 증가시키고 대입임 (top_index가 -1부터 시작하기 때문에)
{
    if (SIsFull(s))
    {
        printf("스택이 가득찼습니다\n");
        return;
    }
    s->stack_array[++(s->top_index)] = data;
    return;
}
struct node* SPop(stack* s)
{
    struct node* rtarget = NULL;
    if (SIsEmpty(s))
    {
        printf("스택이 비어져있습니다\n");
        return NULL;
    }
    rtarget = s->stack_array[s->top_index];
    s->stack_array[s->top_index--] = NULL;
    return rtarget;
}
struct node* SPeek(stack* s)
{
    if (SIsEmpty(s))
    {
        printf("스택이 비어져있습니다\n");
        return NULL;
    }
    return s->stack_array[s->top_index];
}
 
void ShowStack(stack* s)
{
    int i = 0;
    printf("{(top:%d)} : ", s->top_index);
    for (i = 0; i < STACK_LEN; i++)
        printf("[%p]", s->stack_array[i]), putc('-', stdout);
    putc('\n', stdout);
    return;
}
 
// 내가 정의하는 함수
 
struct node* CreateNodeAuto(stack* s)
{
    struct node* tmp = (struct node*)malloc(sizeof(struct node));
    // 초기화
    tmp->data = 0;
    tmp->next = NULL; // tmp->next = s->head;
    // 메모리 스택에 추가
    SPush(s, tmp);
 
    return tmp;
}
 
void RemoveAllNodeAuto(stack* s)
{
    struct node* rtarget = NULL;
    ShowStack(s);
    while (!SIsEmpty(s))
    {
        rtarget = SPop(s);
        free(rtarget);
        ShowStack(s);
    }
    return;
}
 
// 큐 자료구조 관련 함수
 
void QueueInit(queue* q)
{
    q->front = q->rear = NULL;
    q->count = 0;
    return;
}
int QisEmpty(queue* q)
{
    if (q->front == NULL)
        return TRUE;
    else
        return FALSE;
}
struct node* Dequeue(queue* q)
{
    struct node* target;
    // 기본 동작 - 비었는가 확인 -> 삭제 -> 인덱스 변경
    if (QisEmpty(q))
    {
        printf("Queue가 이미 비었습니다.\n");
        return NULL;
    }
    // target 추출
    target = q->front;
 
    // front를 맨 앞 노드의 다음 노드로 변경
    q->front = q->front->next;
 
    // 카운트 감소
    q->count--;
    return target;
}
void Enqueue(queue* q, stack* s, int data)
{
    // 노드 생성
    struct node* new_node = CreateNodeAuto(s); // 추가되는 노드가 항상 마지막이 된다.
    new_node->data = data;
    new_node->next = NULL;
 
    ShowStack(s);
 
    if (QisEmpty(q)) // 노드가 처음 추가하는 노드라면 front와 rear 모두 갱신
    {
        q->front = q->rear = new_node;
    }
    else // 노드가 처음 추가하는 노드가 아니라면 rear만 갱신
    {
        q->rear->next = new_node;
        q->rear = new_node;
    }
 
    // 카운트 증가
    q->count++;
    return;
}
 
void ShowQueue(queue* q)
{
    struct node* index = NULL;
    printf("{(r:%p/f:%p)} : ", q->rear, q->front);
    for (index = q->front; index != NULL; index = index->next)
        printf("[%p(%d)]", index, index->data), putc('-', stdout);
    putc('\n', stdout);
    return;
}