[DataStructure] 큐(Queue) feat. C, Java

자료구조 큐에 대해서 정리를 해보자.

 

큐(Queue)란

큐(Queue)는 컴퓨터 과학에서 사용되는 선형적 자료구조 중 하나이다. 큐는 데이터를 일시적으로 저장하거나 관리하는데 사용되며, 데이터를 먼저 집어넣은 것이 먼저 꺼내지는 "First-In, First-Out"(FIFO) 방식으로 동작한다.

 

큐는 일상생활에서 줄을 서서 기다리는 것과 유사한 개념으로 이해할 수 있다. 가장 먼저 줄을 선 사람이 가장 먼저 서비스를 받는 것과 같이, 큐에 데이터를 추가한 순서대로 데이터가 처리된다.

 

큐의 주요 연산

1. Enqueue : 큐에 데이터를 추가하는 연산이다. 새로운 데이터가 큐의 뒤쪽에 추가된다.
2. Dequeue : 큐에서 데이터를 꺼내는 연산이다. 큐의 맨 앞의 데이터가 삭제되고 반환된다.
3. Front 또는 Peek : 큐의 맨 앞에 있는 데이터를 조회하는 연산이다. 삭제하지 않고 데이터에 접근만 할 수 있다.
4. IsEmpty : 큐가 비어있는지 여부를 확인하는 연산이다. 큐가 비어있을 경우 true를 반환한다.

 

큐의 주요 연산의 시간복잡도

1. Enqueue : 시간복잡도 O(1)이다.
2. Dequeue : 시간복잡도 O(1)이다.
3. Front 또는 Peek : 시간복잡도 O(1)이다.
4. IsEmpty : 시간복잡도 O(1)이다.
5. Search : 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도이다.

 

큐의 활용

큐는 다양한 컴퓨터 애플리케이션에서 활용된다. 예를 들어 컴퓨터 작업들이 처리되는 순서를 관리하고, 프린터 큐는 인쇄 작업들을 관리하는데 사용된다. 또한 네트워크 패킷 처리, 프로세스 스케줄링, 그래프 알고리즘 등 다양한 분야에서 큐가 활용된다. 큐는 스택과 함께 가장 일반적으로 사용되는 자료구조 중 하나이다.

https://ko.wikipedia.org/wiki/%ED%81%90_%28%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0%29

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

큐 with C

큐의 연결리스트 기반 구현

1. ListBaseQueue.h

#ifndef __LB_QUEUE_H__
#define __LB_QUEUE_H__

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node
{
    Data data;
    struct _node *next;

}Node;

typedef struct _lQueue
{
    Node *front;
    Node *rear;

} LQueue;

typedef LQueue Queue;


void QueueInit(Queue *pq);
int QIsEmpty(Queue *pq);

void Enqueue(Queue *pq, Data data);
Data Dequeue(Queue *pq);
Data QPeek(Queue *pq);

#endif

 

2. ListBaseQueue.c

#include <stdio.h>
#include <stdlib.h>
#include "ListBaseQueue.h"

void QueueInit(Queue *pq){
    pq -> front = NULL;
    pq -> rear = NULL;
}

int QIsEmpty(Queue *pq){
    if(pq->front == NULL){
        return TRUE;
    } else{
        return FALSE;
    }
}

void Enqueue(Queue *pq, Data data){
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode -> next = NULL;
    newNode -> data = data;

    if(QIsEmpty(pq)){
        pq -> front = newNode;
        pq -> rear = newNode;
    }
    else{
        pq -> rear -> next = newNode;
        pq -> rear = newNode;
    }

}

Data Dequeue(Queue *pq){
    Node *delNode;
    Data retdata;

    if(QIsEmpty(pq)){
        printf("Queue Memory Error!");
        exit(-1);
    }
    delNode = pq->front;
    retdata = delNode -> data;
    pq -> front = pq -> front -> next; 

    free(delNode);
    return retdata;
}

Data QPeek(Queue *pq){
        if(QIsEmpty(pq)){
        printf("Queue Memory Error!");
        exit(-1);
    }

    return pq->front->data;
}

 

3. ListBaseQueueMain.c

#include<stdio.h>
#include "ListBaseQueue.h"

int main(void){

    //Queue의 생성 및 초기화
    Queue q;
    QueueInit(&q);

    // 데이터 넣기
    Enqueue(&q, 1);
    Enqueue(&q, 2);
    Enqueue(&q, 3);
    Enqueue(&q, 4);
    Enqueue(&q, 5);

    // 데이터 출력
    while(!QIsEmpty(&q)){
        printf("%d ",Dequeue(&q));
    }

    return 0;
}

 

큐 with Java

package ch04_Queue;

import ch04_Stack.IntStack;

public class IntQueue {
    private int[] que; // 큐 배열
    private int capacity; // 큐의 용량
    private int front; // 맨 앞의 요소 커서
    private int rear; // 맨 뒤의 요소 커서
    private int num; // 현재 데이터 갯수

    // 실행 시 예외 : 큐가 비어 있음
    public class EmptyIntQueueException extends RuntimeException {
        public EmptyIntQueueException() {
        }
    }

    // 실행 시 예외 : 큐가 가득 참
    public class OverflowIntQueueException extends RuntimeException {
        public OverflowIntQueueException() {
        }
    }

    // 생성자
    public IntQueue(int maxlen) {
        num = front = rear = 0;
        capacity = maxlen;
        try {
            que = new int[capacity];
        } catch (OutOfMemoryError e) {
            capacity = 0;
        }
    }

    // 큐에 데이터를 인큐
    public int enque(int x) throws OverflowIntQueueException {
        if (num >= capacity)
            throw new OverflowIntQueueException();
        que[rear++] = x;
        num++;
        if (rear == capacity)
            rear = 0;
        return x;
    }

    // 큐에서 데이터를 데큐
    public int deque() throws EmptyIntQueueException {
        if (num <= 0)
            throw new EmptyIntQueueException();
        int x = que[front++];
        num--;
        if (front == capacity)
            front = 0;
        return x;
    }

    // 큐에서 데이터를 피크(프런트 데이터를 들여다 봄)
    public int peek() throws EmptyIntQueueException {
        if (num <= 0)
            throw new EmptyIntQueueException();
        return que[front];
    }

    // 큐를 비움
    public void clear() {
        num = front = rear = 0;
    }

    // 큐에서 x를 검색하여 인데스(찾지 못하면 -1)를 반환
    public int indexOf(int x) {
        for (int i = 0; i < num; i++) {
            int idx = (i + front) % capacity;
            if (que[idx] == x) {
                return idx;
            }
        }
        return -1;
    }

    // 큐의 용량을 반환
    public int getCapacity() {
        return capacity;
    }

    // 큐에 쌓아 있는 데이터 개수를 반환
    public int size() {
        return num;
    }

    // 큐가 비어 있나요?
    public boolean isEmpty() {
        return num <= 0;
    }

    // 큐가 가득 찼나요?
    public boolean isFull() {
        return num >= capacity;
    }

    // 큐 안의 모든 데이터를 프런트 -> 리어 순으로 출력
    public void dump() {
        if (num <= 0) {
            System.out.println("큐가 비어 있습니다.");
        } else {
            for (int i = 0; i < num; i++) {
                System.out.println(que[(i + front) % capacity] + " ");
            }
            System.out.println();
        }
    }

}

 

참고

열혈 자료구조

Do it! 자료구조와 함께 배우는 알고리즘 입문 자바편