[자료구조]큐(Queue)

큐란

선입 선출(First-In First-Out) 형태의 자료 구조.

큐는 먼저 들어간 데이터가 먼저 나오는 자료 구조.

버퍼의 역할로 입력 데이터가 폭주 할 때 임시로 줄을 세워 모아두었다가 내보내는 구조.

삽입과 제거가 주요입니다.

스택과 같은 삽입과 제거의 용어가 헷갈리지 않도록 구분합니다.

스택은 push, pop입니다.

큐는 enqueue, dequeue 입니다. 

큐는 순환(배열)과 링크드 리스트로 구현 할 수 있습니다.

순환 큐와 링크드 큐의 성능 비교

 순환 큐는 동적 할당을 하지 않아 성능 측에서 우수합니다.

큐의 크기를 예측 할 수 있고 고성능이 필요한 버퍼가 필요한 상황이라면 순환 큐가 적절합니다.

큐의 기본 구조

데이터 삽입 과정

데이터 제거 과정

순환(배열) 큐에서 주의 할 점

순환 큐는 전단과 후단이 정해진 크기에서 인덱스를 이동하는 방법입니다.

제거시 전단이 1칸 뒤로 이동합니다.

ex) 화살표(↑)는 전단입니다.

크기 4

1 2 3 4    |    ㅁ 2 3 4     |    ㅁ ㅁ 3 4    |    ㅁ ㅁ ㅁ 4    |    ㅁ ㅁ ㅁ ㅁ

↑                   ↑                     ↑                       ↑          ↑

위에가 안보인다면 아래 사진 보세요.

- 정해진 크기를 전단이 넘어섯을 경우 다시 0인덱스로 갑니다.

- 후단과 만났을 경우 공백 상태입니다.(위의 예시에서 4번째의 4를 가르킬 때 후단과 만납니다.)

추가시 후단이 1칸 뒤로 이동합니다.

ex) 화살표(↑)는 후단입니다.

크기 4

ㅁ ㅁ ㅁ ㅁ    |   1 ㅁ ㅁ ㅁ    |    1 2 ㅁ ㅁ   |    1 2 3 ㅁ    |    1 2 3 4 

↑                      ↑                      ↑                   ↑          ↑         

위에가 안보인다면 아래 사진 보세요.

- 정해진 크기를 후단이 넘어섯을 경우 다시 0인덱스로 갑니다.

- 전단과 만났을 경우 포화 상태입니다.(위 예시에서 5번째의 1을 가르킬때 전단과 만납니다.)

공백 상태와 포화 상태를 확인하는 방법이 전단과 후단이 만났을 때라는 전제가 중복됩니다.

이를 해결 하기 위해 후단의 뒷 부분에 빈 공간을 만들어 둡니다.

ex) 

크기 5

ㅁ ㅁ ㅁ ㅁ ■    |   1 ㅁ ㅁ ㅁ ■   |    1 2 ㅁ ㅁ ■  |    1 2 3 ㅁ ■   |    1 2 3 4 ■

후단     ↑                         ↑                       ↑                     ↑                   ↑        

전단     ↑                      ↑                      ↑                  ↑                ↑       

위에가 안보인다면 아래 사진 보세요.

빈 공간으로 인해 공백 상태와 포화 상태를 구분 할 수 있습니다.

공백 상태는 전단과 후단이 만났을 경우

포화 상태는 두 가지로 구분 할 수 있습니다.

후단 인덱스가 전단 인덱스보다 클경우 : 후단 인덱스 - 전단 인덱스가 크기와 같을 때 -> 5-0 = 5

후단 인덱스가 전단 인덱스보다 작을 경우 : 후단의 다음 인덱스가 전단인 경우 -> 후단이 2이고 전단이 3

C 소스

순환(배열) 큐

CircularQueue.h

/*

* CircularQueue.h

*

* Created on: 2019. 1. 2.

* Author: otrodevym

*/

#ifndef CIRCULARQUEUE_H_

#define CIRCULARQUEUE_H_

#include <stdio.h>

#include <stdlib.h>

typedef int ElementType;

typedef struct tagNode{

    ElementType Data;

} Node;

typedef struct tagCircularQueue{

    int Capacity;

    int Front;

    int Rear;

    Node* Nodes;

}CircularQueue;

void CQ_CreateQueue(CircularQueue** Queue, int Capacity);

void CQ_DestroyQueue(CircularQueue* Queue);

void CQ_Enqueue(CircularQueue* Queue, ElementType Data);

ElementType CQ_Dequeue(CircularQueue* Queue);

int CQ_GetSize(CircularQueue* Queue);

int CQ_IsEmpty(CircularQueue* Queue);

int CQ_IsFull(CircularQueue* Queue);

#endif /* 3_1_CIRCULAR_QUEUE_CIRCULARQUEUE_H_ */

CircularQueue.c

/*

* CircularQueue.c

*

* Created on: 2019. 1. 2.

* Author: otrodevym

*/

#include "CircularQueue.h"

