알고리즘 기초 5 - [자료구조, 큐]

Queue

목차

LIFO(Last Input First Out)이 아닌 FIFO(First In First Out)

 

• Put : 데이터가 도착하는 순대로 저장된다.
• Get : 처음 저장된 데이터부터 차례대로 사용된다.

 

배열을 사용한 큐의 구현

C

#include <stdio.h>

#define MAX 100

// Queue
int Queue[MAX];
int Front, Rear;

void InitializeQueue(void); // 큐 초기화 함수
void Put(int); // 데이터 삽입
void Get(void); // 데이터 삭제
void DisplayQueue(void); // 큐를 보여줌

void InitializeQueue(void) {
    Front = Rear = 0;
}

void Put(int num) {
    Queue[Rear++] = num;

    if(Rear >= Max)
        Rear = 0;
}

int Get(void) {
    int ret;
    ret = Queue[Front++];

    if(Front >= Max)
        Front = 0;

    return ret;
}

void DisplayQueue(void) {
    int i = 0;
    printf("Front -> ");

    for(i = Front; i < Rear; i++)
        printf("%2d -> ", Queue[i]);

    printf("Rear");
}

void main() {
    int ret;
    InitalizeQueue();

    Put(1);
    Put(3);
    Put(10);
    Put(20);
    Put(12);

    printf("다섯 번의 Put() 함수 호출 후 결과\n");
    DisplayQueue();

    ret = Get();
    ret = Get();
    ret = Get();

    printf("\n 세 번의 Get() 함수 호출 후 결과\n");
    DisplayQueue();

    printf("\n 두 번의 Get() 함수 호출 후 결과\n");
    ret = Get();
    ret = Get();
    DisplayQueue();
}

// 결과
// 다섯 번의 Put() 함수 호출 후 결과
// Front -> 1 -> 3 -> 10 -> 20 -> 12 -> Rear
// 세 번의 Get() 함수 호출 후 결과
// Front -> 20 -> 12 -> Rear
// 두 번의 Get() 함수 호출 후 결과
// Front -> End

---

 

---

Java

class  Queue {
        public  static  final  int  MAX = 100;
        public  static  int[] queue = new  int[MAX];
        public  static  int  front, rear;
        public  static  void  initializeQueue() {
        front = rear = 0;
    }

    public  static  void  put(int  data) {
        queue[rear++] = data;
        if(rear >= MAX)
        rear = 0;
    }


    public  static  int  get() {
        int  ret = -1;
        ret = queue[front++];
        if(front >= MAX)
        front = 0;
        return  ret;
    }


    public  static  void  displayQueue() {
        int  i = 0;
        String  str = "front ->";
        for(i=front; i<rear; i++) {
            str += String.format(" %d -> ", queue[i]);
        }

        str += " rear";
        System.out.println(str);
    }

    public  static  void  main(String[] args) {
        int  ret = -1;
        initializeQueue();

        put(1);
        put(3);
        put(10);
        put(20);
        put(12);



        displayQueue();

        ret = get();
        ret = get();
        ret = get();

        displayQueue();

        ret = get();
        ret = get();
        displayQueue();
    }
}
// 결과
// front -> 1 ->  3 ->  10 ->  20 ->  12 ->  rear
// front -> 20 ->  12 ->  rear
// front -> rear

---

 

---

JavaScript

const  MAX = 100;
let  queue = new  Array(MAX);
let  front, rear;

const  initializeQueue = () => {
    front = rear = 0;
}



const  put = (data) => {
    queue[rear++] = data;
    if(rear >= MAX)
    rear = 0;
}

const  get = () =>{
    let  ret = -1;
    ret = queue[front++];
    if(front >= MAX)
        front = 0;

    return  ret;
}

const  displayQueue = () => {
    let  i = 0;
    let  str = "front ->";
    for(i=front; i<rear; i++) {
        str += ` ${queue[i]} -> `;
    }

    str += " rear";
    console.log(str);
}

const  main = () => {
    let  ret = -1;
    initializeQueue();
    put(1);
    put(3);
    put(10);
    put(20);
    put(12);
    displayQueue();

    ret = get();
    ret = get();
    ret = get();
    displayQueue();

    ret = get();
    ret = get();
    displayQueue();
}

main();
// 결과
// front -> 1 ->  3 ->  10 ->  20 ->  12 ->  rear
// front -> 20 ->  12 ->  rear
// front -> rear

---

 

링크드 리스트를 이용한 큐의 구현

---

C

#include <stdio.h>

typedef struct _NODE {
    int Data;
    struct _NODE *Next;
} NODE;

NODE *Front, *Rear, *ptrNode;

void InitializeQueue(void)
void Put(int data);
int Get(void);
void DisplayQueue(void);

void InitializeQueue(void) {
    Front = (NODE *)malloc(sizeof(NODE));
    Rear = (NODE *)malloc(sizeof(NODE));

    Front->Next = Rear;
    Rear->Next = Front;
}

void Put(int data) {
    ptrNode = (NODE *)malloc(sizeof(NODE));
    ptrNode.Data = data;

    if(Front->Next == Rear) {
        Front->Next = ptrNode;
        ptrNode->Next = Rear;
        Rear->Next = ptrNode;
    } else {
        Rear->Next->Next = ptrNode;
        ptrNode->Next = Rear;
        Rear->Next = ptrNode;
    }
}

