队列的顺序存储结构（参考前面文章：http://blog.itpub.net/29876893/viewspace-1847566/）比链式较为复杂些，顺序存储结构要构造循环队列;但是链式就不需要，存储元素的内存地址是随机的，用的时候再向os申请内存空间。链式存储结构中需要两个flag工作指针，过程相对较简单些。但是其中也有需要注意的细节。下面给出实现代码：

点击(此处)折叠或打开

#include<iostream>
using namespace std;
typedef struct Queue{ //队列结点结构
char ch;
Queue *next;
}*queue;
typedef struct flaging { //flag指针结构
queue front, rear;
}*flag;
void initSqueue(queue);
void initflag(flag);
void createSqueue(queue, flag);
void pushSqueue(queue, flag, char);
void popSqueue(queue, flag);
void throughSqueue(queue, flag);
void initSqueue(queue first) {
first = new Queue;
}
void initflag(flag fg) {
fg = new flaging;
}
void createSqueue(queue q,flag fg){
cout << "输入入队的元素:" << endl;
queue p,head;
head = q;
for (char ch; cin >> ch, ch != '#';) {
p = new Queue;
head->next=p;
p->ch = ch;
head = p;
head->next = NULL;
}
fg->front=q->next;
fg->rear = head;
}
void pushSqueue(queue q,flag fg,char ch) { //入队
q = fg->rear;
q->next = new Queue;
q->next->ch = ch;
q->next->next = NULL;
fg->rear = q->next;
}
void popSqueue(queue q,flag fg){ //出队
q = fg->front;
cout << q->ch;
fg->front = q->next;
delete q;
}
void throughSqueue(queue q, flag fg) {//遍历队列，打印在队列中的元素
q = fg->front;
do{
cout << q->ch << " ";
q = q->next;
} while (q != NULL);
}
int main(){
Queue q;
flaging fg;
initSqueue(&q);
initflag(&fg);
createSqueue(&q, &fg);
pushSqueue(&q, &fg, 'F');
cout << "出队的元素是：";
popSqueue(&q, &fg);
cout << endl;
cout << "出队的元素是：";
popSqueue(&q, &fg);
cout << endl;
cout << "出队的元素是：";
popSqueue(&q, &fg);
cout << endl;
cout << "在队列中的元素是:" << endl;
throughSqueue(&q, &fg);
cout << endl;
}

运行结果：

该过程用下面图示简单的表示一下：

有朋友会问，为什么最后指向NULL结点,添加这一步似乎对程序的可读性没有带来多少好处，但是这一步关键之处，在throughSqueue(queue q, flag fg)中，遍历整个队列时，用来判断遍历整个队列时退出的条件，对于该函数作用十分重要，但是如果不实现该函数功能的话，那么没有必要再构造出NULL结点。队列的性质是从front指针处出队列，从rear指针处入队列，上面的示意图很清楚的看出这一性质，front，rear可以看成记忆指针，可以准确的告诉q指针该到什么位置工作，q指针可以看成是移动的。整个过程，画出图会很清晰，相信读者会有更精彩的功能实现。

ITPub博客

队列的链式存储结构

最新文章