큐(Queue)

큐(Queue)란?

• 새로운 아이템의 추가와 기존의 아이템의 삭제가 다른 끝점에서 일어나는 linear한 자료구조
  • rear: insertion이 일어나는 끝 점
  • front: removal이 일어나는 다른 끝 점
• FIFO(First-In First-Out): 먼저 들어온 것이 먼저 나간다.

• 큐의 구현체는 주로 LinkedList 이다. ⇒ Array-based Queue vs Linked Queue

응용 예

• 그래프의 넓이 우선 탐색(BFS)에서 사용
• CPU threading or multi-tasking scheduling
• 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킴
• printing queue(pool)
• keystrokes

---

Queue에서의 연산

• queue(): 새로운 큐를 만든다.
• enqueue(item) : 새로운 아이템을 큐에 넣는다. (rear)
• dequeue(): 큐에 있던 아이템을 제거한다.(front)
• getvalue(): 큐의 front에 있는 아이템의 value를 가져온다.
• isEmpty(): queue가 비었는지 확인한다.
• size(): queue에 있는 아이템의 개수를 얻어온다.

---

Array-based Queue

• 아이템의 최대 개수가 고정되어 있다.

1. front나 rear 하나만 움직이는 방법

 

• (a) front를 움직이는 방법
  • enqueue() ⇒ O(n)
  • dequeue() ⇒ O(1)
• (b) rear를 움직이는 방법
  • enqueue() ⇒ O(1)
  • dequeue() ⇒ O(n)
• 빈번하게 데이터를 쓰고 지울 때는 복잡도가 높다.

2. front와 rear를 둘 다 움직이는 방법

• enqueue() ⇒ O(1)
• dequeue() ⇒ O(1)

• 

• 하지만 front가 지나간 자리를 사용할 수 없어서 낭비가 발생한다.

3. ring shape(원형 큐)

• 배열을 ring shape인 것처럼 생각한다. 이는 데이터를 추가/삭제할 때 모듈러 연산으로 구현할 수 있다.
• enqueue(): rear = (rear+1) % (배열의 크기)
• dequeue(): front = (front +1) % (배열의 크기)
• 메모리 공간은 잘 활용하지만, 배열로 구현되어 있기 때문에 큐의 크기가 제한

---

Linked Queue

• 데이터를 계속 붙일 수 있다(메모리의 크기에 따라)
• 주소를 저장해야 하기 때문에 그만큼 메모리가 더 필요하다.
• single liked list와 비슷하다.
• 초기화

• enqueue()

 📌 1. 새로운 노드를 만든다.
2. rear가 가리키는 노드 뒤에 뒤에 넣는다. (원래 rear의 링크필드를 변경)
3. rear가 새로 추가한 노드를 가리키도록 한다.
4. size를 1 추가해 준다.

 

• dequeue()

📌 1. front 노드가 가리키는 노드(A)로 간다.
2. 그 노드(A)와 연결된 노드를 front 가 가리키도록 한다.
3. size를 1 추가해 준다.

---

JAVA 구현

Array Queue(움직이는 front, rear)

public class ArrayQueue {
    int MAX = 1000;
    int front;    //머리 쪽에 위치할 index값, pop할때 참조하는 index
    int rear;    //꼬리 쪽에 위치할 index값, push할때 참조하는 index
    int [] queue;
    public ArrayQueue() {
        front = rear = 0;    //초기값 0
        queue = new int[MAX]; //배열 생성
    }

    public boolean isEmpty() { //queue에 아무것도 들어있지 않은지 판단하는 함수
        return front == rear;
    }
    public boolean isFull() {    //queue가 가득 차 공간이 없는지 판단하는 함수
        if(rear == MAX-1) {
            return true;
        }else 
            return false;
    }
    public int size() { //queue에 현재 들어가 있는 데이터의 개수를 return
        return front-rear;
    }
    public void enqueue(int value) {
        if(isFull()) {
            System.out.println("Queue is Full");
            return;
        }
        queue[rear++] = value; //rear가 위치한 곳에 값을 넣어주고 rear를 증가시킨다.
    }
    public int dequeue() {
        if(isEmpty()) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int popValue = queue[front++];
        return popValue;
    }
    public int peek() {
        if(isEmpty()) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int popValue = queue[front];
        return popValue;
    }
}