int Get(void) {
    int ret;
    NODE *deleteNode;

    printf("\n");
    if(Front->Next == Rear)
        printf("Queue Empty\n");
    else {
        deleteNode = Front->Next;
        Front->Next = deleteNode->Next;
        ret = deleteNode->Data;
        printf("get() : %d", ret);

        free(deleteNode);    
    }

    return ret;
}

void DisplayQueue(void) {
    NODE *ptrTemp;

    if(Front->Next != Rear) {
        for(ptrTemp = Front->Next; ptrTemp->Next != Rear; ptrTemp = ptrTemp->Next) {
            printf("%d -> ", ptrTemp->Data);
        }
        printf("%d\n", ptrTemp->Data);
    }
    else if(Front->Next == Rear)
        printf("Queue Empty\n");
}

void main() {
    int ret;
    InitalizeQueue();

    Put(1);
    Put(3);
    Put(10);
    Put(20);
    Put(12);

    DisplayQueue();

    ret = Get();
    ret = Get();
    ret = Get();

    DisplayQueue();

    ret = Get();
    ret = Get();

    DisplayQueue();
}

// 결과
// 1 -> 3 -> 10 -> 20 -> 12
// get() : 1
// get() : 3
// get() : 10
// 20 -> 12
// get() : 20
// get() : 12
// Queue Empty

---

 

---

Java

public  class  QueueWithLinkedList {

    static  class  Node {
        int  data;
        Node  next;

        public  Node(int  data) {
            this.data = data;
            this.next = null;
        }
    }

    static  Node  front, rear, ptrNode;

    public  static  void  initQueue () {
        front = new  Node(-1);
        rear = new  Node(-1);
        front.next = rear;
        rear.next = front;
    }

    public  static  void  put(int  data) {
        ptrNode = new  Node(data);

        if(front.next == rear) {
            front.next = ptrNode;
            ptrNode.next = rear;
            rear.next = ptrNode;

        } else {
            rear.next.next = ptrNode;
            ptrNode.next = rear;
            rear.next = ptrNode;

        }

    }

    public  static  int  get () {
        int  ret = -1;
        if(front.next == rear) {
            System.out.println("Queue empty");
        } else {
            ret = front.next.data;
            front.next = front.next.next;
            System.out.println("get() : " + ret);

        }

        return  ret;
    }

    public  static  void  displayQueue() {
        Node  ptrTemp;
        String  str = "";

        if(front.next != rear) {
            for(ptrTemp = front.next; ptrTemp.next != rear; ptrTemp = ptrTemp.next) {
            str += String.format("%d -> ", ptrTemp.data);
        }
            str += ptrTemp.data;
            System.out.println(str);

        } else  if(front.next == rear) {
            System.out.println("Queue empty");

        }
    }

    public  static  void  main(String[] args) {
        int  ret;
        initQueue();
        put(1);
        put(3);
        put(10);
        put(20);
        put(12);

        displayQueue();
        ret = get();
        ret = get();
        ret = get();

        displayQueue();

        ret = get();
        ret = get();

        displayQueue();

    }

}
// 결과
// 1 -> 3 -> 10 -> 20 -> 12
// get() : 1
// get() : 3
// get() : 10
// 20 -> 12
// get() : 20
// get() : 12
// Queue empty

---

 

---

JavaScript

class  Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}


let  front, rear, ptrNode; 

const  initQueue = () => {
    front = new  Node(-1);
    rear = new  Node(-1);

    front.next = rear;
    rear.next = front;
}



const  put = (data) => {
    ptrNode = new  Node(data);

    if(front.next === rear) {
        front.next = ptrNode;
        ptrNode.next = rear;
        rear.next = ptrNode;
    } else {
        rear.next.next = ptrNode;
        ptrNode.next = rear;
        rear.next = ptrNode;
    }

}



const  get = () => {
    let  ret = -1;

    if(front.next === rear) {
        console.log("Queue empty");

    } else {
        ret = front.next.data;
        front.next = front.next.next;
        console.log("get() : " + ret);
    }
    return  ret;
}



const  displayQueue = () => {
    let  ptrTemp;
    let  str = "";


    if(front.next !== rear) {
        for(ptrTemp = front.next; ptrTemp.next != rear; ptrTemp = ptrTemp.next) {
            str += `${ptrTemp.data} -> `;
        }

        str += `${ptrTemp.data}`;
        console.log(str);
    }

    else  if(front.next === rear) {
        console.log("Queue empty");
    }

}



const  main = () => {
    let  ret;

    initQueue();
    put(1);
    put(3);
    put(10);
    put(20);
    put(12);

    displayQueue();

    ret = get();
    ret = get();
    ret = get();

    displayQueue();

    ret = get();
    ret = get()'

    displayQueue();
}
main();

// 결과
// 1 -> 3 -> 10 -> 20 -> 12
// get() : 1
// get() : 3
// get() : 10
// 20 -> 12
// get() : 20
// get() : 12
// Queue empty

---