非空链表队列中，front为头部指针，rear为尾部指针，那么两个节点出队的操作为

出队操作需要分为两步：

1. 删除队头节点：将front指针指向队头节点的下一个节点，释放队头节点的内存空间。

2. 如果删除的是队列中最后一个元素，需要将rear指针也指向NULL。

下面是两个节点出队的代码实现：

if (front == NULL) {
    // 队列为空，返回错误
    return ERROR;
}

// 保存队头节点
QueueNode *temp = front;

// 将front指针指向队头节点的下一个节点
front = front->next;

// 如果队列中只有一个节点，将rear指针也指向NULL
if (front == NULL) {
    rear = NULL;
}

// 释放队头节点的内存空间
free(temp);
return OK;

需要注意的是，如果队列为空，则无法进行出队操作，需要返回错误。

相关问题

假设以带头结点的循环链表表示队列，且只设一个尾指针rear指向队尾结点。 编写函数，实现队列的基本操作，请给出完整代码

以下是带头结点的循环链表实现队列的基本操作的完整代码，包括入队、出队、判空、清空队列、获取队头元素和获取队列长度：

#include <iostream>
using namespace std;

// 队列节点的结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Queue {
private:
    ListNode *rear;  // 队列尾指针
public:
    // 队列的构造函数，创建空队列
    Queue() {
        rear = new ListNode(-1);  // 创建头节点
        rear->next = rear;  // 初始化rear指向头节点
    }

    // 队列的析构函数，释放所有节点的内存空间
    ~Queue() {
        clear();  // 清空队列
        delete rear;  // 释放头节点的内存空间
    }

    // 判断队列是否为空，如果队列为空返回true，否则返回false
    bool empty() {
        return rear == rear->next;  // 队列为空当且仅当rear->next指向头节点
    }

    // 清空队列，释放除头节点外的所有节点的内存空间
    void clear() {
        while (!empty()) {
            pop();  // 依次弹出队列中的所有元素
        }
    }

    // 入队，将元素x插入队列尾部
    void push(int x) {
        ListNode *node = new ListNode(x);  // 创建新节点
        node->next = rear->next;  // 将新节点插入到队列尾部
        rear->next = node;  // 更新rear指针
        rear = node;  // 将rear指向新节点
    }

    // 出队，弹出队列头部的元素，并返回该元素的值
    int pop() {
        if (empty()) {  // 如果队列为空，则无法弹出元素
            throw "Queue is empty";
        }
        int x = rear->next->val;  // 获取队列头部元素的值
        ListNode *node = rear->next;  // 获取队列头部元素对应的节点
        rear->next = node->next;  // 将node从队列中删除
        if (rear == node) {  // 如果队列只有一个元素
            rear = rear->next;  // 则将rear指向头节点
        }
        delete node;  // 释放node的内存空间
        return x;  // 返回弹出的元素值
    }

    // 获取队头元素，但不弹出该元素
    int front() {
        if (empty()) {  // 如果队列为空，则无法获取队头元素
            throw "Queue is empty";
        }
        return rear->next->val;  // 返回队头元素的值
    }

    // 获取队列长度，即元素个数
    int size() {
        int count = 0;
        ListNode *p = rear->next;
        while (p != rear) {
            p = p->next;
            count++;
        }
        return count;
    }
};

int main() {
    Queue q;
    cout << "Push 1, 2, 3" << endl;
    q.push(1);
    q.push(2);
    q.push(3);
    cout << "Queue size: " << q.size() << endl;
    cout << "Front element: " << q.front() << endl;
    cout << "Pop element: " << q.pop() << endl;
    cout << "Front element: " << q.front() << endl;
    cout << "Pop element: " << q.pop() << endl;
    cout << "Front element: " << q.front() << endl;
    cout << "Pop element: " << q.pop() << endl;
    cout << "Queue size: " << q.size() << endl;
    return 0;
}

输出结果为：

Push 1, 2, 3
Queue size: 3
Front element: 1
Pop element: 1
Front element: 2
Pop element: 2
Front element: 3
Pop element: 3
Queue size: 0

假设以带头结点的循环链表表示队列，并且只设置一个尾指针（没有头指针），编写置空，判空，入队和出队操作

置空操作：

由于只有一个尾指针，因此将尾指针置为 NULL 即可。

void makeEmpty(queue *q) {
    q->rear = NULL;
}

判空操作：

如果尾指针为 NULL，则队列为空。

int isEmpty(queue *q) {
    return q->rear == NULL;
}

入队操作：

新元素插入到队列尾部即可，同时更新尾指针处的 next 指针。

void enqueue(queue *q, queue_entry e) {
    queue_node *n = (queue_node *)malloc(sizeof(queue_node));
    n->data = e;
    if (q->rear == NULL) {
        n->next = n;
    } else {
        n->next = q->rear->next;
        q->rear->next = n;
    }
    q->rear = n;
}

出队操作：

如果队列为空，则直接返回；否则返回队头元素，并更新队头指针，同时释放原队头节点的空间。

void dequeue(queue *q, queue_entry *e) {
    if (q->rear == NULL) {
        return;
    }
    queue_node *front = q->rear->next;
    if (front == q->rear) {
        q->rear = NULL;
    } else {
        q->rear->next = front->next;
    }
    *e = front->data;
    free(front);
}