队列遵循先进先出(FIFO)的规则,也是可以用数组或链表来描述
数组实现方式中,循环队列是个不错的方案,只是要注意插入新元素前要检查一下队列有没有满,否则空队列和满队列都会造成队首元素和队末元素的索引相同
template<class T>
class arrayQueue
{
public:
arrayQueue(int initialCapacity = 10);
~arrayQueue() { delete[] queue; }
bool empty() const { return theFront == theBack; }
int size() const
{
return (theBack - theFront + arrayLength) % arrayLength;
}
T& front()
{// return front element
if (theFront == theBack)
throw queueEmpty();
return queue[(theFront + 1) % arrayLength];
}
T& back()
{// return theBack element
if (theFront == theBack)
throw queueEmpty();
return queue[theBack];
}
void pop()
{// remove theFront element
if (theFront == theBack)
throw queueEmpty();
theFront = (theFront + 1) % arrayLength;
queue[theFront].~T(); // destructor for T
}
void push(const T& theElement);
private:
int theFront; // 1 counterclockwise from theFront element
int theBack; // position of theBack element
int arrayLength; // queue capacity
T* queue; // element array
};
下面是构造函数和插入元素
插入元素时要检查队列是否满了,满了就双倍数组长度并把所有元素按顺序平移到开头
template<class T>
arrayQueue<T>::arrayQueue(int initialCapacity)
{// Constructor.
if (initialCapacity < 1)
{
ostringstream s;
s << "Initial capacity = " << initialCapacity << " Must be > 0";
throw illegalParameterValue(s.str());
}
arrayLength = initialCapacity;
queue = new T[arrayLength];
theFront = 0;
theBack = 0;
}
template<class T>
void arrayQueue<T>::push(const T& theElement)
{// Add theElement to queue.
// increase array length if necessary
if ((theBack + 1) % arrayLength == theFront)
{// double array length
// allocate a new array
T* newQueue = new T[2 * arrayLength];
// copy elements into new array
int start = (theFront + 1) % arrayLength;
if (start < 2)
// no wrap around
copy(queue + start, queue + start + arrayLength - 1, newQueue);
else
{ // queue wraps around
copy(queue + start, queue + arrayLength, newQueue);
copy(queue, queue + theBack + 1, newQueue + arrayLength - start);
}
// switch to newQueue and set theFront and theBack
theFront = 2 * arrayLength - 1;
theBack = arrayLength - 2; // queue size arrayLength - 1
arrayLength *= 2;
queue = newQueue;
}
// put theElement at the theBack of the queue
theBack = (theBack + 1) % arrayLength;
queue[theBack] = theElement;
}
用链表描述也很简单
template<class T>
class linkedQueue : public queue<T>
{
public:
linkedQueue(int initialCapacity = 10)
{queueFront = NULL; queueSize = 0;}
~linkedQueue();
bool empty() const
{return queueSize == 0;}
int size() const
{return queueSize;}
T& front()
{
if (queueSize == 0)
throw queueEmpty();
return queueFront->element;
}
T& back()
{
if (queueSize == 0)
throw queueEmpty();
return queueBack->element;
}
void pop();
void push(const T&);
private:
chainNode<T>* queueFront; // pointer to queue front
chainNode<T>* queueBack; // pointer to queue back
int queueSize; // number of elements in queue
};
template<class T>
linkedQueue<T>::~linkedQueue()
{// Destructor.
while (queueFront != NULL)
{// delete front node
chainNode<T>* nextNode = queueFront->next;
delete queueFront;
queueFront = nextNode;
}
}
template<class T>
void linkedQueue<T>::pop()
{// Delete front element.
if (queueFront == NULL)
throw queueEmpty();
chainNode<T>* nextNode = queueFront->next;
delete queueFront;
queueFront = nextNode;
queueSize--;
}
template<class T>
void linkedQueue<T>::push(const T& theElement)
{// Add theElement to back of queue.
// create node for new element
chainNode<T>* newNode = new chainNode<T>(theElement, NULL);
// add new node to back of queue
if (queueSize == 0)
queueFront = newNode; // queue empty
else
queueBack->next = newNode; // queue not empty
queueBack = newNode;
queueSize++;
}
Comments NOTHING