1.概述

队列是逻辑上一维的线性数据结构。所以在队列的代码实现时候，很自然的采用一维数组来存储队列的元素。

队列是一种先进先出(First In First Out, FIFO)的线性表。

它只允许在一端执行插入操作，而在另一端执行删除操作。

允许执行插入操作的一端称为队尾，允许删除的一端称为队头。

由于在队列的实际运行中，发生频繁的进队和出队操作，需要设立队首head和队尾tail两个变量。head用于指示队首元素的位置，也就是队首元素在数组的位置下标。tail用于指示队尾元素的位置，也就是队尾元素在数组的位置下标。但在实际上，tail是指示队尾元素所在位置的下一个位置，也就是下一个进队元素的放置位置。

这样设定有三个好处：

讯享网

1. 方便计算对内有多少元素(tail-head就能得到队列当前元素的个数）
2. 方便判断队列是否为空(当head==tail时候，表示队列为空)
3. 在普通队列和循环队列中都便于判断队列是否已满

2.队列的操作

（1）队列的常用操作

1. 进队：当队列还没满的时候，一个元素进入队列
2. 出队：当队列不是空的时候，队首元素离开
3. 读取队首元素：当队列不空的时候，读取队首元素的值
4. 判断队列是否为空
5. 判断队列是否已满

（2）队列的不常用操作
6. 询问当前队列大小，即队列元素的个数
7. 初始化
有时为了调试代码，还写一个输出函数：output()从队首到队尾，逐个输出队列元素。

3.三种队列实现

/* 简单队列实现：不考虑循环再用那些用过的存储单元 优点：简洁 缺点：不通用 用一维数组来存储队列元素 用两个变量，分别指示队列的首元素和尾元素所在的位置 */ #include <iostream> using namespace std; const int MAXX = 5;//队列的大小。为了方便，这里特意设的很小，在实际应用中，应定义足够大或者足够用的大小 int quee[MAXX];//这里定义一个元素为整数类型的队列 int head;//队首元素所在的位置 int tail;//队尾元素所在的位置 //初始化队列quee void init() { 
    head=tail=0; } bool isFull() { 
    //队尾位置，到了数组末尾 if(tail>=MAXX) return true;//建议tail==MAXX 改为tail>=MAXX return false; } bool isEmpty() { 
    if(head == tail) return true; return false; } bool push(int x) { 
    if(isFull()) return false; quee[tail++] = x; return true; } //读取队首元素 //成功返回true，否则返回false bool getFront(int&v) { 
    if(isEmpty()) return false; v = quee[head]; return true; } void pop() { 
    if(isEmpty()) return; head++; } int main() { 
    init(); push(1); push(2); push(3); int x; cout<<"队列大小： "<<tail-head<<endl; while(!isEmpty()) { 
    getFront(x); cout<<x<<" "; pop(); } } // 队列大小： 3 // 1 2 3  

（2）循环队列，在简单队列基础上实现，重点是取模运算，提高空间利用率

