当前位置：文档之家 › 栈和队列

栈和队列

  • 格式：doc
  • 大小：35.50 KB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

栈、队列

栈、队列

2、二叉树的两个特殊形态
⑴满二叉树： 如果一棵深度为K的二叉树，共有2K-1个结点， 即第I层有2I-1的结点，称为满二叉树。(a)
⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数 可以小于2，并且最下面一层的结点都集中在该层最左边的若 干位置上，则称此二叉树为完全二叉树（例如下图(b)）
？
二叉树是不是树？二叉树∈树？
由上述定义可以看出，二叉树和树是两个不同的概念 ⑴树的每一个结点可以有任意多个后件，而二叉树中每个结点 的后继不能超过2； ⑵树的子树可以不分次序（除有序树外）；而二叉树的子树有 左右之分。我们称二叉树中结点的左后件为左儿子，右后件为 右儿子。 前面引入的有关树的一些基本术语对二叉树仍然适用。下图列 出二叉树的五种基本形态：
一、栈
1、栈的定义 栈是一种线性表，对它的插入和删除都限制地表的同一 端进行。这一端叫做栈的“顶”，另一端则叫做栈的“底”。
特点:后进先出(LIFO)、或者先进后出（FILO） 通常栈可以用顺序的方式存储(数组)，分配一块连续的存储区域存放 栈中的表目，并用一个变量t指向当前栈顶（如下图）。
假设栈中表目数的上限为m，所有表目都具有同一类型 stype，则可以用下列方式定义栈： Const m=栈表目数的上限； Var
4、设有一个顺序栈S，元素S1, S2, S3, S4, S5, S6依次 进栈，如果6个元素的出栈顺序为S2, S3, S4, S6, S5, S1，则顺序栈的容量至少应为多少？ A) 3 B) 4 C) 5 D) 6 5、向顺序栈中压入新元素时，应当（ ）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行
s： array[1‥m] of stype ；{栈}

数据结构(C语言)第3章 栈和队列

数据结构(C语言)第3章 栈和队列

Data Structure
2013-8-6
Page 13
栈的顺序存储（顺序栈）
利用一组地址连续的存储单元依次存放自栈底到栈顶的数 据元素。 结构定义： #define STACK_INIT_SIZE 100; // 存储空间初始分配量 #define STACKINCREMENT 10; // 存储空间分配增量 typedef struct { SElemType *base; // 存储空间基址 SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素位单位 } SqStack;
解决方案2：
顺序栈单向延伸——使用一个数组来存储两个栈
Data Structure 2013-8-6 Page 21
两栈共享空间 两栈共享空间：使用一个数组来存储两个栈，让一个 栈的栈底为该数组的始端，另一个栈的栈底为该数组 的末端，两个栈从各自的端点向中间延伸。
Data Structure
2013-8-6
链栈需要加头结点吗？ 链栈不需要附设头结点。
Data Structure
2013-8-6
Page 27
栈的链接存储结构及实现
Data Structure
2013-8-6
Page 11
GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回S的栈顶元素。 Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。
Data Structure

数据结构--栈和队列基础知识

数据结构--栈和队列基础知识

数据结构--栈和队列基础知识⼀概述栈和队列，严格意义上来说，也属于线性表，因为它们也都⽤于存储逻辑关系为 "⼀对⼀" 的数据，但由于它们⽐较特殊，因此将其单独作为⼀篇⽂章，做重点讲解。

既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列，这些内容都会在本章做详细讲解。

使⽤栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；使⽤队列存储数据，讲究 "先进先出"，即最先进队列的数据，也最先出队列。

⼆栈2.1 栈的基本概念同顺序表和链表⼀样，栈也是⽤来存储逻辑关系为 "⼀对⼀" 数据的线性存储结构，如下图所⽰。

从上图我们看到，栈存储结构与之前所了解的线性存储结构有所差异，这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求：1. 栈只能从表的⼀端存取数据，另⼀端是封闭的；2. 在栈中，⽆论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。

