设有栈S和队列Q初始状态为空，数据元素序列abcdef依次通过栈S，且多个元素从S出栈后立..

2021年上半年上午试卷综合知识

第 34 题


知识点	队列栈
关键词	队列数据栈底
章/节	计算机软件知识

设有栈S和队列Q初始状态为空，数据元素序列a,b,c,d,e,f依次通过栈S，且多个元素从S出栈后立即进入队列Q，若出队的序列是b,d,f,e,c,a,则S中的元素最多时，栈底到栈顶的元素依次为( )。

A. a,b,c

B. a,c,d

C. a,c,e,f

D. a,d,f,e

相关试题计算机软件知识

第28题

2019年上半年

从减少成本和缩短研发周期考虑，要求嵌入式操作系统能运行在不同的微处理器平台上，能针对硬件变化进行结构与功能上的配置。该要求体现了嵌入式操作系统的（）。..

第62题

2014年上半年

某个算法的时间复杂度递归式T(n)=T(n-l)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（62），若问题的规模增加了16倍，则运行时间增加（63）倍。

第60题

2017年下半年

以下关于无向连通图G的叙述中，不正确的是（）。

知识点讲解

· 队列

· 栈

队列

1）队列的定义及基本运算

队列是一种先进先出（FIFO）的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾（Rear），允许删除元素的一端称为队头（Front）。

对队列进行的基本操作如下。

（1）置队空InitQueue(Q)：创建一个空的队列Q。

（2）判队空Empty(Q)：判断队列是否为空。

（3）入队EnQueue(Q,x)：将元素x加入到队列Q的队尾，并更新队尾指针。

（4）出队DeQueue(Q)：将队头元素从队列Q中删除，并更新队头指针。

（5）读队头元素Frontque(Q)：返回队头元素的值，但并不更新队头指针。

2）队列的存储结构

（1）顺序存储。队列的顺序存储结构是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在队列的两端进行，因此设置队头指针和队尾指针，分别指示当前的队首元素和队尾元素。

在顺序队列中，为了降低运算的复杂度，元素入队时只需修改队尾指针，元素出队时只需修改队头指针。由于顺序队列的存储空间是提前设定的，所以队尾指针会有一个上限值，当队尾指针达到其上限时，就不能只通过修改队尾指针来实现新元素的入队操作了。此时，可通过整除取余运算将顺序队列假想成一个环状结构，称之为循环队列。在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置是相同的。为了区别队空和队满的情况，可采用两种处理方式：其一是设置一个标志位，以区别头、尾指针的值相同时队列是空还是满；其二是牺牲一个元素空间，约定以"队列的尾指针所指位置的下一个位置是头指针时"表示队列满，头、尾指针的值相同时表示队列空。

（2）链式存储。用链表表示的队列简称为链队列。为了便于操作，给链队列添加一个头节点，并令头指针指向头节点。队列为空的判定条件是：头指针和尾指针的值相同，且均指向头节点。

3）队列的应用

队列结构常用于处理需要排队的场合，如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。

栈

1）栈的定义及基本运算

栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。栈的修改是按先进后出的原则进行的。因此，栈又称为先进后出（FILO，或后进先出）的线性表。栈进行插入和删除操作的一端称为栈顶，另一端称为栈底。不含数据元素的栈称为空栈。

对栈进行的基本操作有以下几种。

.置空栈InitStack(S)：创建一个空栈S。

.判栈空Empty(S)：当栈S为空栈时返回真值；否则返回假值。

.入栈Push(S,x)：将元素x加入栈顶，并更新栈顶指针。

.出栈Pop(S)：将栈顶元素从栈中删除，并更新栈顶指针。若需要得到栈顶元素的值，可将Pop(S)定义为一个函数，它返回栈顶元素的值。

.读栈顶元素Top(S)：返回栈顶元素的值，但不修改栈顶指针。

2）栈的存储结构

（1）顺序存储。栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针top指示栈顶元素的位置。在顺序存储方式下，需要预先定义或申请栈的存储空间，也就是说，栈空间的容量是有限的。因此在顺序栈中，当一个元素入栈时，需要判断是否栈满，若栈满，则元素入栈会发生上溢现象。

利用栈底位置不变的特性，可以让两个顺序栈共享一个一维数据空间，以互补余缺，实现方法是：将两个栈的栈底位置分别设在存储空间的两端，让它们的栈顶各自向中间延伸。这样，两个栈的空间就可以相互调节，只有在整个存储空间被占满时才发生上溢，这样一来产生上溢的概率要小得多。

（2）链式存储。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必设置头节点，链表的头指针就是栈顶指针。

3）栈的应用

栈的典型应用包括表达式求值、括号匹配等，在计算机语言的实现中以及将递归过程转变为非递归过程的处理中，栈有重要的作用。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5