【数据结构与算法分析】链队列

链队列（linked queues）

（1）运算实现

  为了使入队操作在队列为空和不为空时的操作一致，特别设置了一个不存放元素值的附加结点（头结点）。

  头文件：

#ifndef QUEUE_H
#define QUEUE_H

template <class Type>
struct node {
Type data;
node *next;
};

template <class Type>
class queue {
public:
queue();//构造函数初始化（C++11可以在类中初始化）
~queue();//析构函数用于释放队列全部内存
bool empty();//判断队列是否为空
void get_front(Type &x);//取对头
void append(const Type x);//入队
void serve();//出队
void show();//打印队列数据
private:
node<Type> *front, *rear;
};

template <class Type>
queue<Type>::queue() {
front = new node<Type>;
front->next = NULL;
rear = front;
}
template <class Type>
bool queue<Type>::empty() {
return front == rear;
}
template <class Type>
void queue<Type>::get_front(Type &x) {
if (!empty())
x = front->next->data;
}
template <class Type>
void queue<Type>::append(const Type x) {
node<Type> *u = new node<Type>;
u->data = x;
u->next = NULL;
rear->next = u;
rear = u;
}
template <class Type>
void queue<Type>::serve() {
if (!empty()) {
node<Type> *u = new node<Type>;
u = front->next;
front->next = u->next;
delete u;
}
if (front->next == NULL)
rear = front;
}
template <class Type>
void queue<Type>::show() {
if (!empty()) {
node<Type> *u = front->next;
while (u != NULL) {
cout << u->data << " ";
u = u->next;
}
cout << endl;
}
}
template <class Type>
queue<Type>::~queue() {
while (!empty())
serve();
delete front;
}

#endif

（2）应用实例

  输入一列数字，输出该队列

  源代码：

#include<iostream>
#include"queue.h"
using namespace std;

int main() {
int x;
queue<int> q;
while (cin >> x)
q.append(x);
cin.clear();
q.show();
cin.get();
}

  运行截图：