拿图 1 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。

因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。

因此，我们可以给栈下⼀个定义，即栈是⼀种只能从表的⼀端存取数据且遵循 "先进后出" 原则的线性存储结构。

通常，栈的开⼝端被称为栈顶；相应地，封⼝端被称为栈底。

因此，栈顶元素指的就是距离栈顶最近的元素，拿下图中的栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元素，下中的栈底元素为元素 1。

2.2 进栈和出栈基于栈结构的特点，在实际应⽤中，通常只会对栈执⾏以下两种操作：向栈中添加元素，此过程被称为"进栈"（⼊栈或压栈）；从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；2.3 栈的具体实现栈是⼀种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种⽅式：1. 顺序栈：采⽤顺序存储结构可以模拟栈存储数据的特点，从⽽实现栈存储结构。

栈和队列-题库

栈和队列-题库

位置
(A)链头 (B)链尾 (C)链中
27．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机
将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印.该缓冲区应该是
一个
结构.
(A)堆栈 (B)队列 (C)数组 (D)线性表
28．设栈的输入序列为 1,2,3,…,n,输出序列为 a1,a2,a3,…,an,若存在 1<=k<=n 使得 ak=n,则当 k<=i<=n 时,ai 为 (A)n-i+1 (B)n-(i-k) (C)不确定 29、若已知一个栈的入栈序列是 1,2,3,4….,n，其输出序列为 p1,p2,p3,p4,….,pn，若 p1=n，
是；类似地，考虑对这四个数据元
素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的
元素是
，第二次出队得到的元素是
。经操作后，最后在栈中或队中的元素还
有
个。
供选择的答案：
A～D：①a1 ②a2 ③ a3 ④a4
E： ①1 ②2 ③ 3 ④ 0
24．从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在
答卷的对应栏内。
在做进栈运算时，应先判别栈是否 ；在做退栈运算时，应先判别栈是否 。当栈
中元素为 n 个，做进栈运算时发生上溢，则说明该栈的最大容量为 。
为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应
将两栈的 分别设在这片内存空间的两端，这样，只有当 时，才产生上溢。
B. rear- front-1==m0
C. front== rear
D. front== rear+1

第3章 栈和队列

第3章 栈和队列

第三章栈和队列基本概念1、栈的定义、特点2、顺序栈和链栈的进栈和退栈操作；栈空和栈满的判定条件3、队列的定义和特点4、循环队列、链队列的出队和入队操作、判定队列为空、队列为满的条件一、选择题1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（）。

A. a,b,c,d,eB. d,e,c,b,aC. d,c,e,a,bD. e,d,c,b,a2、判断一个循环队列Q（最多n个元素）为满的条件是（）。

A. Q->rear==Q->frontB. Q->rear==Q->front+1C. Q->front==(Q->rear+1)%nD. Q->front==(Q->rear-1)%n3、设计一个判别表达式中括号是否配对的算法，采用（）数据结构最佳。

A. 顺序表B. 链表C. 队列D. 栈4、带头结点的单链表head为空的判定条件是（）。

A. head==NULLB. head->next==NULLC. head->next!=NULLD. head!=NULL5、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（）。

A. 1243B. 2134C. 1432D. 4312E. 32146、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。

当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。

A. 1和5B. 2和4C. 4和2D. 5和1 大小为6的数组：下标从0-5;从前面出队，从后面入队front(前面)=3rear(后面)=0当出队列中删除一个元素，也就是出队，即front+1:=4再插入两个元素，即rear+2= 27、队列的插入操作是在（）。

A. 队尾B. 队头C. 队列任意位置D. 队头元素后8、循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（）。

《数据结构(C语言)》第3章 栈和队列

