链式队列

【概述】

链式队列是采取链式存储的队列，其不存在队列满而导致上溢的情况，通常设计为一个带头结点的单链表，其有两个指针，队头指针向队头结点，尾指针指向队尾结点

链式队列的实现类如下：

template <typename T> 
struct LNode {      //单链表结点
    T data;         //数据域
    LNode<T> *next; //指针域
};
template <typename T> 
class LinkQueue {
  public:
    LinkQueue();          //初始化队
    int getLen();         //求队长
    bool empty();         //判空
    bool pop(T &elem);    //出队
    bool push(T elem);    //入队
    bool getTop(T &elem); //取队首
    void print();         //输出
  private:
    LNode<T> *head;       //队首指针
    LNode<T> *tail;       //队尾指针
    int len;              //队列长度
};

【初始化】

链式队列被设计为带头结点的单链表，因此其头指针 head 的初始化与带头结点的单链表相似，只是要注意令尾指针 tail 的指向与 head 相同，并给队长 len 赋 $0$ 值即可

template <typename T> 
LinkQueue<T>::LinkQueue() { //初始化队列
    head = (LNode<T> *)malloc(sizeof(LNode<T>));
    tail = head;
    head->next = NULL;
    len = 0;
}

【求队长】

由于数据结构中封装了队长 len，因此在求队长时，直接输出 len 即可

template <typename T> 
int LinkQueue<T>::getLen() { //求队长
    return len;
}

【判空】

由于 tail 指向队尾元素的下一位置，即接下来要插入的位置，因此在判空时，只需判断队尾指针与队头指针是否相同即可

template <typename T> 
bool LinkQueue<T>::empty() { //判空
    if (head == tail)
        return true;
    return false;
}

【出队】

在出队时，首先进行下溢判断，再令队长 len-1，然后将队首结点释放，最后释放结点空间即可，要注意的是，如果要出队的是最后一个结点，要令尾指针 tail 与头指针 head 指向相同

template <typename T> 
bool LinkQueue<T>::pop(T &elem) { //出队
    if (empty()) //下溢判断
        return false;
    //队长-1
    len--; 
    //将队首结点断链
    LNode<T> *p = head->next;
    elem = p->data;
    head->next = p->next;
    //最后一个结点
    if (tail == p) 
        tail = head;
    //释放队首结点空间
    free(p);
    return true;
}

【入队】

在入队时，首先令队长 len+1，之后为新结点赋值，再连接到队尾

template <typename T> 
bool LinkQueue<T>::push(T elem) { //入队
    LNode<T> *p = (LNode<T> *)malloc(sizeof(LNode<T>));
    if (p == NULL) //空间分配失败
        return false;
    //队长+1
    len++;
    //为新结点赋值
    p->data = elem;
    p->next = NULL;
    //连接到队尾
    tail->next = p;
    tail = p;
    return true;
}

【取队头】

在取队首元素时，先进行下溢判断，然后直接取队首指针 head 指向头结点的下一元素的值即可

template <typename T> 
bool LinkQueue<T>::getTop(T &elem) { //取队首
    if (empty()) //下溢判断
        return false;
    elem = head->next->data;
    return true;
}

【输出】

在输出时，从队首开始，将队列中所有元素依次出队，进行输出即可

template <typename T> 
void LinkQueue<T>::print() { //输出
    int elem;
    while (!empty()) { //将所有元素依次出队进行输出
        pop(elem);
        cout << elem << " ";
    }
    cout << endl;
}