numberdeque.cpp

算法结构的编程

//student ID: 600259933
//student Name: Yang Da
//student Email: [e-mail]
#include "NumberDeque.h"
#include <string>
using std::string;
namespace NumberStructures {
void NumberDeque::ShuffleElements(int newFirst, int newLast) {
    if (newFirst < firstElement) {
        int tmp = newFirst;
        while (firstElement <= lastElement)
            arrayStore[tmp++] = arrayStore[firstElement++];
        firstElement = newFirst;
        lastElement = newLast;
    } else if (newLast > lastElement) {
        int tmp = newLast;
        while (lastElement >= firstElement)
            arrayStore[tmp--] = arrayStore[lastElement--];
        firstElement = newFirst;
        lastElement = newLast;
    }
    // else the elements are already in the correct location
}

void NumberDeque::BalanceFront() {
    // Calculate how many spare slots should be to centre the elements
    int frontGap = firstElement;
    int rearGap = DequeSize - lastElement - 1;
    int avgGap = (frontGap + rearGap) / 2;
// Calculate the new first and last elements
    int newFirst = avgGap;
    int newLast = DequeSize - avgGap - 1;

    // Allow for an odd number of elements)
    if ((frontGap + rearGap) % 2 == 1)
        newFirst++;

    ShuffleElements(newFirst, newLast);
}

void NumberDeque::BalanceRear() {
    // Calculate how many spare slots should be to centre the elements
    int frontGap = firstElement;
    int rearGap = DequeSize - lastElement - 1;
    int avgGap = (frontGap + rearGap) / 2;

    // Calculate the new first and last elements
    int newFirst = avgGap;
    int newLast = DequeSize - avgGap - 1;

    // Allow for an odd number of elements)
    if ((frontGap + rearGap) % 2 == 1)
        newLast--;

    ShuffleElements(newFirst, newLast);
}
NumberDeque::NumberDeque() {
//	arrayStore = new int[DequeSize];
    firstElement = DequeSize/2 ;
    lastElement = firstElement-1;
}
void NumberDeque::PushFront(int value) {
    if (Full())
        throw string("Dqueue Overflow!");
    else if (Empty()) {
        lastElement = firstElement;
        arrayStore[firstElement]=value;
    } else {

        arrayStore[firstElement++]=value;
        BalanceFront();
    }
}
void NumberDeque::PushRear(int value) {
    if (Full())
        throw string("Dqueue Overflow!");
    else if (Empty()) {
        firstElement=lastElement ;
        arrayStore[++lastElement]=value;
    } else {

        arrayStore[lastElement]=value;
        BalanceRear();
    }
}
int NumberDeque::PopFront() {
    if (Empty())
        throw string("Dqueue underflow!");
    else {
        int front = arrayStore[++firstElement];
        BalanceFront();
        return front;
    }

}
int NumberDeque::PopRear() {
    if (Empty())
        throw string("Dqueue underflow!");
    else {
        int rear = arrayStore[--lastElement];
        BalanceRear();
        return rear;
    }
}
int NumberDeque::Front() {
    return arrayStore[firstElement];
}
int NumberDeque::Rear() {
    return arrayStore[lastElement];
}
bool NumberDeque::Empty() {
    return Count()==0;
}
bool NumberDeque::Full() {
    return firstElement-lastElement==DequeSize;
}
int NumberDeque::Count() {
    return  lastElement-firstElement +1;
}
}