《数据结构(C语言)》第3章 栈和队列
Data structures
栈
❖ 栈的顺序存储与操作 ❖ 1.顺序栈的定义
(1) 栈的静态分配顺序存储结构描述 ② top为整数且指向栈顶元素 当top为整数且指向栈顶元素时，栈空、入栈、栈满 及出栈的情况如图3.2所示。初始化条件为 S.top=-1。
(a) 栈空S.top==-1 (b) 元素入栈S.stack[++S.top]=e (c) 栈满S.top>=StackSize-1 (d) 元素出栈e=S.stack[S.top--]
/*栈顶指针，可以指向栈顶
元素的下一个位置或者指向栈顶元素*/
int StackSize; /*当前分配的栈可使用的以 元素为单位的最大存储容量*/
}SqStack;
/*顺序栈*/
Data structures
栈
❖ 栈的顺序存储与操作 ❖ 1.顺序栈的定义
(2) 栈的动态分配顺序存储结构描述 ① top为指针且指向栈顶元素的下一个位置 当top为指针且指向栈顶元素的下一个位置时，栈空 、入栈、栈满及出栈的情况如图3.3所示。初始化条 件为S.top=S.base。
…，n-1，n≥0} 数据关系：R={< ai-1，ai>| ai-1，ai∈D，i=1，2
，…，n-1 } 约定an-1端为栈顶，a0端为栈底 基本操作：
(1) 初始化操作：InitStack(&S) 需要条件：栈S没有被创建过 操作结果：构建一个空的栈S (2) 销毁栈：DestroyStack(&S) 需要条件：栈S已经被创建 操作结果：清空栈S的所有值，释放栈S占用的内存空间
return 1;
}
Data structures
栈

数据结构基础栈和队列

数据结构基础栈和队列
②X=S[TOP]，（退栈后的元素赋给X）； ③TOP--，结束（栈指针减１，指向栈顶）。
栈的应用 十进制数N和其它d进制数的转换是实现计算的基本问题，
解决方法很多，下面给出一种算法原理： N=(N / d)×d＋N % d （其中 / 为整除运算，%为求余运算）。
例如：(1348)10＝(2504)8运算过程如下：
default:x=0; while (s[i]!=' ') x=x*10+s[i++]-'0'; stack[++top]=x;
break;
}
i++;
}
//while
return stack[top];
}
main() {
printf("input a string(@_over):"); gets(s); printf("result=%d",comp(s)); return 0; }
cout<<"Please enter a number(N) base 10:"; cin>>n; cout<<"please enter a number(d):"; cin>>d; do{
a[++i]=n%d; n=n/d; }while(n!=0); for (j=i;j>=1;j--)cout<<a[j]; return 0; }
集合
• 数据元素的物理结构有两种：顺序存储结构和链 式存储结构
• 顺序存储结构:用数据元素在存储器中的相对位 置来表示数据元素之间的逻辑关系。

第三章栈和队列

第三章栈和队列
西南交通大学信息科学与技术学院软件工程系‐赵宏宇
续8
//循环队列实现方案二 在SqQueue结构体中增设计数变量c，记录队列中当前 元素个数 void clearQueue(SqQueue &q) { q.r=q.f=-1; q.c=0; //r=f=-1~n-1区间任意整数均可 } int empty(SqQueue &q) { return q.c==0; } int full(SqQueue &q) { return q.c==q.n; } //队空、队满时q.f==q.r均为真 //优点：队满时没有空闲元素位置(充分利用了空间)
西南交通大学信息科学与技术学院软件工程系‐赵宏宇 数据结构A 第3章‐19
西南交通大学信息科学与技术学院软件工程系‐赵宏宇
数据结构A 第3章‐20
3.3 栈的应用
续1
3.3 栈的应用
续2
2. 栈与递归 (1) 递归程序的存储空间消耗 由于函数调用的指令返回地址、形式参数以及断 点状态均用系统堆栈实现存储，因此递归调用的层次 数(深度)决定了系统堆栈必须保留的存储空间容量大小。 例1 以下函数用递归法实现n元一维数组元素逆序存储， 试分析所需栈的深度。 void reverse(ElemTp a[], int i, int j) //数组a下标范围i..j实现元素逆序存储 { if(i<j) { a[i]a[j]; reverse(a, i+1, j-1); } }
西南交通大学信息科学与技术学院软件工程系‐赵宏宇 数据结构A 第3章‐7
3. 堆栈习题举例 例1 若元素入栈次序为ABC，写出所有可能的元素出栈 次序。 答: 所有可能的元素出栈次序共5种，即 ABC 操作PXPXPX (P表示入栈，X表示退栈) ACB PXPPXX BAC PPXXPX BCA PPXPXX CBA PPPXXX