void CQ_CreateQueue(CircularQueue** Queue, int Capacity){

    (*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));

    (*Queue)->Nodes = (Node*) malloc(sizeof(Node) * (Capacity+1));

    (*Queue)->Capacity = Capacity;

    (*Queue)->Front = 0;

    (*Queue)->Rear = 0;

}

void CQ_DestroyQueue(CircularQueue* Queue){

    free(Queue->Nodes);

    free(Queue);

}

void CQ_Enqueue(CircularQueue* Queue, ElementType Data){

    int Position = 0;

    if(Queue->Rear == Queue->Capacity){

        Position = Queue->Rear;

        Queue->Rear = 0;

    }else{

        Position = Queue->Rear++;

    }

    Queue->Nodes[Position].Data = Data;

}

ElementType CQ_Dequeue(CircularQueue* Queue){

    int Position = Queue->Front;

    if(Queue->Front == Queue->Capacity){

        Queue->Front = 0;

    }else{

        Queue->Front++;

    }

    return Queue->Nodes[Position].Data;

}

int CQ_GetSize(CircularQueue* Queue){

    if(Queue->Front <= Queue->Rear){

        return Queue->Rear - Queue->Front;

    }else{

        return Queue->Rear + (Queue->Capacity - Queue->Front)+1;

    }

}

int CQ_IsEmpty(CircularQueue* Queue){

    return (Queue->Front == Queue->Rear);

}

int CQ_IsFull(CircularQueue* Queue){

    if(Queue->Front < Queue->Rear){

        return (Queue->Rear - Queue->Front) == Queue->Capacity;

    }else{

        return (Queue->Rear+1 )== Queue->Front;

    }

}

main.c

/*

* CircularQueueMain.c

*

* Created on: 2019. 1. 2.

* Author: otrodevym

*/

#include "CircularQueue.h"

int CircularQueueMain(){

    int i = 0;

    CircularQueue* Queue;

    CQ_CreateQueue(&Queue, 10);

    CQ_Enqueue(Queue, 1);

    CQ_Enqueue(Queue, 2);

    CQ_Enqueue(Queue, 3);

    CQ_Enqueue(Queue, 4);

    for(i = 0; i < 3; i++){

        printf("Dequeue : %d, ", CQ_Dequeue(Queue));

        printf("Front : %d, Rear : %d \n", Queue->Front, Queue->Rear );

    }

    i = 100;

    while(CQ_IsFull(Queue) == 0 ){

        CQ_Enqueue(Queue, i++);

    }

    printf("Capacity : %d, Size : %d \n\n", Queue->Capacity, CQ_GetSize(Queue));

    while(CQ_IsEmpty(Queue) == 0){

        printf("Dequeue : %d, ", CQ_Dequeue(Queue));

        printf("Front : %d, Rear : %d \n\n", Queue->Front, Queue->Rear);

    }

    CQ_DestroyQueue(Queue);

}

링크드 큐

LinkedQueue.h

/*

* LinkedQueue.h

*

* Created on: 2019. 1. 2.

* Author: otrodevym

*/

#ifndef LINKEDQUEUE_H_

#define LINKEDQUEUE_H_

#define NULL <void *>0

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct tagNode{

    char* Data;

    struct tagNode* NextNode;

} Node;

typedef struct LinkedQueue{

    Node* Front;

    Node* Rear;

    int Count;

} LinkedQueue;

void LQ_CreateQueue(LinkedQueue** Queue);

void LQ_DestroyQueue(LinkedQueue* Queue);

Node* LQ_CreateNode(char* NewData);

void LQ_DestroyNode(Node* _Node);

void LQ_Enqueue(LinkedQueue* Queue, Node* NewData);

Node* LQ_Dequeue(LinkedQueue* Queue);

int LQ_IsEmpty(LinkedQueue* Queue);

#endif /* 3_2_LINKED_QUEUE_LINKEDLIST_H_ */

LinkedQueue.c

/*

* LinkedQueue.c

*

* Created on: 2019. 1. 2.

* Author: otrodevym

*/

#include "LinkedQueue.h"

void LQ_CreateQueue(LinkedQueue** Queue){

    (*Queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue));

    (*Queue)->Front = NULL;

    (*Queue)->Rear = NULL;

    (*Queue)->Count = 0;

}

void LQ_DestroyQueue(LinkedQueue* Queue){

    while(!LQ_IsEmpty(Queue)){

        Node* Popped = LQ_Dequeue(Queue);

        LQ_DestroyNode(Popped);

    }

    free(Queue);

}

Node* LQ_CreateNode(char* NewData){

    Node* NewNode = (Node*)malloc(sizeof(Node));

    NewNode->Data = (char*)malloc(strlen(NewData)+1);

    strcpy(NewNode->Data, NewData);

    NewNode->NextNode = NULL;

    return NewNode;

}

void LQ_DestroyNode(Node* _Node){

    free(_Node->Data);

    free(_Node);

}

void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode){

    if(Queue->Front == NULL){

        Queue->Front = NewNode;

        Queue->Rear = NewNode;

        Queue->Count++;

    }else{

        Queue->Rear->NextNode = NewNode;

        Queue->Rear = NewNode;

        Queue->Count++;

    }

}

