4-1. 연결 큐 (Linked Queue)

연결 리스트로 Queue 구현

 

Queue Class 정의

class LinkedQueue;	// 전방 선언

class ChainNode {
friend class LinkedQueue;
private:
   int data;
   ChainNode *link;
public:
   ChainNode (int element=0, ChainNode* next=0) // 생성자
      { data=element; link=next; }
};

class LinkedQueue{
private:
   ChainNode *top;
public:
   LinkedQueue() { top=0; };		// 생성자
   void Push(const int&);		// 삽입 함수
   int* Pop(int&)			// 삭제 함수
};

 

 

Linked Queue 삽입

void LinkedQueue::Push (const int& e){
   if (front==0)	// empty queue
      front = rear = new ChainNode(e,0);
   else			// node 삽입 후 rear 수정
      rear = rear->link = new ChainNode(e,0);
}

 

Linked Queue 삭제

int* LinkedQueue::Pop (int& retvalue){
// 첫번째 node 제거, 주소 반환
   if(front==0)		// empty queue
      return 0;
   ChainNode* delNode = front;
   retvalue = front->data;	// 삭제되는 값 저장
   front = front->link;		// 다음 node로 이동
   delete delNode;
   return &retvalue;
}