4. 큐(Queue)

정의

한쪽 끝에서 자료를 넣으면 다른 한쪽 끝에서 자료를 뺄 수 있는구조로 쉽게 말해서 먼저들어온 데이터가 먼저 나오는 구조라고해서 FIFO(First In First Out)라고 부른다.

예를 들어 enqueue(A), enqueue(B), dequeue()를 순서대로 실행하면 A가 나오고 B가 남는다. 이 순서를 유지하는 것이 큐의 불변식이다. 작업 요청, 이벤트, 그래프의 너비 우선 탐색처럼 도착한 순서대로 처리할 때 쓴다. 가장 나중에 넣은 것을 먼저 꺼내야 한다면 스택이 맞다.

<그림1. 큐>

                                                                           <그림1. 큐>

큐의 연산

• enqueue : 데이터를 큐에 삽입

• dequeue : 제일 첫 번째 들어온 데이터를 제거

• 큐의 전단은 front, 후단은 rear로 이루어짐

• 새로운 데이터가 들어오면 rear가 하나씩 증가

• 데이터를 빼내면 front가 다음 queue에 저장되어 있는 데이터를 가리킴

enqueue

void enqueue(Object[] queue, int data) {
    if (rear == queue.length) throw new IllegalStateException("공간이 없습니다");
    queue[rear++] = data;
}

이 단순 배열 예제에서는 rear가 다음 삽입 위치다. 삽입 후 한 칸 증가하며, 앞에서 이미 꺼낸 칸을 재사용하지 않는다. 아래에서 원형 큐로 바꿀 이유가 여기에 있다.

dequeue

Object dequeue(Object[] queue) {
    if (front == rear) throw new IllegalStateException("큐가 비었습니다");
    Object value = queue[front];
    queue[front++] = null;
    return value;
}

기존 예제는 data를 배열에 다시 쓰고 반환값이 없어 dequeue가 아니었다. 제거에서는 먼저 front 위치의 값을 읽고 참조를 지운 뒤 위치를 옮긴다. front == rear가 빈 상태라는 것은 이 선형 큐에만 적용된다.

배열에서 단순 큐의 문제점

• 배열에서 큐가 차면 데이터를 빼내야 하고, front 앞의 배열에는 공백이 생긴다(가용용량이 줄어들어버림). 또 다른경우 데이터를 빼낼 때 기존 데이터를 배열의 첫 번 째 위치로 이동해야하는 연산이 생길 수 있다.

• 이런 문제를 해결하기 위해 Circular Queue 를 활용한다.

길이 5 배열에 A, B, C를 넣고 A와 B를 꺼내면 앞의 두 칸이 빈다. 선형 구현의 rear는 여전히 3이라 두 번 더 넣으면 끝에 도달한다. 데이터를 매번 앞으로 옮기면 한 번의 제거가 O(n)이 된다. 인덱스를 배열 길이로 나눈 나머지로 순환시키면 빈 칸을 재사용하면서 삽입·제거를 O(1)로 유지할 수 있다.

원형 큐(Circular Queue)

• 배열의 끝(rear)과 시작(front)부분을 이어 순환시키도록 하는 것.

• 배열의 rear에 데이터를 삽입하면서 rear의 다음이 front와 만나면 배열이 꽉차게 됨.

아래 C 구현은 실제 요청 용량 capacity보다 한 칸 더 할당한다. front는 다음에 꺼낼 위치, rear는 다음에 넣을 위치다. 두 값이 같으면 비었고 (rear+1) % (capacity+1) == front이면 가득 찼다. 한 칸을 비워 두므로 두 상태를 구분할 수 있다. Java 구현은 별도의 length 필드를 사용하므로 배열의 모든 칸을 활용한다.

flowchart LR
  A[front: 다음 제거 칸] --> B[값을 읽고 front를 한 칸 순환]
  C[rear: 다음 삽입 칸] --> D[값을 쓰고 rear를 한 칸 순환]
  E[인덱스가 끝에 닿음] --> F[0으로 돌아감]

다음 그림과 코드에서 같은 위치에 다시 도착해도 이전 값이 남아 있다는 뜻은 아니다. 현재 요소 수나 빈 칸 규칙을 함께 확인해야 한다.

<그림2. 원형 큐(Circular Queue) >

                                             <그림2. 원형 큐(Circular Qeueue) >

CircularQueue.c

#include "CircularQueue.h"

void createQueue(Queue **queue, int capacity) {
    if (capacity < 1) exit(1);
    (*queue) = (Queue*)malloc(sizeof(Queue));
    (*queue)->capacity = capacity;
    (*queue)->front = 0;
    (*queue)->rear = 0;
    (*queue)->nodes = (Node*)malloc(sizeof(Node)* (capacity+1));
}
void enqueue(Queue *queue, element data) {
    if (isFull(queue)) exit(1);
    queue->nodes[queue->rear].data = data;
    queue->rear = (queue->rear + 1) % (queue->capacity + 1);
}
element dequeue(Queue *queue) {
    if (isEmpty(queue)) exit(1);
    element value = queue->nodes[queue->front].data;
    queue->front = (queue->front + 1) % (queue->capacity + 1);
    return value;
}
int isEmpty(Queue *queue) {
    if (queue->front == queue->rear) {
        return TRUE;
    }
    return FALSE;
}
int isFull(Queue *queue) {
    return (queue->rear + 1) % (queue->capacity + 1) == queue->front;
}

