자료구조 스터디 week5 - 큐

큐(Queue)

입장을 위해 줄 서는 모습, 대기열과 같이 먼저 들어온 데이터가 먼저 나가는 방식으로 실행되는 자료구조

따라서 선입선출(FIFO)의 특징을 가진다.

- 후입선출(LIFO) 특징을 가지는 스택과는 대비되는 개념이다.

 

배열 자료형을 이용하며, 변수 front와 tail을 통해 큐에 있는 자료를 추가 혹은 삭제할 수 있다.

물론 큐의 최대 크기를 예상할 수 있는 경우에는 배열이 가장 효율적이지만, 작업 과정에서 배열의 크기를 예상할 수 없는 경우 배열의 크기를 재할당 받아야하는 단점이 존재한다.

 

배열을 이용한 큐 구현

ADT 큐에는 4개의 필드 queue[], numItems, front, tail이 있고, 5개의 함수가 있다.

예) enque(x), dequeue(), front(), isEmpty(), dequeueAll()

 

먼저 큐를 초기화하기 위해서 배열을 할당받는다. 이후 원소가 들어있지 않을 때는 numItems를 0으로 설정하고, 삽입될 때 마다 혹은 삭제될 때 1씩 증가 혹은 감소시킨다.

 

 

배열 상에서 값이 추가될 때 tail이 1씩 증가하고, 삭제가 발생할 때마다 front가 1씩 증가한다. 하지만 이와 같은 로직은 공간 낭비를 발생시킬 수 있다. 따라서 알고리즘을 이용하여 배열을 원형으로 인식하도록 할 필요가 있다.

 

스택에서 공간상의 비효율 발생을 없애기 위해 아래와 같이 동작하도록 한다.

// 원소 삽입
tail <- (tail + 1) % queue.length
queue[tail] <- x

// 원소 삭제
queueFront <- queue[front]
front <- (front + 1) % queue.length

배열의 길이를 초과할 경우 인덱스를 길이로 나누어 초기의 인덱스부터 시작하도록 설정할 수 있다.

 

원소 삽입

큐에서 원소를 삽입할 때는 마지막 부분에 삽입한다

구현 방법 : 원소를 삽입할 때는 tail 값을 1 증가시킨 다음 그 자리에 새 원소를 저장한다

 

euqueue(x):
    if (isFull()) /* 에러 처리 */
    else
        tail <- (tail+1) % queue.length
        queue[tail] <- x
        numItems++

 

원소 삭제

큐에서 원소 삭제는 가장 먼저 들어온 원소를 대상으로 한다

구현 방법 : front에 있는 원소를 삭제하고 front를 1 증가시키는 방법으로 구현한다

dequeue():
    if (isEmpty()) /* 에러 처리 */
    else
        queueFront <- queue[front]
        front <- (front+1) % queue.length
        numItems--
        return queueFront

 

 

최종 코드

package queue;

public interface QueueInterface<E> {
    public void enqueue(E x);
    public E dequeue();
    public E front();
    public boolean isEmpty();
    public void dequeueAll();
}

package queue;
public class ArrayQueue<E> implements QueueInterface<E> {

    private E queue[];
    private int front, tail, numItems;
    private static final int DEFAULT_CAPACITY = 64;
    private final E ERROR = null;
    
    public ArrayQueue() {
        queue = (E[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        tail = DEFAULT_CAPACITY - 1;
        numItems = 0;
    }
    
    public ArrayQueue(int n) {
        queue = (E[]) new Object[n];
        front = 0;
        tail = n - 1;
        numItems = 0;
    }
    
    // 큐에 원소 삽입하기
    public void enqueue(E newItems) {
        if (isFull()) System.out.println("Queue Full");
        else {
            tail = (tail + 1) % queue.length;
            queue[tail] = newItem;
            ++numItems;
        }
    }
    
    // isFull()
    public boolean isFull() {
    	return (numItems == queue.length);
    }
    
    // 큐에서 원소 삭제하기
    public E dequeue() {
    	if (isEmpty()) return ERROR;
        else {
            E queueFront = queue[front];
            front = (front + 1) % queue.length;
            --numItems;
            return queueFront;
        }
    }
    
    // front()
    public E front() {
    	if (isEmpty()) return ERROR;
        else return queue[front];
    }
    
    // 큐가 비었는지 확인하기
    public boolean isEmpty() {
    	return (numItems == 0);
    }
    
    // 큐 비우기
    public void dequeueAll() {
    	queue = (E[]) new Object[queue.length];
        front = 0;
        tail = queue.length - 1;
        numItems;
    }
}

 

 

연결리스트를 이용한 큐 구현

여러 연결리스트 중 단방향 원형 연결리스트를 이용하여 큐를 구현할 수 있음

레퍼런스 tail이 리스트의 마지막 노드를 가리키고 이를 통해서 첫번째 front 노드에 접근할 수 있다.

필드는 큐의 끝을 가리키는 tail 1개가 필요하며, 함수는 5개가 있다.

 

원소 삽입

원소를 삽입할 때는 무조건 맨 뒤에 삽입한다

구현 방법 : 원소를 tail 노드 뒤에 삽입하고 레퍼런스 tail이 삽입된 새 노드를 가리키도록 변경한다. 이 후 새 노드는 리스트의 첫번째 노드로 연결시킨다

* 만약 큐가 비어있다면 tail이 가리키는 노드가 없기 때문에 tail.next를 쓸 수 없다. 따라서 코드 구현시에 큐가 비어있는 경우를 함께 생각해야한다

enqueue(newItem):
    if (isEmpty())
        newNode.next <- newNode
        tail <- newNode
    else:
        newNode.next <- tail.next
        tail.next <- newNode
        tail <- newNode

 

원소 삭제

맨 앞에 있는 원소를 삭제한다

구현 방법 : tail 노드가 front 노드를 링크하므로 tail의 링크를 한 번 따라가면 front 노드를 만난다. front 노드를 가리키고 있던 tail 노드의 링크를  front 노드의 다음 노드를 가리키도록 바꾼다

dequeue():
    if (isEmpty()) /* 에러 처리 */
    else
        front <- tail.next
        if (front = tail)				// 원소 1개
            tail <- null
        else						// 2개 이상의 원소
            tail.next <- front.next
        return front.item

 

 

최종 코드

package queue;
import list.Node;

public class LinkedQueue<E> implements QueueInterface<E> {
    private Node<E> tail;
    private final E ERROR = null;	// 임의의 에러 값
    public LinkedQueue() {
        tail = null;
    }

    // 큐에 원소 삽입하기
    public void enqueue(E newItem) {
        Node<E> newNode = new Node<>(newItem);
        if (isEmpty()) {
            newNode.next = newNode;
            tail = newNode;
        } else {
            newNode.next = tail.next;
            tail.next = newNode;
            tail = newNode;
        }
    }

    // 큐에서 원소 삭제하기
    public E dequeue() {
        if (isEmpty()) return ERROR;
        else {
            Node<E> front = tail.next;
            if (front == tail)			// only one item in queue
                tail = null;
            else				// more than one item
                tail.next = front.next;
            return front.item;
        }
    }

    // front()
    public E front() {
        if (isEmpty()) return ERROR;
        else return tail.next.item;		// tail.next == front
    }

    // isEmpty()
    public boolean isEmpty() {
        return (tail == null);
    }

    // 큐 비우기
    public void dequeueAll() {
        tail = null;
    }
}