链式队列(LinkedQueue)
template<class T>
class LinkedQueue {
struct Node {
T data;
Node* next;
Node(const T& x){ data=x; next=nullptr; }
};
Node* frontPointer;
Node* rearPointer;
int n;
public:
LinkedQueue(){
frontPointer=rearPointer=nullptr;
n=0;
}
~LinkedQueue(){ clear(); }
bool empty() const { return frontPointer==nullptr; }
int size() const { return n; }
void enqueue(const T& x){
Node* q=new Node(x);
if(rearPointer==nullptr){
frontPointer=rearPointer=q;
}else{
rearPointer->next=q;
rearPointer=q;
}
n++;
}
bool dequeue(){
if(empty()) return false;
Node* q=frontPointer;
frontPointer=frontPointer->next;
delete q;
n--;
if(frontPointer==nullptr)
rearPointer=nullptr;
return true;
}
T& front(){
if(empty()) throw underflow_error("LinkedQueue::front on empty queue");
return frontPointer->data;
}
T& back(){
if(empty()) throw underflow_error("LinkedQueue::back on empty queue");
return rearPointer->data;
}
void clear(){
while(!empty()) dequeue();
}
};
工程细节
- 入队接在
rearPointer 后,出队删除 frontPointer,两者均为 O(1);队尾的 next 始终为空。
- 首次入队同时设置首尾指针。删除最后一个元素后,
frontPointer 和 rearPointer 必须同时为 nullptr,否则尾指针会悬空。
- 清空后再次入队应走空队列分支;空队列读取
front() 或 back() 抛出 underflow_error。
跳转
下一个:链式串
上一个:链式栈