ds-栈和队列

ds-栈和队列

//插入元素x为栈顶元素
if ( StackFull (S) ){
S->base =( StackData *)realloc(S->base ,
(S->stacksize+ STACKINCREMENT) *sizeof(StackData));
if(! S->base)exit(overflow);
2020/7/8
YuJin CS STU
9/77
顺序栈的基本运算:
▪ 判栈空
int StackEmpty (SeqStack *S) { //判栈空
if (S->top ==S->base ) return 1
else return 0
}
▪ 判栈满
int StackFull (SeqStack *S) {
S->top= S->base + S->stacksize; S->stacksize+= STACKINCREMENT;
//追加存储空间
}
*(S->top++)=x;
Return ok
}
*realloc(void *p, size) realloc函数将p指向的对象的长度修改为 size个字节；
//判栈满
if( S->top - S->base == S-> StackSize) return 1
//满则返回1
else return 0;
//否则返回0
}
2020/7/8
YuJin CS STU
10/77
▪初始化
void InitStack ( SeqStack *S) { //置空栈

数据结构的4种存储结构

数据结构的4种存储结构

数据结构的4种存储结构数据结构指的是在计算机中组织和存储数据的方式。

在计算机科学中，有四种主要的数据结构存储方式，分别是数组、链表、栈和队列。

本文将详细介绍这四种存储结构的特点、应用场景和优缺点。

一、数组数组是一种线性数据结构，它由一系列相同类型的元素组成，这些元素在内存中是连续存储的。

数组能够快速访问任意位置的元素，但插入和删除元素则需要移动其他元素。

数组的应用场景非常广泛。

例如，在图像处理中，可以使用二维数组来表示和操作图像的像素信息。

数组还可以用于实现高效的查找算法，如二分查找。

然而，数组的大小在声明时就需要确定，无法动态扩展，这限制了其灵活性。

而且，插入和删除操作的时间复杂度为O(n)，效率比链表要低。

二、链表链表是一种非连续、非顺序的数据结构，由一系列节点组成。

每个节点包含了一个数据元素和指向下一个节点的引用。

链表的元素在内存中可以是连续或分散的。

链表适用于频繁插入和删除节点的场景，因为它不需要移动其他节点。

另外，链表的大小可以动态地增长或缩小，灵活性更好。

链表还可以用于构建其他数据结构，如队列和栈。

然而，链表的随机访问效率低，需要遍历整个链表才能找到目标元素。

而且，链表需要额外的空间来存储节点的引用，增加了存储开销。

三、栈栈是一种先进后出（LIFO）的数据结构。

它可以看作是一种特殊的线性表，只能在栈的一端操作，称为栈顶。

栈的插入和删除操作都在栈顶进行。

栈具有很多实际应用。

例如，在函数调用过程中，可以使用栈来保存局部变量和返回地址。

栈还可以用于实现递归算法、括号匹配等。

栈的大小由系统自动管理，使用起来非常方便。

然而，栈的存储空间有限，一旦超出容量会发生栈溢出。

同时，栈不支持随机访问元素。

四、队列队列是一种先进先出（FIFO）的数据结构。

它可以看作是一种特殊的线性表，只能在双端操作，称为队头和队尾。

队列的插入操作在队尾进行，删除操作在队头进行。

队列广泛应用于各种场景。

例如，在操作系统中，可以使用队列来调度进程；在网络通信中，可以使用队列来管理数据包的传输顺序。

数据结构：栈和队列期末单元测试与答案

数据结构：栈和队列期末单元测试与答案

一、单选题1、经过以下栈运算后，x的值是（）。

InitStack(s); Push(s,a); Push(s,b); Pop(s,x); GetTop(s,x);A.bB.0C.1D.a正确答案：D2、若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A.2，3，5，4，1B.5，4，3，2，1C.2，1，5，4，3D.4，3，1，2，5正确答案：D3、若链栈采用无头结点的单链表存储，top指向栈顶。

若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A.x=top->data;top=top->next；B.top=top->link;x=top-> next；C.x=top-> next；D.x=top;top=top-> next；正确答案：A4、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A.n+r-fB.n+r-f)%nC.r-fD.(n+f-r)%n正确答案：B5、设有一个递归算法如下int fact(int n) { //n大于等于0if(n<=0)return 1;elsereturn n*fact(n-1);}则计算fact(n)需要调用该函数的次数为（）。

A.n+2B.nC.n-1D.n+1正确答案：D6、栈在（）中有所应用。

A.表达式求值B.递归调用C.其他三个选项D.函数调用正确答案：C7、为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。

主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是（）。

A.线性表B.有序表C.栈D.队列正确答案：D8、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。

数据结构与算法：Python语言描述 栈和队列 ppt课件

数据结构与算法：Python语言描述 栈和队列 ppt课件

裘宗燕，2019/12/22-/10/
栈的应用
栈是算法和程序里最常用的辅助结构，基本用途基于两方面： 用栈可以很方便地保存和取用信息，因此常作为算法或程序里的辅 助存储结构，临时保存信息，供后面的操作使用 利用栈后进先出的特点，可以得到特定的存储和取用顺序 许多实际运用结合了这两方面的特性
配对的原则
遇到的闭括号应该匹配此前遇到的最近的尚未匹配的对应开括号
由于多种/多次/可能嵌套，为检查配对，遇到的开括号必须保存
由于括号可能嵌套，需要逐对匹配，闭括号应与前面最近的尚未有 匹配的开括号匹配，后面括号应与更前面次近的括号匹配
可以删除匹配的括号，为后面的匹配做好准备
后遇到并保存的开括号应该先删除，这就是后进先出，而且要按照出现 顺序，显然应该/可以用一个栈保存开括号
概述
栈和队列保证元素存取之间的时间关系，特点是：
栈是保证缓存元素后进先出（Last In First Out，LIFO）的结构
队列是保证缓存元素的先进先出（先存者先用，First In First Out， FIFO）关系的结构
对于栈和队列，任何时候，下次访问或删除的元素都默认地唯一确定。 只有新的存入或删除（弹出）操作可能改变下次的默认元素
self._elems = [] # 所有栈操作都映射到list操作
def is_empty(self):
return self._elems == []
def top(self):
if self._elems == []:
raise StackUnderflow("in SStack.top()")
return self._elems[-1]

栈与队列的基本操作

栈与队列的基本操作

a0
a1
a2
…
…
an-1
front
元素移动方向
rear
图7.15队列
图中队列的队尾(rear) 随着元素的不断加入，而不断向后移； 而队头(front)随元素的出队，也不断后移，即位置在变。
7.3.2 队列
顺序队列的缺点：
由图可见：空队 时指针（下标） front和rear在 一起都指向队前 方，当有元素进 队，则rear后 移；有元素出队， 则front后移， 最后分配给队的 前端不再被利用。
加标志，能否实现？
Question：循环队列的队满/队空如何区分？ （1）浪费一个空位置，空队时rear=front；满队时 必须空一个位置； （2）加标志来表示队空/队满，进队出队都要判 断，使用上更不方便。
顺序表循环队列类的设计
class CycleQueue {
不用空位置，用标志需要有
int rear,front;
//进队，rear++
DataType DeQue();
//出队，front++
DataType GetFront();
//取队头数据，front不变
void MakeEmpty不(){用fro空nt=位rea置r=，0;e不lem用e标nts志[fr。on当t]=NULL; }//队置空
（初始态） };
istack.PrintStack();
for(i=0;i<10;i++) b[i]=istack.Pop();
if(istack.IsEmpty()) cout<<"栈空"<<endl;
for(i=0;i<10;i++) cout<<b[i]<<'\t'; //注意先进后出

大学《数据结构》第三章：栈和队列-第一节-栈

大学《数据结构》第三章：栈和队列-第一节-栈

第一节栈
一、栈的定义及其运算
1、栈的定义
栈(Stack)：是限定在表的一端进行插入和删除运算的线性表，通常将插入、删除的一端称为栈项(top)，另一端称为栈底(bottom)。

不含元素的空表称为空栈。

栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出(Last In First Out)的线性表，简称为LIFO表。

真题选解
（例题·填空题）1、如图所示，设输入元素的顺序是（A，B，C，D），通过栈的变换，在输出端可得到各种排列。

若输出序列的第一个元素为D，则输出序列为。

隐藏答案
【答案】DCBA
【解析】根据堆栈"先进后出"的原则，若输出序列的第一个元素为D，则ABCD入栈，输出序列为DCBA
2、栈的基本运算
(1)置空栈InitStack(&S)：构造一个空栈S。

Java中栈和队列的使用及区别

Java中栈和队列的使用及区别

poll() ：检索并删除此队列的头部，如果此队列为空，则返回null。
E
remove() ：检索并删除此队列的头。
3、 Deque（双端队列 /栈）
Deque是双端队列的接口，也是我们使用最多的队列，既可以当作栈也可以当作队列使用。
Deque是支持在两端插入和删除元素的线性集合，双端队列是“双端队列”（double ended queue）的缩写。大多数Deque对它们可能包含 的元素数量没有固定的限制，但是此接口支持容量受限的双端队列以及没有固定大小限制的双端队列。此接口定义访问双端队列两端的元素 的方，提供了用于插入，删除和检查元素的方法。这些方法中的每一种都以两种形式存在：一种在操作失败时引发异常，另一种返回一个特 殊值（根据操作为null或false）。插入操作的后一种形式是专为容量受限的Deque实现而设计的。在大多数实现中，插入操作不会失败。
简单来说，PriorityQueue就是一个优先级队列，在我们需要堆的时候可以使用PriorityQueue当作堆进行使用，因为PriorityQueue继承
自AbstractQueue，而AbstractQueue实现Queue，所以PriorityQueue的方法和Queue差不多，使用起来也比较方便。
5.3 适 用 场 景 不 同
栈：具有记忆能力，使用于括号求解、表达式转换、函数递归和调用的实现、深度优先搜索遍历、浏览器后退功能等，需要记忆原来数 据内容的场景。 队列：可以进行有顺序的处理，如计算机系统中各种资源的管理、消息缓冲器的管理、广度优先搜索等场景。
6、 总 结
在不考虑多线程的情况下 使用栈就是使用Deque的实现类 使用队列就使用Deque的实现类 使用堆就使用PriorityQueue。

数据结构实用教程(C语言版) 第3章 栈和队列

数据结构实用教程(C语言版) 第3章 栈和队列
返回到本节目录
3.1.1 栈的概念
假设有一个栈S=（a1，a2，…，an），栈 中元素按a1，a2，…，an的次序进栈后， 进栈的第一个元素a1为栈底元素，出栈的第 一个元素an为栈顶元素，也就是出栈的操作 是按后进先出的原则进行的，其结构如图31所示。
图3-1栈结构示意图
返回到本节目录
3.1.2栈的基本操作
3.1.3顺序栈
由于栈是操作受限制的线性表，因此与线性表类似，栈也 有两种存储结构，即顺序存储结构和链式存储结构。 1. 顺序栈的定义 栈的顺序存储结构称为顺序栈。类似于顺序表的类型定义，顺 序栈是用一个预设的足够长度的一维数组和一个记录栈顶元素 位置的变量来实现。顺序栈中栈顶指针与栈中数据元素的关1.3顺序栈
3. 顺序栈的基本操作实现
（3）进栈操作 进栈操作的过程如图3-3所示。先判断栈S如图3-3（a） 是否为满，若不满再将记录栈顶的下标变量top加1如 图3-3（b），最后将进栈元素放进栈顶位置上如图33（c）所示，算法描述见算法3.3。
图3-3 进栈操作过程图
返回到本节目录
栈除了在栈顶进行进栈与出栈外，还有初始化、判空 等操作，常用的基本操作有： （1）初始化栈InitStack(S)。其作用是构造一个空 栈 S。 （2）判断栈空EmptyStack(S)。其作用是判断是 否是空栈，若栈S为空，则返回1；否则返回0。 （3）进栈Push(S,x)。其作用是当栈不为满时，将 数据元素x插入栈S中，使其为栈S的栈顶元素。 （4）出栈Pop(S,x)。其作用是当栈S不为空时，将 栈顶元素赋给x，并从栈S中删除当前栈顶元素。 （5）取栈顶元素GetTop(S,x)。其作用是当栈S不 为空时，将栈顶元素赋给x并返回，操作结果只是 读取栈顶元素，栈S不发生变化。 返回到本节目录

简要说明线性表、栈和队列的异同点

简要说明线性表、栈和队列的异同点

简要说明线性表、栈和队列的异
同点
Stack和queue都是线性表，它们是特殊的线性表：特别的是插入点和删除点是有限的。

堆栈在线性表的固定端插入和删除，因此其特征是后进先出。

队列在线性表的一端插入，在另一端删除，所以特征是FIFO
堆栈和队列是操作位置有限的线性表，即插入和删除的位置是有限的。

Stack是一个线性表，只允许在表的一端插入和删除，所以它是一个后进先出表。

队列是一个线性表，只能在表的一端插入，在表的另一端删除，所以它是一个后进先出的表
共同点：两者都有顺序结构和链式结构，只能在线性表的一端插入和删除。

区别：不同的操作。

堆栈和队列是程序设计中广泛使用的两种线性数据结构。

其特点在于基本操作的特殊性。

堆栈必须按照“后进先出”的规则操作，队列必须按照“先进先出”的规则操作。

与线性表的关系：堆栈和队列是线性表，它们限制插入和删除点（或控制访问点）。

队列是一种特殊的线性表，它只允许在表的前面删除，在表的后面插入。

队列和堆栈一样，是一种操作受限的线性表。

插入的结束称为团队的尾部，删除的结束称为团队的头部。

当队列中没有元素时，称为空队列。

栈队列和线性表的异同栈和队列是线性结构吗栈和队列逻辑上都是线性表吗。

第三章 栈和队列

第三章 栈和队列

第三章栈和队列一．选择题1.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当做退栈处理时，top变化为。

A．top不变 B．top＝top-n C．top＝top-1 D．top=top+1 2.在一个顺序存储的循环队列中，队首指针指向队首元素的。

A．前一个位置 B．后一个位置 C．队首元素位置 D．队尾元素位置3.若进栈序列为1,2,3,4,栈过程中可以出栈，则不可能是一个出栈序列。

A．3,4,2,1 B．2,4,3,1 C．1,4,2,3 D．3,2,1,44.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是。

A．front= =rear+1 B．front+1= =rear C．front= =rear D．front= =0 5.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行。

A．hs->next=s; B．s->next=hs->next;hs->next=s;C．s->next=hs;hs=s; D．s->next=hs;hs=hs->next;6.下列说法哪个正确：_______A．堆栈是在两端操作、先进后出的线性表B．堆栈是在一端操作、先进先出的线性表C．队列是在一端操作、先进先出的线性表D．队列是在两端操作、先进先出的线性表7.栈和队列的共同点_______A．都是先进后出 B．都是先进先出C．只允许在端点处插入和删除元素 D．没有共同点8.以下数据结构中哪一个是非线性结构？_______A．队列 B．栈 C．线性表 D．二叉树9.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3 ，…，pn，若p1=n，则 pi 为_______A．i B．n=i C．n-i+1 D．不确定10.当利用大小为 N 的一维数组顺序存储一个栈时，假定用top==N 表示栈空，则向这个栈插入一个元素时，首先应执行_______语句修改top指针。

栈和队列的存储方式,既可以是顺序方式,又可以是链式方式.

栈和队列的存储方式,既可以是顺序方式,又可以是链式方式.

栈和队列的存储方式,既可以是顺序方
式,又可以是链式方式.

【原题】
判断题：栈和队列的存储方式,既可以是顺序方式,又可
以是链式方式。（ ）(2分)
A. 正确
B. 错误
【答案】
A. 正确
【解析】
因为栈和队列是一种数据结构，只要满足了栈和队列的
属性，顺序存储或者链式存储都可以达到目的。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第3章 栈和队列 一 选择题 1. 对于栈操作数据的原则是（ ）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( )。 A. i B. n-i C. n-i+1 D. 不确定 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ ）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 11. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ ）。 A．fedcba B. bcafed C. dcefba D. cabdef 12. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。 A．XYZ B. YZX C. ZXY D. ZYX 13. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ） A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 16. 栈在（ ）中应用。 A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 17. 一个递归算法必须包括（ ）。 A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 19. 表达式a*(b+c)-d的后缀表达式是( )。 A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 21. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 22. 用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 23. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。 A．仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改 24. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 26. 循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。 A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 28. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 29. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不对 30. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。 A. 1234 B. 4132 C. 4231 D. 4213 31. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 A. (rear+1) MOD n=front B. rear=front C．rear+1=front D. (rear-l) MOD n=front 32. 栈和队列的共同点是（ ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 33. 栈的特点是（ ① ）,队列的特点是（ ② ）,栈和队列都是（ ③ ）。若进栈序列为1,2,3,4 则（ ④ ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（ ⑤ ）是一个出队列序列。 ①, ②: A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进 ③: A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构 ④, ⑤: A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,4 34. 栈和队都是（ ） A．顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构 35. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。 A． 6 B. 4 C. 3 D. 2 36. 用单链表表示的链式队列的队头在链表的（ ）位置。 A．链头 B．链尾 C．链中 37. 依次读入数据元素序列{a，b，c，d，e，f，g}进栈,每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列？ A．{d ，e，c，f，b，g，a} B. {f，e，g，d，a，c，b} C. {e，f，d，g，b，c，a} D. {c，d，b，e，f，a，g}

二 判断题 2. 栈是实现过程和函数等子程序所必需的结构。（ ） 5. 即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ） 9. 栈和队列都是限制存取点的线性结构。（ ） 10．若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。（ ） 14. 通常使用队列来处理函数或过程的调用。（ ） 15. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ） 16. 循环队列通常用指针来实现队列的头尾相接。（ ） 18. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ） 19. 栈和队列都是线性表，只是在插入和删除时受到了一些限制。（ ） 三 填空题 1．栈是_______的线性表，其运算遵循_______的原则。 3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。 6．两个栈共享空间时栈满的条件_______。 7．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。 9．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。 10. 顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。 12. 循环队列的引入，目的是为了克服_______。 13．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M= _______。 14．________又称作先进先出表。 15. 队列的特点是_______。 16．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。 17. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。 18．判断循环队列的满与空的方法是_____ _和__ ____。