3학년 2학기 전공/자료구조
[자료구조] Chapter 4. Queue
시데브
2024. 9. 30. 15:51
경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.
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를 넘어갈 때 다시 처음으로 돌아올 수 있도록 계산
728x90
반응형