[Data Structure] Queue(큐)

Queue (큐)

 

큐 개념

큐의 삽입과 삭제의 원리는 First-In First-Out(FIFO, 선입선출)로 작동한다. 가장 먼저 들어온 데이터가 가장 먼저 나가게된다. 큐의 실제 활용 예시는 다음과 같다.

• 대기열
• 공유자원의 접근권한, 순서
• 멀티 프로그래밍 과정

 

Queue ADT

큐의 추상자료형은 다음과 같다.

• enqueue(object) : 데이터를 큐의 제일 마지막에 삽입한다.
• dequeue() : 큐의 가장 앞에 있는 데이터를 제거한다.
• object front() : 큐의 가장 앞에 있는 데이터를 반환해준다.
• integer size() : 큐에 저장된 원소들의 개수를 반환해준다.
• boolean empty() : 큐가 비어있는 지를 확인해준다.

 

Queue implementation (큐 구현)

큐의 구현방식은 스택과 마찬가지로 2가지 방법이 있다.

1. Array-based Queue
2. Linked List-based Queue

 

Array-based Queue (배열 기반 큐)

 

ArrayQueue prototype

#include <iostream>
#include <string>
using namespace std;

class arrayQueue {
public:
  int* Q;
  int capacity;
  int n;
  int f;
  int r;

  arrayQueue(int size);
  arrayQueue();
  int size();
  bool isEmpty();
  int front();
  int rear();
  void enqueue(int data);
  void dequeue();
}

배열 기반 큐의 프로토타입 함수 종류들이다. 멤버변수에서 포인터 변수인 Q는 실제로 큐의 역할을 저장하는 변수이다. 배열 기반의 큐는 스택과 다르게 보통 원형 큐의 형태로 제작해서 Circular array로 구현을 하는데, 그래서 큐의 성질에 맞게 가장 앞의 인덱스를 알려주는 f와 가장 뒤의 인덱스를 알려주는 r변수를 갖고있다.

 

arrayQueue initializer (생성자)

arrayQueue(int size) {
  this->n = 0;
  this->Q = new int[size];
  this->capacity = size;
  this->f = 0;
  this->r = -1;
}

배열기반 큐의 생성자이다. 배열기반이므로 배열의 기본 크기를 정해준다. 그리고 스택에서 top의 index역할과 유사한 것이 r이므로 r은 -1로, f는 0으로 초기화 해준다. f가 이동하는 경우는 dequeue로 가장 앞의 원소를 삭제하는 경우이므로 0번 인덱스부터 시작해야한다.

 

isEmpty, size function

int size() {
  return n;
}

bool isEmpty() {
  return n == 0;
}

사이즈와 공백 판단 함수는 항상 그래왔듯이 어려운 구현은 아니다.

 

enqueue function

void enqueue(int data) {
  if (size() == capacity) {
    cout << "Queue is full\n";
  }else {
    r++;
    Q[r % capacity] = data;
    n++;
  }
}

사실 원형 배열로 큐를 구현할 때 f와 r의 위치로 꽉 찼는지 아닌지를 구별하지만 귀찮은 것도 있고 공간을 하나 낭비하므로 n으로 개수를 명명해주는 변수를 만들어주겠다.
환형 배열의 원리는 간단하다. mod의 원리는 활용해서 해당 위치에 데이터를 넣어주면 된다.

 

dequeue function

void dequeue() {
  if (empty()) {
    cout << "Queue is empty\n";
  }else {
    n--;
    f++;
    f = f % capacity;
  }
}

제거 연산은 더 간단하다. f의 인덱스를 변경해주기만 하면 된다. 그리고 혹시 f가 index over가 발생할 수 있으므로 mod연산이 된 것으로 바꿔준다. 어차피 capacity를 넘지 않는 이상 f는 본인 값이 유지가 된다.

 

front, rear function

int front() {
  return Q[f];
}

int rear() {
  return Q[r];
}

간단한 함수다. 각 각 알맞는 값들을 인덱스로 반환해주면된다.

 

Linked-List based Queue (링크드 리스트 기반 큐)

 

LinkedQueue prototype

#include <iostream>
using namespace std;

class Linkedlist {
public:
    int n; // count of element
    int capacity; // size of queue
    Node* f;
    Node* r;

    Linkedlist() {}

    Linkedlist(int n) {
        this->n = 0;
        this->capacity = n;
        this->f = NULL;
        this->r = NULL;
    }

    int isEmpty();
    int front();
    int rear();
    int size();
    void enqueue(int e);
    void dequeue();

    ~Linkedlist() {}

};

생성자 원리는 크게 일반적인 리스트와 다르지 않으니 생략하고 넘어간다.

 

isEmpty, size function

bool isEmpty() {
  return n == 0;
}

int size() {
  return n;
}

이 두 함수는 배열기반과 큰 차이는 없다. 그대로 유지해주면 될 듯하다.

 

enqueue function

void enqueue() {
  Node* v = new Node(e);

  if (n == capacity) {
    cout << "Full\n";
  }else{
    if (isEmpty()) {
      f = r = v;
    }else{
      r->next = v;
      r = v;
    }
    n++;
  }
}

실제로 enqueue함수는 링크드 리스트에서 addBack함수와 큰 차이는 없다. 실제로 원리가 리스트의 가장 뒤에 추가하는 것이니...
비어있을 때와 아닐 때만 잘 구분해서 구현해주면된다.

 

dequeue function

void dequeue() {
Node* old = f;

  if (isEmpty()) {
    cout << "Empty\n";
  }else{
    f = f->next;
    n--;
    delete old;
  }
}

링크드 리스트 큐의 dequeue는 removeFront와 같다. front의 위치를 옮겨주고 이전에 front의 역할을 동적할당 해제를 해주면 된다.

 

front, rear

int front() {
  if (isEmpty()) {
    return -1;
  }else {
    return f->data;
  }
}

int rear() {
  if (isEmpty()) {
    return -1;
  }else {
    return r->data;
  }
}

front와 rear는 비어있을 때의 조건을 해줄 필요가 있다. 나 같은 경우 구현문제에서는 자연수만 처리하므로 -1일 때를 빈 경우로 처리했다. 실제로는 NULL값으로 체크해도 될 것 같다.