Array Queue (Ring shape)

public class ArrayQueue {
	private Object queueArray[];
	private static final int DEFAULT_SIZE = 10;
	private int maxSize; // 큐의 최대 크기
	private int front; 
	private int rear; 

	ArrayQueue(int size) {
		maxSize = size + 1; // 공백, 포화 상태를 쉽게 구분하기 위해 자리 하나를 항상 비워둠
		rear = 0;
		front = 1;
		queueArray = new Object[maxSize];
	}

	ArrayQueue() {
		this(DEFAULT_SIZE);
	}

	public void clear() {
		rear = 0;
		front = 1;
	}

	public boolean enqueue(Object it) {
		if (((rear + 2) % maxSize) == front)
			return false; // 가득차 있다
		
		rear = (rear + 1) % maxSize; 
		queueArray[rear] = it;
		return true;
	}
	
	public Object dequeue() {
		if (length() == 0)
			return null; // 비어있다.
		
		Object it = queueArray[front];
		front = (front + 1) % maxSize; // Circular increment
		return it;
	}

	// front 값 반환
	public Object frontValue() {
		if (length() == 0)
			return null;
		return queueArray[front];
	}

	// 큐의 현재 길이 반환
	public int length() {
		return ((rear + maxSize) - front + 1) % maxSize;
	}

	// 큐가 비었는지 확인
	public boolean isEmpty() {
		return front - rear == 1;
	}

	// 큐가 가득 차있는지 확인
	public boolean isFull() {
    return ((rear+2) % size == front);
	}
} 

Linked Queue

public class LinkedQueue { // 큐의 기능을 만들 클래스
	private Node front, rear;
	private int size;

	public LinkedQueue() {
		front = rear = null;
	}

	public boolean queueisEmpty() {
		if (front == null && rear == null) {
			return true;
		} else {
			return false;
		}
	}

	public void enqueue(String value) {
		Node newNode = new Node(value, null);
		if (queueisEmpty()) { // 큐안에 데이터가 없으면 첫번째 Node에 front와 rear를 연결
			front = rear = newNode;
		} else {
			front.link = newNode; // 큐 안에 데이터가 있으면 front를 다음 노드에 연결 후 front의 값을 마지막 노드로 삽입
			front = newNode;
			size++;
		}
	}

	public String dequeue() {
		if (queueisEmpty()) {
			System.out.println("Queue is Empty");
			return null;
		} else {
			Node popNode = rear;
			rear = rear.link;
			size--;
			return popNode.data;
		}
	}
	
	public int size() {
		return size;
	}
}

---

API

JAVA

• import java.util.*;
• Queue<T> queue = new LinkedList<>();
• 자바에서 Queue는 인터페이스이다. 그래서 구현 클래스를 사용해야 한다.
• add() , offer() : 큐에 삽입
  • add는 overflow될 때까지 쓸 수 있다. offer은 overflow되면(다 차면) 넣지 x
• peek() : 가장 먼저 큐에 들어간 요소 반환
• remove() , poll() : 가장 먼저 큐에 들어간 요소 삭제하면서 반환
• isEmpty() : 큐가 비어있는지 반환
• size() : 큐에 있는 요소의 크기 반환

Python

• list를 간단히 큐로 활용한다. 맨 앞에 넣고 맨 뒤에서 빼는 형식
• euqueue(item): O(n)
• dequeue(): O(1)

C++

• std::queue 인데 어떤 container(vertor,list,deque,,,)로 queue로 쓸 수 있음
• front(), back(), size(), empty()
• push(item) : (=enqueue()) O(1)
• pop() : (=dequeue()) O(1)

---

요약

• FIFO
• 주로 linked List 사용
• 스택과 비교해보기
• 스택(Stack)

스택(Stack)

 

참고자료

https://opendsa-server.cs.vt.edu/ODSA/Books/CS2/html/

Chapter 0 Preface — CS2 Software Design & Data Structures

 

여담

- 노션으로 쓴 걸 티스토리에 올리는 건 너무 번거롭다.