搭建博客网站seowhy教研室

队列的概念

队列，符合先进先出特点的一种数据结构，是一种特殊的线性表，但它不像线性表一样可以任意插入和删除操作，而是只允许在表的一端插入，也就是在队列的尾部进行插入；只允许在表的另一端进行删除，也就是在队列的头部进行删除。

以下的实现是顺序队列（存储空间在内存上是连续的队列）

队列的实现

队列的结构定义

#define MAX_SIZE 20            //队列的最大容量
typedef int DateElem;   typedef struct _Queue
{DateElem date[MAX_SIZE];int head;				//头指针int tail;				//尾指针
}squeue;

队列的初始化

void InitQueue(squeue* sq)
{if (!sq) return;sq->head = 0;sq->tail = 0;
}

销毁（清空）队列

和队列的初始化有点类似哈哈。

bool DestoryQueue(squeue* sq)
{if (!sq) return false;sq->head = 0;sq->tail = 0;return true;
}

判满

bool IsFull(squeue* sq)
{if(!sq) return false;    //防御性编程if (sq->tail >= MAX_SIZE ) //每入队一个元素，sq->tail++，入队了MAX_SIZE个元素刚好sq->tail等于MAX_SIZE{return true;}else{return false;}
}

判空

可以从 队列的初始状态（空队列）和 入队后再出队 中找到判空的条件。

bool IsEmpty(squeue* sq)
{if (!sq) return false;if (sq->head == sq->tail) //两个指针之间没有元素{return true;}else{return false;}
}

入队

bool EnterQueue(squeue* sq, DateElem e)
{if (IsFull(sq)){cout << "无法插入元素"<<e<<"，队列已满。" << endl;return false;}sq->date[sq->tail ] = e;  //尾部插入sq->tail++;               //尾指针指向下一块未被使用区域 return true;
}

出队

出队的方式有两种，一种是乾坤大挪移，每出队一个元素都要将后面所有的元素往前挪，十分浪费时间。另一种是舍弃空间来达到快速出队元素。

第一种

bool PopQueue(squeue* sq, DateElem* date)
{if (!sq || IsEmpty(sq)) return false;*date = sq->date[sq->head];         //返回出队的元素for (int i = sq->head + 1; i < sq->tail; i++){sq->date[i - 1] = sq->date[i]; //从第二个结点开始，将第二个结点赋值给第一个结点……}sq->tail--;    //别忘记return true;
}

第二种

bool PopQueue2(squeue* sq,DateElem *date)
{if (!sq || IsEmpty(sq)) return false;//不是无限制的出队if (sq->head >= MAX_SIZE) return false;*date = sq->date[sq->head];sq->head++;return true;
}

本来头指针一直指向下标为 0 的地方，但是这种出队方式会导致头指针一直向后移动，出现“假溢出”，明明队列还有空间存储，可是却无法插入元素了。如下图：

造成了空间的浪费，不过在比赛时为了通过题目，这点空间浪费无所谓，使用顺序队列非常容易构建。

 打印队列

和链表的打印一样。

bool PrintQueue(squeue* sq)
{if (!sq) return false;for (int i = sq->head; i < sq->tail; i++){printf("%d ", sq->date[i]);}return true;
}

获取队首元素

int GetHeadElem(squeue* sq)
{if (!sq || IsEmpty(sq)) return 0; //指针存在 或者 队列不为空return sq->date[sq->head];        //在队头不出队的清况下，返回队首元素
}

获取队列长度

int GetLength(squeue* sq)
{if (!sq) return 0;return sq->tail - sq->head; //最开始为空队列sq->tail - sq->head 为 0 ，依次类推得到长度
}

主函数

我已经写好了测试的方法，可以尽情调试看看代码的正确性。

int main(void)
{squeue* sq = new squeue;DateElem* s = new DateElem;InitQueue(sq);DateElem e = 0;int choose = -1;while (choose != 0){cout << "1.入队" << endl<< "2.出队" << endl<< "3.打印队列" << endl<< "4.获取队首元素" << endl<< "5.获取队列长度" << endl<< "6.销毁队列" << endl<< "0.退出" << endl;cin >> choose;switch (choose){case 1:cout << "请输入要入队的元素：";cin >> e;if (EnterQueue(sq, e)){cout << "入队成功" << endl;}else{cout << "入队失败" << endl;}break;case 2:if (PopQueue(sq, s)){cout << "出队的元素是：" << *s << endl;}else{cout << "出队失败" << endl;}break;case 3:cout << "队列中的元素是：";PrintQueue(sq);cout << endl;break;case 4:cout << "队首元素是：" << GetHeadElem(sq) << endl;break;case 5:cout << "队列的长度是：" << GetLength(sq) << endl;break;case 6:if (DestoryQueue(sq)){cout << "队列已销毁" << endl;}else{cout << "队列不存在" << endl;}break;case 0:cout << "退出成功" << endl;break;default:cout << "输入非法" << endl;break;}}return 0;
}

好了再见！