CircularQueue.h

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


#ifndef CIRCULARQUEUE_H
#define CIRCULARQUEUE_H

#define TRUE 1
#define FALSE 0

typedef int element;
typedef struct _Node {
    element data;
}Node;

typedef struct _Queue {
    int capacity;
    int front;
    int rear;
    Node* nodes;
}Queue;

void createQueue(Queue **queue, int capacity);
void enqueue(Queue *queue, element data);
element dequeue(Queue *queue);
int isEmpty(Queue *queue);
int isFull(Queue *queue);

#endif //CIRCULARQUEUE_H

용량이 3이면 내부 배열은 4칸이다. A·B·C를 넣으면 front=0, rear=3이고, 다음 삽입은 (3+1)%4 == 0이므로 가득 찼다. A를 꺼내 front=1로 옮긴 뒤 D를 넣으면 인덱스 3에 쓰고 rear=0으로 순환한다. 데이터의 논리적 순서는 B·C·D다. 이 예제의 dequeue는 제거한 값을 반환하도록 수정했다. 원래 C 코드는 서로 다른 모듈로 나눈 나머지를 사용하고 isFull 괄호가 닫히지 않아 컴파일도 되지 않았다. C에서는 사용을 마친 nodes와 큐 구조체를 해제하는 함수도 별도로 구현해야 한다.

ArrayList Queue java version

아래 Java 배열 큐는 length를 별도로 저장한다. 그래서 front == rear가 빈 경우와 꽉 찬 경우 둘 다 가능하며 이 조건만으로 비었는지 판단할 수 없다. length == 0이면 비었고 length == capacity이면 가득 찼다. enqueue와 dequeue는 인덱스를 나머지 연산으로 움직이고, toString은 물리적 배열 인덱스 0부터가 아니라 front부터 length개를 읽어야 FIFO 순서가 나온다.

Queue.java

public interface Queue<T> {
    public void enqueue(T t);
    public T dequeue();
    public boolean isFull();
    public boolean isEmpty();
}

ArrayQueue.java

public class ArrayQueue<T> implements Queue<T> {

	private Object[] queue;
	private int front;
	private int rear;
	private int capacity;
	private int length;
	private static final int DEFAULT_CAPACITY = 5;

	public ArrayQueue() {
		this.capacity = DEFAULT_CAPACITY;
		this.front = 0;
		this.rear = 0;
		this.length  = 0;
		this.queue = new Object[capacity];
	}
	public ArrayQueue(int capacity) {
		if (capacity < 1) throw new IllegalArgumentException("capacity must be positive");
		this.capacity = capacity;
		this.front = 0;
		this.rear = 0;
		this.length = 0;
		this.queue = new Object[capacity];
	}

	@Override
	public void enqueue(T data) {
		if (isFull()) {
			throw new IndexOutOfBoundsException("queue is Full...");
		}
		queue[this.rear] = data;
		this.rear = (this.rear + 1) % this.capacity;
		this.length++;
	}

	@Override
	public T dequeue() {
		if (isEmpty()) {
			throw new IndexOutOfBoundsException("queue is empty...");
		}
		Object data = queue[this.front];
		queue[this.front] = null;
		this.front = (this.front + 1) % this.capacity;
		this.length--;
		return (T)data;
	}

	@Override
	public boolean isFull() {
		if (length == capacity) {
			return true;
		}
		return false;
	}

	@Override
	public boolean isEmpty() {

		if (length == 0) {
			return true;
		}
		return false;
	}

	@Override
	public String toString() {
		if (length == 0) {
			return "[ ]";
		} else {
			StringBuilder sb = new StringBuilder("[");
			for(int i =0; i<length; i++) {
				sb.append(queue[(front + i) % capacity]);
				if (i != length-1) {
					sb.append(", ");
				}
			}
			sb.append("]");
			return sb.toString();
		}
	}

}

연결리스트 큐 (LinkedList Queue)

배열 큐는 노드 할당이 없고 공간이 연속되어 있지만 고정 용량을 정해야 한다. 연결 큐는 front와 rear 참조만 유지하면 둘 다 O(1)에 처리할 수 있으며 용량을 미리 정할 필요가 없다. 노드마다 다음 노드를 가리키는 참조가 추가로 든다.

• 연결리스트 큐를 이용하면 용량상태를 확인할 필요가 없으며 용량의 제한이 없어서 가득찬다는 개념이 존재하지 않음

• front에서 데이터를 빼낼 때 next Node를 연결 해제 해주면 되므로 삽입 삭제가 편리

LinkedQueue.h

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

