Queue(啊哈算法)

下面摘录啊哈算法中的重点片段及queue实现代码，同时总结数据结构队列的常见用法

队列概念

*队列是一种特殊的线性结构，它只允许在队列的首部（head）进行删除操作，这称为“出队”，而在队列 的尾部（tail）进行插入操作，这称为“入队”。当队列中没有元素时（即head==tail），称为 空队列。

*队列符合先进先出的原则（FIFO）

*队列是广度优先搜索以及队列优化的Bellman-Ford 最短路算法的核心数据结构

用结构体类型封装

#include <cstdio> struct queue{ int data[100]; //队列的主体，用来存储内容 int head; //队头 int tail; //队尾 } int main(){ struct queue q; int i; //初始化队列 q.head = 0; q.tail = 0; for(i=0; i<9; i++){ //依次向队列插入9个数 scanf("%d", &q.data[q.tail]); q.tail++; } while(q.head < q.tail){ //打印队首并将队首出队 printf("%d", q.data[q.head]); q.head++; //先将新队首的数添加到队尾 q.data[q.tail] = q.data[q.head]; q.tail++; //再将队首出队 q.head++; } return 0; }

STL–Queue(FIFO)

定义queue对象的示例代码如下：

#include <queue> queue<int> q;

queue的基本操作

1.入队：如q.push(x):将x元素接到队列的末端； 2.出队：如q.pop() 弹出队列的第一个元素，并不会返回元素的值； 3.访问队首元素：如q.front(); 4.访问队尾元素，如q.back(); 5.访问队中的元素个数，如q.size();