[데이터 구조] 대기 열의 순서 대기 열의 클래스 템 플 릿 구현

대기 열 은 액세스 위 치 를 제한 하 는 선형 표 이다.삽입 에 동의 하 는 한 끝 을 팀 꼬리 (rear) 라 고 하고 삭제 에 동의 하 는 한 끝 을 팀 머리 (front) 라 고 합 니 다.
대열 은 FIFO 의 성질 을 가지 고 있다
대기 열의 저장 표시 도 두 가지 방식 이 있 습 니 다. 배열 기반, 목록 기반 입 니 다.배열 기반 을 순서 대기 열 이 라 고 합 니 다.목록 기반 을 체인 대기 열 이 라 고 합 니 다.
다음은 동적 배열 의 순서 대기 열 을 기반 으로 한 템 플 릿 류 의 실현 입 니 다.
순서 대기 열의 추상 적 인 기본 클래스, 예 를 들 어 다음 과 같은 것 을 볼 수 있 습 니 다. 인터페이스 와 명시 적 인 기본 구조 함수 와 분석 함수 만 제공 하고 파생 클래스 에서 호출 합 니 다.

#ifndef QUEUE
#define QUEUE
//       

template
class Queue
{
public:
    Queue(){}
    ~Queue(){}
    virtual bool EnQueue(const T& x)=0;
    virtual bool DeQueue(T& x)=0;
    virtual bool getFront(T& x)const=0;
    virtual bool IsEmpty()const=0;
    virtual bool IsFull()const=0;
    virtual int getSize()const=0;
};

#endif

순서 대기 열의 상세 한 실현 은 다음 과 같다. (모든 순 허 함수 의 인 터 페 이 스 를 덮어 쓰 고 자신의 인터페이스 와 데이터 구성원 을 제공한다.)

/
#include"Stack.h"
#include 
//#include 
#include 
using namespace std;

template
class SeqQueue:public Queue
{
public:
    SeqQueue(int sz=10):front(0),rear(0),maxSize(sz),elements(new T[sz]){assert(elements!=NULL);}
    ~SeqQueue(){delete []elements;}
    SeqQueue(const SeqQueue& rhs);
    SeqQueue& operator=(const SeqQueue& rhs);

    bool EnQueue(const T& x);
    bool DeQueue(T& x);
    bool getFront(T& x)const;
    bool IsEmpty()const{return (rear==front)?true:false;}   //   
    bool IsFull()const{return ((rear+1)%maxSize==front)?true:false;}    //   
    int getSize()const{return (rear-front+maxSize)%maxSize;}    //    。+maxSize    


    void makeEmpty(){front=rear=0;}
    friend ostream& operator<< (ostream& os,const SeqQueue& rhs);//  

protected:
    int front,rear;
    T* elements;
    int maxSize;
};

template
bool SeqQueue::EnQueue(const T& x)
{
    if(IsFull())
        return false;
    elements[rear]=x;
    rear=(rear+1)%maxSize;//    ++rear
    return true;
}

template
bool SeqQueue::DeQueue(T& x)
{
    if(IsEmpty())
        return false;
    x=elements[front];
    front=(front+1)%maxSize;
    return true;
}

template
bool SeqQueue::getFront(T& x)const
{
    if(IsEmpty())
        return false;
    x=elements[front];
    return true;
}



template
ostream& operator<& rhs)
{
    os<
SeqQueue::SeqQueue(const SeqQueue& rhs)
{
    front=rhs.front;
    rear=rhs.rear;
    maxSize=rhs.maxSize;

    T* dest=new T[maxSize];
    T* src=rhs.elements;
    elements=dest;

    for(int i=0;i
SeqQueue& SeqQueue::operator=(const SeqQueue& rhs)
{
    delete[] elements;
    makeEmpty();

    front=rhs.front;
    rear=rhs.rear;
    maxSize=rhs.maxSize;

    T* dest=new T[maxSize];
    T* src=rhs.elements;
    elements=dest;

    for(int i=0;i

테스트 코드:

int main(int argc, char* argv[])
{
    SeqQueue s(5);
    int a=1,b=2,c=3,d=4,e=0;
    s.EnQueue(a);
    s.EnQueue(b);
    s.EnQueue(c);
    s.EnQueue(d);
    cout< s1(s),s2;
    cout<

테스트 결 과 는 다음 과 같다.

front=0 rear=4
elements: 1 2 3 4
front=2 rear=4
elements: 3 4
getSize(): 2
IsEmpty(): false
IsFull(): false
getFront(): 3
front=2 rear=4
elements: 3 4
front=2 rear=4
elements: 3 4
       . . .

주의사항:
1. 이 실현 은 동적 배열 에 저 장 된 순환 대기 열 로 논리 적 으로 하나의 링 을 구성 합 니 다.
2. rear 는 실제 팀 의 꼬리 위 치 를 가리 키 는 다음 위 치 를 가리 키 고 front 는 진정한 헤드 요소 가 있 는 위 치 를 가리킨다.
3. 초기 화 시 rear = front = 0
4. 빈 것 으로 추정: front = rear
5. 추정 가득: (rear + 1)% maxSize = front.
rear 가 front 의 이전 위 치 를 가리 키 면 대기 열 이 가득 차 있다 고 생각 하기 때문에 최대 max Size - 1 개의 요소 만 저장 할 수 있 습 니 다.이것 은 대열 이 비어 있다 는 추정 과 차 이 를 보이 기 위해 서다.
6. 대상 지정 1: front = (front + 1)% maxSize
7. 팀 끝 포인터 1: rear = (rear + 1)% max Size