Node* LQ_Dequeue(LinkedQueue* Queue){

    Node* Front = Queue->Front;

    if(Queue->Front->NextNode == NULL){

        Queue->Front = NULL;

        Queue->Rear = NULL;

    }else{

        Queue->Front = Queue->Front->NextNode;

    }

    Queue->Count--;

    return Front;

}

int LQ_IsEmpty(LinkedQueue* Queue){

    return (Queue->Front == NULL);

}

main.c

/*

* LinkedQueueMain.c

*

* Created on: 2019. 1. 2.

* Author: otrodevym

*/

#include "LinkedQueue.h"

int main(){

    Node* Popped;

    LinkedQueue* Queue;

    LQ_CreateQueue(&Queue);

    LQ_Enqueue(Queue, LQ_CreateNode("abc"));

    LQ_Enqueue(Queue, LQ_CreateNode("def"));

    LQ_Enqueue(Queue, LQ_CreateNode("efg"));

    LQ_Enqueue(Queue, LQ_CreateNode("hij"));

    printf("Queue Size : %d \n ", Queue->Count);

    while(LQ_IsEmpty(Queue) == 0){

        Popped = LQ_Dequeue(Queue);

        printf("Dequeue : %s \n", Popped->Data);

        LQ_DestroyNode(Popped);

    }

    LQ_DestroyQueue(Queue);

    return 0;

}

Java 소스

순환(배열) 큐

CircularQueue.java

package c_queue;

public class CircularQueue<T> {

    private Node<T>[] Nodes;

    private int size;

    int front;

    int rear;

    

    public CircularQueue(int size) {

        this.Nodes = new Node[size];

        this.size = size;

        this.front = -1;

        this.rear = -1;

        

    }

    

    class Node<T>{

        T value;

        

        public Node() {

            

        }

        

        public Node(T value) {

            this.value = value;

        }

    }

    

    

    private void enQueue(T value) {

        Node<T> newNode = new Node<T>(value);

        if(this.rear == -1) {

            this.rear++;

            Nodes[this.rear] = newNode;

        }else {

            if((this.rear+1) == this.size) {

                this.rear = 0 ;

            }else {

                this.rear++;

            }

            Nodes[this.rear] = newNode;

        }

    }

    

    

    private T deQueue() {

        if((this.front+1) == this.size) {

            this.front = 0;

        }else {

            this.front++;

        }       

        T data =Nodes[this.front].value;

        Nodes[this.front] = null;

        return data;

    }

    

    private boolean isEmpty() {

        if(this.front == this.rear) {

            return true;

        }else {

            return false;

        }

    }

    

    private boolean isFull() {

        if(this.front < this.rear) {

            return (this.rear - this.front) == this.size;

        }else {

            return this.size == (this.rear) + ((this.size - this.front)+1);

        }

    }

    

    public static void main(String args[]) {

        int size = 10;

        CircularQueue<String> list = new CircularQueue<String>(size);

        list.enQueue("1");

        list.enQueue("2");

        list.enQueue("3");

        System.out.println("--------------------------");

        System.out.println(list.rear);

        System.out.println("--------------------------");

        System.out.println(list.deQueue());

        System.out.println(list.deQueue());

        System.out.println(list.deQueue());

        System.out.println("--------------------------");

        if(!list.isEmpty()) {

            System.out.println(list.front);

            System.out.println(list.rear);

            System.out.println(list.deQueue());

        }

        

        while(!list.isFull()) {

            list.enQueue("3");

        }

        

        while(!list.isEmpty()) {

            System.out.println(list.deQueue());

        }

    }  

}

링크드 큐

LinkedQueue.java

package c_queue;

public class LinkedQueue<T> {

    private Node front;

    private Node rear;

    private int size;

    

    public LinkedQueue() {

        this.front = null;

        this.rear = null;

        this.size = 0;

    }

    

    class Node {

        private T value;

        private Node nextNode;

        

        public Node(T value) {

            this.value = value;

            this.nextNode = null;

        }

    }

    

    private void enQueue(T newValue) {

        Node newNode = new Node(newValue);

        if(this.rear == null) {

            this.front = newNode;

            this.rear = newNode;

        }else {

            this.rear.nextNode = newNode;

            this.rear = newNode;

        }

    }

    

    private T deQueue() {

        T data =this.front.value;

        this.front = this.front.nextNode;

        return data;

    }

    

    private boolean isEmpty() {

        return (this.front == null);

    }

    

    public static void main(String args[]) {

        LinkedQueue<String> list = new LinkedQueue<>();

        

        list.enQueue("1");

        list.enQueue("2");

        list.enQueue("3");

        list.enQueue("4");

        list.enQueue("5");

        

        

        System.out.println(list.deQueue());

        System.out.println(list.deQueue());

        System.out.println(list.deQueue());

        

        while(!list.isEmpty()) {

            System.out.println(list.deQueue());

        }

    }

}