数据结构——链队列

链式队列的实现思想同顺序队列类似，只需创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素

图 1 所示为链式队列的初始状态，此时队列中没有存储任何数据元素，因此 top 和 rear 指针都同时指向头节点。

在创建链式队列时，强烈建议初学者创建一个带有头节点的链表，这样实现链式队列会更简单。

由此，我们可以编写出创建链式队列的 C 语言实现代码为:

//链表中的节点结构

typedef struct QNode{
    int data;
    struct QNode * next;
}QNode;
//创建链式队列的函数
QNode * initQueue(){
    //创建一个头节点
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    //对头节点进行初始化
    queue->next=NULL;
    return queue;
}

链式队列数据入队
链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：

将该数据元素用节点包裹，例如新节点名称为 elem；
与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
最后移动 rear 指针指向该新节点，即 rear=elem；
由此，新节点就入队成功了。

例如，在图 1 的基础上，我们依次将 {1,2,3} 依次入队，各个数据元素入队的过程如图 2 所示:

数据元素入链式队列的 C 语言实现代码为：

QNode* enQueue(QNode * rear,int data){
    //1、用节点包裹入队元素
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->data=data;
    enElem->next=NULL;
    //2、新节点与rear节点建立逻辑关系
    rear->next=enElem;
    //3、rear指向新节点
    rear=enElem;
    //返回新的rear，为后续新元素入队做准备
    return rear;
}

链式队列数据出队 当链式队列中，有数据元素需要出队时，按照 “先进先出”
的原则，只需将存储该数据的节点以及它之前入队的元素节点按照原则依次出队即可。这里，我们先学习如何将队头元素出队。

链式队列中队头元素出队，需要做以下 3 步操作：

通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点； 将 p 节点（即要出队的队头节点）从链表中摘除； 释放节点
p，回收其所占的内存空间； 我们将元素 1 和 2 出队，

链式队列中队头元素出队的 C 语言实现代码为：

void DeQueue(QNode * top,QNode * rear){
    if (top->next==NULL) {
        printf("队列为空");
        return ;
    }
    // 1、
    QNode * p=top->next;
    printf("%d",p->data);
    top->next=p->next;
    if (rear==p) {
        rear=top;
    }
    free(p);
}

c++实现链式链表

#include <stdio.h>
#include <stdlib.h>
typedef struct QNode{
    int data;
    struct QNode * next;
}QNode;
QNode * initQueue(){
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    queue->next=NULL;
    return queue;
}
QNode* enQueue(QNode * rear,int data){
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->data=data;
    enElem->next=NULL;
    //使用尾插法向链队列中添加数据元素
    rear->next=enElem;
    rear=enElem;
    return rear;
}
QNode* DeQueue(QNode * top,QNode * rear){
    if (top->next==NULL) 
    {
        printf("\n队列为空");
        return rear;
    }
    QNode * p=top->next;
    printf("%d ",p->data);
    top->next=p->next;
    if (rear==p) {
        rear=top;
    }
    free(p);
    return rear;
}
int main() {
    QNode * queue,*top,*rear;
    queue=top=rear=initQueue();//创建头结点
    //向链队列中添加结点，使用尾插法添加的同时，队尾指针需要指向链表的最后一个元素
    rear=enQueue(rear, 1);
    rear=enQueue(rear, 2);
    rear=enQueue(rear, 3);
    rear=enQueue(rear, 4);
    //入队完成，所有数据元素开始出队列
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    return 0;
}

运行结果为：

1 2 3 4
队列为空
0

c++实现

#include <iostream>
using namespace std;

template <typename T>
// 结点
struct Node
{
	T value;
	Node<T>* next;
	Node() {}
	Node(const T& val, Node<T>* theNext):value(val),next(theNext) {}
};

template <typename T>
class Queue
{
private:
	Node<T>* m_front;
	Node<T>* m_rear;
	int m_size;
public:
	Queue() {
		m_front = m_rear = NULL;
		m_size = 0;
	}
	
	// 向队中加入元素
	void EnQueue(const T& e) {
		// 从堆空间申请一个结点并初始化
		Node<T>* node = new Node<T>(e, NULL);
		
		if (node != NULL) {
			// 如果此时队为空
			if (m_size == 0)
				m_front = node;
			else
				m_rear->next = node;
			m_rear = node;
			m_size++;
		}
	}

	// 删除队头元素
	bool DeQueue() {
		if (m_front == NULL)
			return false;
		else {
			Node<T>* toDel = m_front->next;
			delete m_front;
			// 队头指针后移
			m_front = toDel;
			m_size--;
			return true;
		}
	}
	
	T front() {
		if (m_front == NULL)
			return -1;
		else
			return m_front->value;
	}

	bool empty() const {
		return m_size == 0;
	}

	int size() const {
		return m_size;
	}

};

int main()
{
	Queue<int> q;
	for (int i = 0; i < 10; i++)
		q.EnQueue(i);

	cout << "入队完成之后元素个数为： " << q.size() << endl;
	for (int i = 0; i < 10; i++) {
		cout << "此时队头元素为: " << q.front() << endl;
		q.DeQueue();
	}
	cout << "出队完成之后元素个数为:  " << q.size() << endl;
	return 0;
}