当前课程知识点：Data Structures and Algorithm Design Part I >  04.Stack+Queue >  D.Queue-ADT+implementation >  04D-3

返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表

04D-3在线视频

下一节:05A-1

返回《Data Structures and Algorithm Design Part I》慕课在线视频列表

04D-3课程教案、知识点、字幕

我们这里给出一种实现方法

好消息是 并不需要从轮子开始造起

与栈同理

既然队列也是属于序列

自然可以利用我们此前已经实现的

最基本的向量以及列表结构

直接派生而得

比如这里选用列表来实现队列

具体的代码如下

可以看到 所谓的Queue

也就是队列模板类

的确是以public的形式

继承自我们此前已经实现完善的list

所以因此同样地 一些标准接口

像size()或者是empty()等等

都可以直接沿用

我们不必再重写了

其实某种意义上而言

插入和删除等动态操作也是如此

只不过因为这里操作位置受限

而且名字也进行了更换

所以我们有必要重新定义一下

而且定义的方法非常的简明

我们可以看到 所谓的enqueue

其实就是将当前的元素

作为末元素插入

与其说是队列

不如说是列表当中

如果你有点淡忘了

建议你去温习一下insertAsLast这个接口

从功能上看

如果我们是通过一个列表来模拟队列的话

我们这里的习惯

将顶端认为是前端front

相应地 将底端取作尾端

那么insertAsLast就是将一个新的元素

作为最后那个元素插入其中

这种方式非常自然

我们再来看删除操作dequeue()

可以看到 这里无非是去找到

当前的首元素 first element

从位置来看 也就是这个元素

first接口将按照语义

返回这个节点的position

而当我们用这个position

交给remove接口的时候

它就会顺利地将这个节点删除掉

当然 这里我们保证了

这个队列当前是非空的

对这一点的核对

我们交给程序员来完成

既然我们的前端取作这个位置

所以首元素首当其冲的

也就是我们需要查询的那个front元素

因此我们将first node的data域

直接返回也是再自然不过了

由此可见

这种基于以前的工作

来进一步完成新的任务的思路

是非常高明的

不仅使得我们的工作可以快速推进

而且使得整个工作的系统性和安全性

都能得到保障

那么更好的消息是

我们如果稍做考察的话会发现

如此实现的

无论是enqueue dequeue还是front

这些接口都能够在常数的时间内完成

O(1)的时间

这也是不能再好的消息了

你应该还记得 我们在基于向量

以public的形式派生出来的stack模板类

对于vector的方向选择是非常敏感的

我们更倾向于使用vector的首端

作为栈结构的底端 或者说叫盲端

而所有的动态操作 包括push

以及pop 都在另一端

也就是vector的末端来进行

我们当时曾经做过分析

这样前后颠倒过来

虽然还勉强可行

但是在效率上

却会有天壤之别

那么当我们基于List

来实现Queue的时候

是否也需要注意这个禁忌呢？

如果将两个方向颠倒过来

又会如何呢？

我们将这个问题作为这一节的思考题

Data Structures and Algorithm Design Part I课程列表：

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--（a）计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-（xd）：LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

04D-3笔记与讨论

也许你还感兴趣的课程:


  1. Scientific Fitness Method--Chan Si Gong(Round 2)

  2. 护理伦理学(2021秋)

  3. 统计方法（SAS、SPSS和R统计软件应用）(2021秋)

  4. Traditional Customs and Chinese Arts(Round4)

  5. Landscape Architecture Design(Round 2)

  6. Matlab 基础及在地学中的应用(2021秋)

  7. Strategies of Becoming a Dessert Master(Round 2)

  8. 室内乐(2021秋)

  9. Medical Immunology(Round 2)

  10. 管理素质与能力的五项修炼——跟我学“管理学”(2021秋)

  11. Data Structures and Algorithm Design Part I(Self-Paced)

  12. 清华大学计算机科学与技术系六十周年系庆学术报告（四）大数据(自主模式)

  13. Mechanical Manufacturing Technology(Round 1)

  14. Surgery(Spring 2021)

  15. 临床研究方法学导论(2021春)

  16. 2019年研究生学术与职业素养讲座(自主模式)

  17. 工业互联网大讲堂(自主模式)

  18. Chinese History From Warring States to the Tang Dynasty(Self-Paced)

  19. History of Chinese Architecture Part I(Self-Paced)

  20. Database Technology and Programming(Round 1)
© 柠檬大学-慕课导航 课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。