江小南

V1

2023/02/14阅读:16主题:萌绿

【数据结构】双端队列

1. 回顾

栈:只允许从一端插入和删除的线性表(先进后出:FILO)。

队列:只允许从一端插入,另一端删除的线性表(先进先出:FIFO)。

2. 双端队列

1. 双端队列

双端队列:只允许从两端插入,两端删除的线性表。

若只使用其中一端插入、删除操作,则效果等同于栈。

2. 输入受限的双端队列

输入受限的双端队列:只允许从一端插入,两端删除的线性表。

3. 输出受限的双端队列

输出受限的双端队列:只允许从两端插入,一端删除的线性表。

3. 思考题

若数据元素输入序列为1,2,3,4,则哪些输出序列是合法的,哪些是非法的?

(A)3、2、4、1

(B)4、3、1、2

(C)1、4、2、3

(D)4、2、1、3

解析:题目中没有明确说是那种序列,就要从栈、队列、双端队列等多个角度思考。4个数字的所有排列组合顺序有 种情况。由卡特兰数: 得出对于栈的情况有14种合法出栈序列。

同时,在栈中合法的序列,在双端队列中也一定合法

A选项看成一个栈,首先入栈1、2、3,然后3、2依次出栈,4入栈,再4出栈,最后1出栈。合法。

B看成输入受限的双端队列。首先4个元素输入,4、3依次出列,1从另一端出列,最后2出列,合法。

C看成输入受限的双端队列。首先1输入,然后1出队列。再2、3、4依次输入,4出列,2从另一端出列,最后3出列,合法。

D无法实现,不合法。

4. 小结

回顾:共享栈。

【数据结构】栈的基本原理与实现

分类:

后端

标签:

数据结构与算法

作者介绍

江小南
V1