이번 글은 queue에 대해서 살펴보겠습니다.
C++ 코드는 이곳에서 확인할 수 있습니다.
Concept
Queue는 FIFO (First In First Out) 방식의 자료구조입니다. 먼저 삽입된 데이터가 먼저 나오는 구조이고, 자료구조를 그림으로 표현하면 아래와 같습니다.
Queue에는 head와 tail이라는 포인터가 존재하고, head는 queue의 가장 앞에 있는 element를 가리키며 tail은 queue의 가장 뒤에 있는 element를 가리킵니다.
Queue Operation
Queue에는 enqueue와 dequeue operation이 있습니다.
아래 코드는 array list이지만, 기본적인 enqueue와 dequeue opeartion은 동일하게 동작합니다. 코드를 설명하면서 enqueue와 dequeue에 대해서 설명하도록 하겠습니다.
template <class elemType>
class arrayListType
{
public:
const arrayListType<elemType> &operator=(const arrayListType<elemType>&);
bool isEmpty() const;
bool isFull() const;
int listSize() const;
int maxListSize() const;
void print() const;
bool isItemAtEqual(int location , const elemType &item)const;
void insertAt(int location, const elemType &insertItem);
void insertEnd(const elemType& insertItem);
void removeAt(int location);
void retrieveAt(int locaiton, elemType &retItem) const;
void replaceAt(int locaiton, const elemType &repItem);
void clearList();
int seqSearch(const elemType& item) const;
void insert(const elemType& insertItem);
void remove(const elemType& insertItem);
arrayListType(int);
arrayListType(const arrayListType<elemType> &otherList);
~arrayListType();
protected:
elemType *list;
int length;
int maxSize;
};Stack과 마찬가지로 variadic data type을 위해서 template을 사용했고, 핵심적인 method는 insert (enqueue)와 remove (dequeue)입니다. 각 method에 대한 구현을 살펴보겠습니다.
template <class elemType>
inline void arrayListType<elemType>::insert(const elemType &insertItem)
{
if(length >= maxSize)
cerr << "cannot insert in a full list" << endl;
else{
list[length++] = insertItem;
}
}Insert method는 array list에 추가할 element를 assign한 뒤, array list의 length member를 증가시키게 됩니다.
template <class elemType>
inline void arrayListType<elemType>::remove(const elemType &insertItem)
{
if(length <= 0)
cerr << "cannot remove from a empty list" << endl;
else
length--;
}Remove method의 경우, insert와 반대로 array list의 length member를 감소시키면 됩니다.
Queue는 linked list, doubly linked list, circular list 등으로 구현해도 됩니다. 이번 글에서는 queue의 간단한 구현을 살펴보기 위해 array list를 통한 queue 자료구조와 operation에 대해서 살펴봤습니다.
질문이나 잘못된 내용에 대해서 댓글로 남겨주시면 감사하겠습니다.
