[자료구조] Queue(큐) - Java, Python

---

큐(Queue)

큐는 선입선출(FIFO : First In First Out)로 처리되는 자료구조이다. 즉 먼저 들어가는 원소가 가장 먼저 나오는 구조이다.

큐에서의 선입선출

위 사진에서 원소 1은 제일 먼저 큐에 들어왔기때문에 제일 먼저 제거된다. 이게 바로 선입선출이다.(FIFO : First In First Out)

 

큐에 원소를 넣는 것을 enqueue 라고 하며, 큐에서 원소를 제거하는 것을 dequeue 라고 한다.

 

C, C++, Java, Python 또는 C#과 같은 다양한 언어들로 스택을 구현할 수 있지만, 성능은 거의 동일하다.

---

큐의 기본적인 명령어

- Enqueue : 큐 끝(마지막)에 원소 추가

- Dequeue : 큐 맨 앞(시작점)에 위치한 원소 제거

- IsEmpty : 큐가 비어있는지 체크

- IsFull : 큐가 가득 찼는지 확인

- Peek : 큐의 맨 앞에 위치한 원소 값(value)를 읽어옴(제거하지 않는다)

---

큐의 동작방식

큐는 다음과 같은 방식으로 진행된다.

 

1. FRONT 와 REAR 두 개의 포인터 생성

 

- FRONT : 큐의 첫번째 원소 추적

 

- REAR 큐의 마지막 원소 추적

 

2. 큐가 초기화(Initializing)되었을 때, FRONT 와 REAR 값을 -1로 설정

 

Enqueue Operation

1. 큐가 꽉 찼는지 확인한다( IsFull )

 

2. 첫번째 원소에 대해서 FRONT 값을 0으로 설정한다

 

3. REAR 가 가르키는 index를 1 늘린다

 

4. REAR 값이 가르키는 위치에 새로운 원소를 추가한다.

 

Dequeue Operation

 

1.  큐가 비어있는지 확인한다( IsEmpty )

 

2. FRONT 가 가르키는 index 의 value 를 반환한다

 

3. FRONT 가 가르키는 index 를 1 늘린다.

 

4. 마지막 원소일 경우, FRONT 와 REAR 값을 -1로 초기화한다.

Enqueue 및 Dequeue 동작

---

큐 구현

Python

#Python

class Queue:

	#최초실행시 queue 생성
    def __init__(self):
        self.queue = []

    # 큐에 원소 추가
    def enqueue(self, item):
        self.queue.append(item)

    # 큐에서 원소 제거
    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

    # 큐 출력
    def display(self):
        print(self.queue)

	# 큐 사이즈?
    def size(self):
        return len(self.queue)


q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)

q.display()

q.dequeue()

print("After removing an element")
q.display()

Java

// Java

public class Queue {
  int SIZE = 5;
  int items[] = new int[SIZE];
  int front, rear;

  //front, rear 초기값 설정
  Queue() {
    front = -1;
    rear = -1;
  }
  
  // 큐 가득찼는지 확인
  boolean isFull() {
    // 첫 원소 존재하고, 마지막 원소가 배열 마지막에 위치할때 가득참!
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    return false;
  }

  // 큐 비어있는지 확인
  boolean isEmpty() {
    // 원소가 존재하지 않다면 == front값 초기값과 같다면
    if (front == -1)
      return true;
    else
      return false;
  }

  // Enqueue
  void enQueue(int element) {
    // 제일 먼저 큐가 가득차있는지 체크
    if (isFull()) {
      System.out.println("Queue is full");
    } else {
      // 큐에 아직 원소 없으면 front값 0 으로
      if (front == -1)
        front = 0;  
      rear++;
      items[rear] = element;
      System.out.println("Inserted " + element);
    }
  }

  // Dequeue
  int deQueue() {
    int element;
    if (isEmpty()) {
      System.out.println("Queue is empty");
      return (-1);
    } else {
      element = items[front];
      if (front >= rear) {
        front = -1;
        rear = -1;
      } /* 큐에 원소가 하나 남아있을 때 Dequeue를 하게되면, 이후 큐가 비어있게 된다. 
        따라서 front와 rear값을 -1로 초기화해주어야한다. */
      else {
        front++;
      }
      System.out.println("Deleted -> " + element);
      return (element);
    }
  }

  void display() {
    /* 큐에 있는 원소들을 나열하여 보여주기 위한 function */
    int i;
    if (isEmpty()) {
      System.out.println("Empty Queue");
    } else {
      System.out.println("\nFront index-> " + front);
      System.out.println("Items -> ");
      for (i = front; i <= rear; i++)
        System.out.print(items[i] + "  ");

      System.out.println("\nRear index-> " + rear);
    }
  }

  public static void main(String[] args) {
    // 사이즈 5짜리 큐 생성
    Queue q = new Queue();

    // deQueue 는 큐가 비어있을 때 사용할 수 없다.
    q.deQueue();

    // 원소 1, 2, 3, 4, 5 삽입
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    q.enQueue(4);
    q.enQueue(5);

    // 원소 6은 큐가 가득찼기때문에 더이상 넣을 수 없다.
    q.enQueue(6);

    q.display();

    // deQueue function을 실행하면 제일 먼저 삽입된 원소 1부터 지우게 된다.
    q.deQueue();

    // 4개의 원소만 보인다!
    q.display();

  }
}

---

큐의 한계

아래 이미지에서 볼 수 있듯이, Enqueue와 Dequeue를 한 후 큐의 길이가 줄어들었다.

큐의 한계

index 0 또는 1에 원소를 넣고싶다면, 모든 원소를 Dequeue 하거나, 큐 자체를 리셋시켜야한다.

 

Circular Queue (순환 큐) 를 사용하면 REAR 가 마지막 index에 있을 때, 원소를 또 넣을 수 있고, 이때 REAR의 index는 0으로 다시 돌아간다. (위의 사진이 만약 순환 큐 일 경우)

---

큐의 시간복잡도

array 기반의 Enqueue 와 Dequeue 를 사용하는 Queue 는 O(1)의 시간복잡도를 가진다.

다만, Python 코드 에서 pop(N)을 사용한다면 pop되는 원소의 위치에 따라 O(n)의 시간복잡도를 갖게 된다.

---

큐 를 사용해보자

큐의 일반적인 사용 용도

 

- CPU 스케줄링, Disk 스케줄링

 

- 두 프로세스 간에 데이터가 비동기적으로 전송되는 경우, 동기화시기키위해 큐 를 사용한다 ( IO Buffers, pipes, file IO, etc...)

 

- 실시간 시스템의 장애 제어

 

- 콜센터 시스템 ( 사람들의 전화를 큐에 넣고 하나씩 처리한다 )