Queue (큐)

Queue

Queue 는 대기줄이라는 의미가 있다.

일상생활에서 생각했을때 대기줄은 먼저 온 사람부터 나가게 되어있는데 그 부분을 그대로 구현한 자료구조이다.

 

FIFO (First-In First_Out) 방식을 따른다.

Necessary components

• front : queue의 맨 앞 index
• rear : queue의 맨 뒤 index
• enqueue(item) : item을 queue의 맨 뒤에 추가
• dequeue() : 맨 앞의 요소를 삭제하며 반환

Additional operations

• empty() :queue가 비어있는지 확인
• full() : queue가 가득 차있는지 확인
• peek() : 맨 앞 부분 삭제하지 않고 반환
• size() : queue의 현재 크기 반환

---

Implementation

Array Queue

• front, rear = 0 으로 초기화
• enqueue(item), item을 맨 뒤로 삽입
• dequeue(), 맨 앞의 값 삭제하고 반환한뒤 모든 값을 한칸씩 당김

#include <iostream>

using namespace std;

// 배열 큐
class ArrrayQueue{
private:
	//최대 크기
    const static int MAX_SIZE = 100;
    int front;
    int rear;
    int data[MAX_SIZE];
public:
    ArrrayQueue(){
        front = rear = 0;
    }
    ~ArrrayQueue(){}
    bool empty(){return front == rear;}
    bool full(){return rear == MAX_SIZE;}
    int peek(){
        if(empty()){
            throw "queue is empty";
        }
        else return data[front];
    }
    void enqueue(int item){
        if(full()){
            throw "queue is full";
        }
        else{
            rear = rear + 1;
            data[rear] = item;
        }
    }
    //ret에 값 넣어두고 배열 값 옮기기
    int dequeue(){
        if(empty()){
            throw "queue is empty";
        }
        else{
            int ret = data[front];
            for(int i=0; i<rear; i++){
                data[i] = data[i+1];
            }
            rear--;
            return ret;
        }
    }
    void display(){
        cout<< "queue : ";
        for(int i=0; i<=rear; i++){
            cout<< data[i] << endl;
        }
        cout << endl;
    }
};

여기서 문제점은 dequeue() 연산시 자리를 옮기는 과정에서 오버헤드가 발생한다.

data가 n개 라고 가정한다면 n-1개의 데이터를 각각 1번씩 n-1번을 옮겨야하는 것인데,

 

이를 해결한 자료구조가 Circular queue이다.

---

Circular queue (원형 큐)

정적 배열이지만 끝과 끝을 이어 원형이라고 생각하고 순환하는 구조를 만든것이다.

즉 queue의 맨 처음 값은 front를 기준으로 생각하게 된다.

 

이때 dummy 로 하나의 칸은 비워두고 채우게 구현할 것이다.

dummy없이 원형 큐를 구현하게 된다면 큐가 empty일때와 full일때의 차이를 구분하기 어렵기 때문이다.

(a). 와 (f).를 비교했을때 front, rear pointer는 같지만 상태는 정반대인 것을 확인 할 수 있다.

#include <iostream>

using namespace std;

class CircularQueue{
protected:
    const static int MAX_SIZE = 100;
    int front;
    int rear;
    int data[MAX_SIZE];
public:
    CircularQueue(){
        front = rear = 0;
    }
    ~CircularQueue(){}
    bool empty(){return front == rear;}
    bool full(){return (rear+1)%MAX_SIZE == front;}
    void enqueue(int item){
        if(full()){
            throw "queue is full";
        }
        else{
            rear = (rear+1)%MAX_SIZE;
            data[rear] = item;
        }
    }
    int dequeue(){
        if(empty()){
            throw "queue is empty";
        }
        else{
            front = (front+1)%MAX_SIZE;
            return data[front];
        }
    }
    int peek(){
        if(empty()){
            throw "queue is empty";
        }
        else return data[(front+1)%MAX_SIZE];
    }
    void display(){
        cout<< "queue : ";
        int max = (front<rear) ? rear : rear+MAX_SIZE;
        for(int i=front+i; i<=max; i++){
            cout<< data[i%MAX_SIZE];
        }
        cout << endl;
    }
};

Time Complexity

ArrayQueue

• enqueue() : O(1)
• dequeue() : O(n)

CircularQueue

• enqueue() : O(1)
• dequeue() : O(1)

Pros & Cons

Pros : CircularQueue 는 공간을 추상화 하여 연산의 시간복잡도를 줄였다.

Cons : Array 기반 Queue는 할당받은 공간에 비해 적게 사용한다면 공간 낭비를 하게 된다.

 

Solutions

1. STL vector를 활용한 queue
2. Linked list 이용한 queue

---

LinkedQueue

//linux linked list code 참조
#include <iostream>

using namespace std;

class Item{
private:
    int id;
public:
    Item(int id){this->id = id;}
    int get_id(){return id;}
};

class Node{
private:
    Item item;
    Node* link;
public:
    Node(const Item &item):item(item){this->link = nullptr;}
    Node* get_link(){return this->link;}
    void set_link(Node* p){this->link = p;}
    Item get_item(){return item;}
};

class LinkedQueue{
private:
    Node* front;
    Node* rear;
public:
    LinkedQueue(){
        this->front = this->rear = nullptr;
    }
    bool empty(){
        return this->front == nullptr;
    }
    ~LinkedQueue(){
        while(!this->empty()){
            this->dequeue();
        }
    }
    void display(){
        for(Node* p = front; p != nullptr; p = p->get_link()){
            cout<< p->get_item().get_id() <<endl;
        }
    }
    void enqueue(const Item &item){
        if(this->empty()){
            this->front = this->rear = new Node(item);
        }
        else{
            Node* p = new Node(item);
            this->rear->set_link(p);
            this->rear = p;
        }
    }
    Item dequeue(){
        //데이터가 없는 경우
        if(this->empty()){throw 'Qeueue is empty';}
        //데이터가 있는 경우
        else{
            Node* p = this->front;
            this->front = this->front->get_link();
            Item item = p->get_item();
            if(p != nullptr) delete p;
            // dequeue 이후 데이터가 없는 경우
            if(this->front == nullptr) this->rear = nullptr;
            return item;
        }
    }
};

Time Complexity

LinkedQueue

• enqueue() : O(1)
• dequeue() : O(1)

Pros & Cons

Pros : LinkedQueue 는 공간을 추상화 하여 연산의 시간복잡도를 줄였다.

Cons : data하나의 생성에 Node class만큼의 메모리를 더 소비하게 된다.

 

데이터가 크기가 고정적이면 "CirculaQueue",

데이터 크기가 가변적이면 "LinkedQueue"가 효율적이다.