#ifndef LINKQUEUE_H
#define LINKQUEUE_H

#define TRUE 1
#define FALSE 0

typedef int element;
typedef struct _Node {
    element data;
    struct _Node* next;
}Node;

typedef struct _Queue {
    Node* front;
    Node* rear;
    int count;
}LinkedQueue;

Node *createNode(element data);
void createQueue(LinkedQueue **queue);
void enqueue(LinkedQueue *queue, Node* newNode);
void dequeue(LinkedQueue *queue);
int isEmpty(LinkedQueue *queue);

#endif //LINKQUEUE_H

LinkQueue.c

#include "LinkQueue.h"

void createQueue(LinkedQueue **queue) {
    (*queue) = (LinkedQueue*)malloc((sizeof(LinkedQueue)));
    (*queue)->front = NULL;
    (*queue)->rear = NULL;
    (*queue)->count = 0;
}
Node *createNode(element data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
void enqueue(LinkedQueue *queue, Node* newNode) {
    if (queue->front == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
        queue->count++;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
        queue->count++;
    }
}
void dequeue(LinkedQueue *queue) {
    if (isEmpty(queue)) exit(1);
    Node* front = queue->front;
    if (queue->front->next == NULL) {
        queue->front = NULL;
        queue->rear = NULL;
    } else {
        queue->front =queue->front->next;
    }
    queue->count--;
    free(front);
}
int isEmpty(LinkedQueue *queue) {
    if (queue->count == 0) {
        return TRUE;
    }
    return FALSE;
}

C 버전은 createNode가 만든 노드를 enqueue에 넘긴다. 원래 createNode에는 return이 없어 호출자가 유효한 포인터를 받지 못했고, dequeue는 제거 노드를 해제하지 않았다. 빈 큐에서 front->next를 읽으면 잘못된 메모리에 접근하므로 먼저 빈 상태를 검사한다. 메모리 할당 실패, 큐 전체 해제 함수는 학습용 코드에서 생략됐으며 실제 프로그램에서는 처리해야 한다.

Linked Queue java version

LinkedQueue.java

public class LinkedQueue<T> implements Queue<T> {

	private Node front;
	private Node rear;
	private int length;
	private class Node {
		private T data;
		private Node next;
		public Node() {
			this.data = null;
			this.next = null;
		}
		public Node(T data) {
			this.data =data;
			this.next = null;
		}
	}

	public LinkedQueue() {
		this.length = 0;
	}
	@Override
	public void enqueue(T data) {
		Node newNode = new Node(data);
		if (front == null) {
			front = newNode;
			rear = newNode;
		} else {
			rear.next = newNode;
			rear = newNode;
		}
		length++;
	}

	@Override
	public T dequeue() {
		if (isEmpty()) {
			throw new IndexOutOfBoundsException("is empty");
		}
		Node remove = front;
		front = front.next;
		if (front == null) rear = null;
		remove.next = null;
		length--;
		return remove.data;
	}


	@Override
	public boolean isEmpty() {
		if (length == 0) {
			return true;
		}
		return false;
	}
	@Override
	public boolean isFull() {
		// 연결 큐에는 고정 용량이 없다.
		return false;
	}

	@Override
	public String toString() {
		Node temp = front;
		if (temp == null) {
			return "[ ]";
		} else {
			// StringBuilder 클래스를 이용하여 데이터를 출력
			StringBuilder sb = new StringBuilder("[");
			sb.append(temp.data);
			temp = temp.next;
			while (temp != null) {
				sb.append(", ");
				sb.append(temp.data);
				temp = temp.next;
			}
			sb.append("]");
			return sb.toString();
		}
	}
}

Java 연결 큐에서 enqueue(A), enqueue(B) 후 A를 꺼내면 front가 B로 이동하고 rear는 그대로 B다. B까지 꺼내면 두 참조가 모두 null이어야 다음 삽입을 새 큐처럼 처리한다. 기존 코드는 마지막 제거 후 rear를 남겨 뒀다. length가 static이면 다른 큐 인스턴스의 삽입·삭제가 현재 큐의 빈 상태 판단에 영향을 주므로 인스턴스 필드로 고쳤다.

구현	삽입·제거	공간	주의할 경계
선형 배열	끝에 닿으면 재사용 불가	고정 용량	앞쪽 빈 칸 낭비
원형 배열	각각 O(1)	고정 용량	비어 있음과 가득 참 구분
연결 큐	각각 O(1)	요소마다 노드	마지막 제거 후 rear 초기화

Java 표준 API를 쓰는 코드라면 ArrayDeque가 양끝 삽입·제거를 지원한다. 예외가 필요한지에 따라 remove·add와 특별 값을 돌려주는 poll·offer의 차이를 정해야 한다. Oracle Deque 문서에 연산 대응표가 있다.

Queue.java

public interface Queue<T> {
	public void enqueue(T t);
	public T dequeue();
	public boolean isFull();
	public boolean isEmpty();
}

소스코드

github 이동 (Click)