讯享网/* 高效使用空间的实现：循环队列--考虑循环再用那些弃置的存储单元 用一维数组来模拟队列 用两个变量，分别指示队列的首元素和尾元素所在的位置 */ #include <iostream> #include <cstdio> using namespace std; const int MAXX = 6;//队列的大小。为了方便，这里特意设的很小，在实际应用中，应定义足够大或者足够用的大小 int quee[MAXX];//这里定义一个元素为整数类型的队列 int head;//队首元素所在的位置 int tail;//队尾元素所在的位置 //初始化队列quee void init() { 
    head=tail=0; } bool isFull() { 
    //如果tail的下一个位置与head相同则队列已满 //从而区分队列为空的情况，即rear==head的情况 //注意到，虽然这个时候队列中会有一个空的位置导致装不满 if((tail+1)%MAXX==head) return true;// return false; } bool isEmpty() { 
    if(head == tail) return true; return false; } bool push(int x) { 
    if(isFull()) return false; //如果队列已满，则返回false quee[tail] = x; tail = (tail+1)%MAXX;//通过取模运算实现元素的循环填充 return true; } //读取队首元素 //成功返回true，否则返回false bool getFront(int&v) { 
    if(isEmpty()) return false; v = quee[head]; return true; } //若队列不空则删除首元素x,并返回true， 否则返回false bool pop() { 
    if(isEmpty()) return false; head = (head+1)%MAXX; return true; } //求队列元素的个数 int getSize() { 
    return (tail-head+MAXX)%MAXX; } void output() { 
    for(int i = head;i!=tail; i=(i+1)%MAXX) { 
    printf("%d ",quee[i]); } printf("\n"); } int main() { 
    init(); push(11); push(12); push(13); push(14); push(15); output(); int outQueVal_1, outQueVal_2; getFront(outQueVal_1);//读取队首元素11 printf("outQueVal_1: %d\n", outQueVal_1);//预计输出11 pop(); getFront(outQueVal_2);//读取队首元素12 printf("outQueVal_2: %d\n", outQueVal_2);//预计输出12 pop(); push(16); //元素16应该保存在quee[5]中 push(17); //元素17应该保存在quee[0]中 push(18); //预计此时队列已满，不能再进队了 output(); //预计输出：13 14 15 16 17 } //11 12 13 14 15 //outQueVal_1: 11 //outQueVal_2: 12 //13 14 15 16 17 

（3）链表队列，用指针实现，空间利用率最高，但代码较繁琐，容易写错，一般情况下不建议使用

#include <cstdio> using namespace std; //队列元素节点 struct NODE { 
    int value; //存放队列元素的值 struct NODE *next; //指向下一个元素的指针 }; struct myQueue { 
    struct NODE *head; //指向队首元素 struct NODE *tail; //指向队尾元素 int cnt; //队列元素个数 }; void init(struct myQueue &q) { 
    q.head = q.tail = NULL; q.cnt = 0; } bool isEmpty(struct myQueue&q) { 
    if (0 >= q.cnt /*q.head==NULL*/) return true; return false; } void push(struct myQueue&q, int v) { 
    // struct NODE*tmp = (struct NODE*) malloc(1*sizeof(struct NODE)); struct NODE* tmp = new(struct NODE); if (!tmp) { 
    return; //这里省略了对new操作失败时候的善后处理 } tmp->value = v; tmp->next = NULL; if (q.cnt <= 0) //要区分是不是第一个元素 { 
    q.head = q.tail = tmp; } else { 
    q.tail->next = tmp; q.tail = tmp; } q.cnt++; } bool getFront(struct myQueue q, int&v) { 
    if (isEmpty(q)) return false; v = q.head->value; return true; } void pop(struct myQueue&q) { 
    if (isEmpty(q)) return; struct NODE* tmp = q.head; q.head = tmp->next; q.cnt--; delete tmp; //free(tmp); } void freeQueue(struct myQueue&q) { 
    while (q.head) { 
    struct NODE* tmp = q.head; q.head = q.head->next; delete tmp; //free(tmp); } q.head = q.tail = NULL; q.cnt = 0; } void output(struct myQueue q) { 
    for (struct NODE*i = q.head; i != NULL; i = i->next) { 
    printf("%d ", i->value); } printf("\n"); } int getSize(struct myQueue q) { 
    return q.cnt; } int main() { 
    struct myQueue q1; //定义一个队列 init(q1); // 初始化 push(q1, 1); //元素进队 push(q1, 2); push(q1, 3); push(q1, 4); push(q1, 5); printf("遍历：\t"); output(q1); //预计输出1 2 3 4 5 pop(q1); pop(q1); output(q1);//预期输出3 4 5 push(q1, 6); push(q1, 7); push(q1, 8); output(q1);//预期输出3 4 5 6 7 8 //提取对头数据测试 int quFrontVal = 0; getFront(q1, quFrontVal); printf("%d\n", quFrontVal);//预计输出3 freeQueue(q1);//切记释放队列 //设置NULL与测试NULL init(q1); if(isEmpty(q1)) printf("队列空"); else printf("队列非空"); push(q1, 1); push(q1, 2); push(q1, 3); printf("%d\n", getSize(q1));//预计输出3 push(q1, 4); push(q1, 5); printf("%d\n", getSize(q1));//预计输出5 push(q1, 6); push(q1, 7); push(q1, 8); push(q1, 9); printf("%d\n", getSize(q1));//预计输出9 output(q1);//预计1 2 3 4 5 6 7 8 9 freeQueue(q1);//切记释放队列 return 0; }