[C code] 원형 큐 (Circular Queue)

#include <stdio.h>
#include <stdlib.h>
#define size 10

typedef struct Queue
{
    int front, rear;
    int * data;
}Queue;

void EnQ(Queue * q, int data)
{
    if(q->front == (q->rear+1)%size)  //FullQ
    {
        puts("Queue is Full");
        return;
    }
    else
    {
        q->rear = (q->rear+1)%size;
        q->data[q->rear] = data;
    }
    return;
}

int DeQ(Queue * q)
{
    if(q->front == q->rear)  //EmptyQ
    {
        puts("Queue is Empty");
        return;
    }
    else
    {
        q->front = (q->front+1)%size;
        return q->data[q->front];
    }
}

int main()
{
    Queue q;
    q.front = 0;
    q.rear = 0;
    q.data = malloc(sizeof(int)*size);

    int switchNum, data;
    while(1)
    {
        printf("1 : EnQueue\n2 : DeQueue\n0 : Exit\n : ");
        scanf("%d", &switchNum);
        getchar();
        if(switchNum == 1)
        {
            printf("What Data? : ");
            scanf("%d", &data);
            EnQ(&q, data);
        }
        else if(switchNum == 2)
        {
            if(q.front != q.rear)
                printf("%d dequeued from queue\n\n", DeQ(&q));
        }
        else
        {
            break;
        }
    }

    for(int i=q.front+1 ; i<=q.rear ; i++)
    {
        printf("%4d", q.data[i%size]);
    }

    return 0;
}

 

큐(Queue)는 한쪽 끝(rear)에서 삽입, 그 반대쪽 끝(front)에서 삭제가 일어나는 순서 리스트

선입선출(First In First Out: FIFO) 리스트

( 스택(Stack)은 한쪽 끝(top)에서 모든 삽입, 삭제가 일어나는 순서 리스트 -> 후입선출(LIFO)

덱(Double-Ended Queue: Deque)은 큐의 전단(front), 후단(rear)에서 모두 삽입, 삭제 가능한 순서 리스트 )

단순 배열의 큐를 %size를 이용하여 원형 큐로 변환함

​

더 나아가 큐의 위치 번호인 capacity로, 원소 삽입 시 배열 크기를 동적 할당할 수 있음 (realloc)

1) 크기가 2배 되는 새 배열 newQueue를 생성한다

2) queue[front+1] ~ queue[capacity-1] 사이에 있는 원소들을 newQueue의 0에서부터 복사해 넣는다

3) queue[0] ~ queue[rear] 사이에 있는 원소들을 newQueue의 capacity-front-1에서부터 복사해 넣는다

​

- whitby

 

---

 

다음은 연결리스트를 이용한 큐이다 (Linked List Queue)

 

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct node
{
    int impt;
    int check;
    struct node *next;
}Node;

typedef struct queue
{
    Node *rear;
    Node *front;
}Queue;

Queue queue;

void initQ();
void pushQ(int impt, int check);
void popQ();

int main()
{
    // ~
    
    return 0;
}

void initQ()
{
    queue.front = NULL;
    queue.rear = NULL;
}

void pushQ(int impt, int check)
{
    Node *tempNode = (Node *)malloc(sizeof(Node));
    tempNode->impt = impt;
    tempNode->check = check;
    tempNode->next = NULL;

    if(queue.rear == NULL)
    {
        queue.front = tempNode;
        queue.rear = tempNode;
    }
    else
    {
        queue.rear->next = tempNode;
        queue.rear = tempNode;
    }
}

void popQ()
{
    if(queue.rear != NULL)
    {
        Node *tempNode = (Node *)malloc(sizeof(Node));

        tempNode = queue.front;
        queue.front = queue.front->next;

        free(tempNode);
    }
}