加载中

手写数据结构·线性表16:链式队列

链式队列(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。

跳转

下一个:链式串

上一个:链式栈

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/c37d35d4/

版权声明:本文采用 CC BY-NC-SA 4.0 许可协议