[자료구조] Chapter 4. Queue

경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

 

What is Queue?

• Queue: 가장 처음에 들어간 데이터가 가장 먼저 나오는 선입선출, FIFO(First-In, First-Out)의 자료구조를 가진다.
• homogeneous items의 oerdered group
• rear - new element가 삽입되는 위치 -> enqueue
• front - element가 삭제되는 위치 -> dequeue
• ex) job buffers, network buffers, ...

 

1. Queue 자료구조의 ADT

Constructor: 
QueueType(int maxQue);

Transformer:
void enqueue(ItemType value);
- rear 위치로 value 삽입

ItemType dequeue();
- first 위치의 value를 queue에서 삭제 및 해당 값 반환

void clear();
- queueu 내부의 value 모두 삭제 

Observer:
bool isFull() const;
bool isEmpty() const;

 

2. Queue 자료구조 Implementation

template<class ItemType>
class QueueType {
private:
    ItempType * data;
    int front;
    int rear;
    int maxQueue;
public:
    QueueType(int maxQue);
    void enqueue(ItemType value);
    ItemType dequeue();
    void clear();
    
    bool isFull() const;
    bool isEmpty() const;
    
    ~QueueType();
}

template<class ItemType>
QueueType<ItemType>::QueueType(int maxQue) {
    //constructor -- No return type
    maxQueue = maxQue + 1;
    front = maxQueue - 1;
    rear = maxQueue - 1;
    data = new ItemType[maxQueue];
}

// O(1)
template<class ItemType>
void QueueType<ItemType>::enqueue(ItemType newItem) {
    rear = (rear + 1) % maxQueue;
    data[rear] = newItem;
}

// O(1)
template<class ItemType>
ItemType QueueType<ItemType>::dequeue() {
    front = (front + 1) % maxQueue;
    return data[front];
}

// O(1)
template<class ItemType>
bool QueueType<ItemType>::isFull() const {
    return (rear == front);
}

// O(1)
template<class ItemType>
bool QueueType<ItemType>::isEmpty() const {
    return ((rear + 1) % maxQueue == front);
}

// O(1)
template<class ItempType>
int QueueType<ItemType>::size() const {
    return maxQueue;
}

template<class ItemType>
QueueType<ItemType>::~QueueType() {
    //Destructor
    delete [] data;
}

 

- Full vs Empty

-> 빈 공간이 없이 구현할 경우, full과 empty 상황이 겹침

 

-> Reserved 공간을 하나 확보해야 full과 empty 상황이 겹치지 않는다.

 

- (index + 1) % maxQueue 수식

• circular queue의 특성에 따라, max index를 넘어갈 때 다시 처음으로 돌아올 수 있도록 계산