데이터 구조의 대기 열 (5)

본 고 는 'Deque' 의 두 가지 실현 인 'DequeAsArray' 와 'DequeAsLinkedList' 를 배 울 것 이다.
1. DequeAsArray (링크 열기 클릭)
        코드 재 활용 을 향상 시 키 기 위해 여 기 는 다 중 계승 방식 으로 이 루어 집 니 다. 다음 과 같 습 니 다.

#pragma once
#include "Deque.h"
#include "QueueAsArray.h"

class DequeAsArray : public Deque, public QueueAsArray
{
public:
    DequeAsArray(unsigned int);
    ~DequeAsArray();

    void Purge();
    void Accept(Visitor &) const;

    Object & Head() const;
    Object & Tail() const;
    void Enqueue(Object &);
    void EnqueueHead(Object&);
    void EnqueueTail(Object &);
    Object & Dequeue();
    Object & DequeueHead();
    Object & DequeueTail();
};

        'Effective C + +' 의 '다 중 상속' 에 관 한 조항 을 참고 하여 본 사례 는 Public 상속 과 private 상속 조합 방식 도 사용 할 수 있다.그 중에서 DequeAsArray 의 인 터 페 이 스 는 주로 Deque 에서 계승 되 고 QueueAsArray 에서 계승 된다.

#include "stdafx.h"
#include "DequeAsArray.h"


DequeAsArray::DequeAsArray(unsigned int size)
    :QueueAsArray(size)
{
}


DequeAsArray::~DequeAsArray()
{
}

void DequeAsArray::Purge()
{
    QueueAsArray::Purge();
}

void DequeAsArray::Accept(Visitor & visitor) const
{
    QueueAsArray::Accept(visitor);
}

Object & DequeAsArray::Head() const
{
    return QueueAsArray::Head();
}

Object & DequeAsArray::Tail() const
{
    if (count == 0)
        throw std::domain_error("deque is empty");
    return *array[tail];
}

void DequeAsArray::Enqueue(Object& object)
{
    Deque::Enqueue(object);
}

void DequeAsArray::EnqueueHead(Object & object)
{
    if (count == array.Length())
        throw std::domain_error("deque is full");
    if (head-- == 0)
        head = array.Length() - 1;
    array[head] = &object;
    ++count;
}

void DequeAsArray::EnqueueTail(Object & object)
{
    QueueAsArray::Enqueue(object);
}

Object & DequeAsArray::Dequeue()
{
    return Deque::Dequeue();
}

Object & DequeAsArray::DequeueHead()
{
    return QueueAsArray::Dequeue();
}

Object & DequeAsArray::DequeueTail()
{
    if (count == 0)
        throw std::domain_error("deque is empty");
    Object & result = *array[tail];
    if (tail-- == 0)
        tail = array.Length() - 1;
    --count;
    return result;
}

2. DequeAsLinkedList (클릭 하여 링크 열기)
        마찬가지 로 DqueAsLinkedList 도 다 중 계승 을 사용 합 니 다. 다음 과 같 습 니 다.

#pragma once
#include "Deque.h"
#include "QueueAsLinkedList.h"

class DequeAsLinkedList : public Deque, private QueueAsLinkedList
{
public:
    DequeAsLinkedList();
    ~DequeAsLinkedList();

    void Purge();
    void Accept(Visitor &) const;

    Object & Head() const;
    Object & Tail() const;
    void Enqueue(Object &);
    void EnqueueHead(Object&);
    void EnqueueTail(Object &);
    Object & Dequeue();
    Object & DequeueHead();
    Object & DequeueTail();
};

        구현 코드 는 다음 과 같 습 니 다:

#include "DequeAsLinkedList.h"


DequeAsLinkedList::DequeAsLinkedList()
{
}


DequeAsLinkedList::~DequeAsLinkedList()
{
    Purge();
}

void DequeAsLinkedList::Purge()
{
    QueueAsLinkedList::Purge();
}

void DequeAsLinkedList::Accept(Visitor & visitor) const
{
    QueueAsLinkedList::Accept(visitor);
}

Object & DequeAsLinkedList::Head() const
{
    return QueueAsLinkedList::Head();
}

Object & DequeAsLinkedList::Tail() const
{
    if (count == 0)
        throw std::domain_error("deque is empty");
    return *list.Last();
}

void DequeAsLinkedList::Enqueue(Object& object)
{
    Deque::Enqueue(object);
}

void DequeAsLinkedList::EnqueueHead(Object & object)
{
    list.Prepend(&object);
    ++count;
}

void DequeAsLinkedList::EnqueueTail(Object & object)
{
    QueueAsLinkedList::Enqueue(object);
}

Object & DequeAsLinkedList::Dequeue()
{
    return Deque::Dequeue();
}

Object & DequeAsLinkedList::DequeueHead()
{
    return QueueAsLinkedList::Dequeue();
}

Object & DequeAsLinkedList::DequeueTail()
{
    if (count == 0)
        throw std::domain_error("deque is empty");
    Object & result = *list.Last();
    list.Extract(&result);
    --count;
    return result;
}

        그것 의 실현 은 상대 적 으로 더욱 간단 해 야 한다.