Queue

• FIFO (First-In First Out)
• Rear에서 삽입이 이루어지고, Front에서 삭제가 이루어진다.
  

※linked list를 사용하여 Queue 구현

Queue class

template <class Item>
class queue {
public:
	queue() {
		front_ptr = NULL;
	}
	void push(const Item& data);
	void pop();
	bool empty() const;
	Item front() const;

private:
	node<Item>* front_ptr;
	node<Item>* rear_ptr;
};

empty

template <class Item>
bool queue<Item>::empty() const {
	return front_ptr == NULL;
}

push

template <class Item>
void queue<Item>::push(const Item& data) {
	// Queue가 비어있는지 확인
	if (empty()) {
    	// Linked list 처음 데이터 삽입
		head_insert(front_ptr, data);
        // rear_ptr 설정
		rear_ptr = front_ptr;
	}
	else {
    	// liked list 가장 마지막(rear_ptr 다음 위치)에 데이터 삽입
		list_insert(rear_ptr, data);
        // rear_ptr 변경
		rear_ptr = rear_ptr->after_link();
	}
}

Linked list를 사용하여 구현한 Queue는 Queue overflow를 고려하지 않아도 된다.

pop

template <class Item>
void queue<Item>::pop() {
	// Queue underflow
	assert(!empty());
	// Linked list의 head 부분 데이터를 삭제
	head_remove(front_ptr);
}

Queue가 비어있는 경우 Queue underflow를 고려해야 한다.

front

template <class Item>
Item queue<Item>::front() const {
	// Queue가 비어있으면 Error
	assert(!empty());
	return front_ptr->data();
}