《3、2、4_双端队列.pdf》由会员分享，可在线阅读，更多相关《3、2、4_双端队列.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2020/1/21王道考研/1本节内容双端队列王道考研/CSKAOYAN.COM1王道考研/CSKAOYAN.COM双端队列双端队列1234删除插入1234删除插入双端队列双端队列：只允许从两端插入、两端删除的线性表栈栈：只允许从一端插入和删除的线性表1234删除插入队列队列：只允许从一端插入、另一端删除的线性表删除插入555若只使用其中一端的插入、删除操作，则效果等同于栈22020/1/21王道考研/2王道考研/CSKAOYAN.COM双端队列双端队列1234删除插入双端队列双端队列：只允许从两端插入、两端删除的线性表删除插入51234删除插入输入受限输入受限的双端队列的双端队列：只允许从一
2、端插入、两端删除的线性表删除51234插入删除插入5输出受限输出受限的双端队列的双端队列：只允许从两端插入、一端删除的线性表3王道考研/CSKAOYAN.COM考点：判断输出序列合法性考点：判断输出序列合法性若数据元素输入序列为 1,2,3,4，则哪些输出序列是合法的，哪些是非法的？1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,
3、1,24,3,2,1= 4! = 241234删除插入栈栈42020/1/21王道考研/3王道考研/CSKAOYAN.COM考点：判断输出序列合法性考点：判断输出序列合法性若数据元素输入序列为 1,2,3,4，则哪些输出序列是合法的，哪些是非法的？1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,1= 4! = 2
4、41234删除插入栈栈5王道考研/CSKAOYAN.COM考点：判断输出序列合法性考点：判断输出序列合法性若数据元素输入序列为 1,2,3,4，则哪些输出序列是合法的，哪些是非法的？1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,1= 4! = 241234删除插入栈栈62020/1/21王道考研/4王道考研/C
5、SKAOYAN.COM考点：判断输出序列合法性考点：判断输出序列合法性若数据元素输入序列为 1,2,3,4，则哪些输出序列是合法的，哪些是非法的？1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,1= 4! = 241234删除插入栈栈7王道考研/CSKAOYAN.COM考点：判断输出序列合法性考点：判断输出序列合
6、法性若数据元素输入序列为 1,2,3,4，则哪些输出序列是合法的，哪些是非法的？1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,1= 4! = 24删除插入栈栈卡特兰数：14 + 1= 141n + 1)*=14种合法出栈序列82020/1/21王道考研/5王道考研/CSKAOYAN.COM考点：判断输出序列合法
7、性考点：判断输出序列合法性若数据元素输入序列为 1,2,3,4，则哪些输出序列是合法的，哪些是非法的？= 4! = 24删除插入输入受限输入受限的双端队列的双端队列删除1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,11234栈中合法的序列，双端队列中一定也合法9王道考研/CSKAOYAN.COM考点：判断输出序
8、列合法性考点：判断输出序列合法性若数据元素输入序列为 1,2,3,4，则哪些输出序列是合法的，哪些是非法的？= 4! = 24删除插入输入受限输入受限的双端队列的双端队列删除1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,11234102020/1/21王道考研/6王道考研/CSKAOYAN.COM考点：判断输出
9、序列合法性考点：判断输出序列合法性若数据元素输入序列为 1,2,3,4，则哪些输出序列是合法的，哪些是非法的？= 4! = 24删除插入输入受限输入受限的双端队列的双端队列删除1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,1123411王道考研/CSKAOYAN.COM考点：判断输出序列合法性考点：判断输出序列
10、合法性若数据元素输入序列为 1,2,3,4，则哪些输出序列是合法的，哪些是非法的？= 4! = 24删除插入输入受限输入受限的双端队列的双端队列删除1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,1122020/1/21王道考研/7王道考研/CSKAOYAN.COM考点：判断输出序列合法性考点：判断输出序列合法性
11、若数据元素输入序列为 1,2,3,4，则哪些输出序列是合法的，哪些是非法的？= 4! = 24删除插入输出受限输出受限的双端队列的双端队列1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,11234栈中合法的序列，双端队列中一定也合法插入13王道考研/CSKAOYAN.COM考点：判断输出序列合法性考点：判断输出序
12、列合法性若数据元素输入序列为 1,2,3,4，则哪些输出序列是合法的，哪些是非法的？= 4! = 24删除插入输出受限输出受限的双端队列的双端队列1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,11234插入142020/1/21王道考研/8王道考研/CSKAOYAN.COM考点：判断输出序列合法性考点：判断输出
13、序列合法性若数据元素输入序列为 1,2,3,4，则哪些输出序列是合法的，哪些是非法的？= 4! = 24删除插入输出受限输出受限的双端队列的双端队列1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,11插入15王道考研/CSKAOYAN.COM考点：判断输出序列合法性考点：判断输出序列合法性若数据元素输入序列为 1
14、,2,3,4，则哪些输出序列是合法的，哪些是非法的？= 4! = 24删除插入输出受限输出受限的双端队列的双端队列1,2,3,41,2,4,31,3,2,41,3,4,21,4,2,31,4,3,22,1,3,42,1,4,32,3,1,42,3,4,12,4,1,32,4,3,13,1,2,43,1,4,23,2,1,43,2,4,13,4,1,23,4,2,14,1,2,34,1,3,24,2,1,34,2,3,14,3,1,24,3,2,1插入162020/1/21王道考研/9王道考研/CSKAOYAN.COM知识回顾与重要考点知识回顾与重要考点在栈中合法的输出序列，在双端队列中必定合法回忆：栈的变种共享栈17