Learning Key Word -2

Keyword

 2017/12/13

数据结构

队列

定义：只允许在表的一端插入，在另一端删除。
- 允许插入的一端叫做队尾(rear), 允许删除的一端叫做队头(front)
- 与栈对比，队列为FIFO。栈为LIFO
队列的存储方式
- 基于数组
  - 可能会假溢出。因为维护的front指针与rear不得不不断的后移。从而使得数组空间前部可能会遭到极大的浪费。
循环队列 — 应对假溢出
- front = (front + 1) % maxSize;
- rear = (rear + 1) % maxSize;
链式队列 — 基于单链表
- 无惧溢出

队列应用：打印二项展开式 (a + b)^i 的系数 — 打印杨辉三角

杨辉三角的性状可知，除了第一行以外。打印接下来的任意i行数据，都依赖于i-1行的数据。

void solve()
{
    queue <int> q;
    int i = 1;
    int j;
    int s,k;
    int t,u;
    int n = 10;
    s=k=0;
    q.push(i);q.push(i);
    for(i = 1;i <= n; i++){
        cout << endl;
        q.push(k);
        for(j = 1;j <= i + 2;j++)
        {
            t = q.front();
            q.pop();
            u = s + t;q.push(u);
            s = t;
            if( j != i + 2) cout << s << ' ';
        }
    }
}
//keycode

队列应用： bfs

寻找矩阵地图中的最短路径

dfs相比之下就很慢咯

优先级队列

定义：每次从队列中取出的应是具有最高优先级的元素，这种队列就是优先级队列（Priority Queue）
- 每个元素都有一个优先权或值。
- 优先级队列主要操作：1.查找；2.插入；3.删除
- 优先权是一个可变的概念。优先级队列分为最小优先与最大优先
存储表示与实现
- 数组：实现效率差 — 调整队列中元素的次序。最坏：O(n)
- 堆（heap）：实现效率高。O(log_2n)

双端队列



Learning Key Word -2

数据结构

队列

队列应用： 打印二项展开式 (a + b)^i 的系数 — 打印杨辉三角

队列应用： bfs

优先级队列

双端队列

队列应用：打印二项展开式 (a + b)^i 的系数 — 打印杨辉三角