整本书的知识点，点击右方链接：整本书笔记知识点

文章目录

• 三、栈和队列
• • 3.1、栈和队列的定义和特点
  • • 3.1.1、栈的定义和特点
    • 3.1.2、队列的定义和特点
  • 3.2、案例引入
  • 3.3、栈的表示和操作的实现
  • • 3.3.1、栈的类型定义
    • 3.3.2、顺序栈的表示和实现
    • 3.3.3、链栈的表示和实现
  • 3.4、栈与递归
  • 3.5、队列的表示和操作的实现
  • • 3.5.1、队列的类型定义
    • 3.5.2、循环队列——队列的顺序表示和实现
    • 3.5.3、链队——队列的链式表示和实现
  • 3.6、案例分析与实现
  • 第三章小结
  • 第三章习题

 

 

三、栈和队列

3.1、栈和队列的定义和特点

3.1.1、栈的定义和特点

• 栈：受约束的线性表，只允许栈顶元素入栈和出栈

• 对栈来说，表尾端称为栈顶，表头端称为栈底，不含元素的空表称为空栈

• 先进后出，后进先出

  

3.1.2、队列的定义和特点

• 队列：受约束的线性表，只允许在队尾插入，在队头删除
• 先进先出，后进后出

3.2、案例引入

略

3.3、栈的表示和操作的实现

3.3.1、栈的类型定义

栈也有两种存储表示方法，分别称为顺序栈和链栈。

3.3.2、顺序栈的表示和实现

顺序栈的存储结构

//－－－－－ 顺序栈的存储结构－ －－－－
#define MAXSIZE 100 		//顺序栈存储空间的初始分配址
typedef struct{SElemType *base; 		//栈底指针SElemType *top; 		//栈顶指针int stacksize; 			//栈可用的最大容扯
}SqStack;

top 指栈顶元素后一位置

 

S.top == 0时，栈空

 

S.top == stacksize 时，栈满

一、 顺序栈的初始化

二、顺序栈的入栈：

 

三、顺序栈的出栈：

 

四、顺序栈取栈顶元素：

3.3.3、链栈的表示和实现

链栈示意图：

链栈的存储结构：

一、链栈的初始化

二、链栈的入栈

三、链栈的出栈

四、链栈取栈顶元素

3.4、栈与递归

栈与递归知识点看小结思维导图

3.5、队列的表示和操作的实现

3.5.1、队列的类型定义

队列的操作与栈类似，不同的是，删除时在表的头部(即队头)进行。

3.5.2、循环队列——队列的顺序表示和实现

队列也有两种存储表示，顺序表示和链表表示。

队列的顺序存储结构表示：一组地址连续的存储单元存储

单纯的顺序队列有"假溢出"的问题。

尾指针无法插入元素，队列的实际可用空间并未占满，这种现象称为 “假溢出＂

为了避免 ”假溢出“，可以将顺序队列变为 一 个环状的空间

• 循环队列解决了“假溢出”(下标溢出)
• 没有解决真溢出（空间溢出）

在这种情况下， 如何区别队满还是队空呢？

1、少用一个元素空间， 即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队空的条件不变， 即当头、 尾指针的值相同时， 则认为队空；而当尾指针在循环意义上加1后是等于头指针， 则认为队满。

1. 队空的条件： Q.front == Q.rear
2. 队满的条件： (Q.rear+ 1)%MAXQSIZE == Q.front
3. 入队：Q.rear = (Q.rear + 1)% MAXQSIZE
4. 出队：Q.front = (Q.front + 1)% MAXQSIZE
5. 当前元素个数： (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE

如图 3.14 (d)所示， 当J7、 J8、 J9 进入图 3.14(a)所示的队列后， (Q.rear+ 1)%MAXQSIZE 的值等于 Q.front, 此时认为队满。

2、另设一个标志位以区别队列是 “空” 还是 “满＂。

一、循环队列的初始化

二、循环队列求队列长度

三、循环队列入队

四、循环队列出队

五、循环队列取队头元素

3.5.3、链队——队列的链式表示和实现

队列的链式存储结构

一、链队的初始化

二、链队的入队

三、链队的出队

链队在出队前也需要判断队列是否为空，不同的是，链队在出队后需要释放出队头元素的所占空间

①、判断队列是否为空，若空则返回ERROR。

②、临时保存队头元素的空间，以备释放。

③、修改队头指针，指向下一个结点。

④、判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值， 指向头结点。

⑤、释放原队头元素的空间。

需要注意的是，在链队出队操作时还要考虑当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）

四、取链队的队头元素

3.6、案例分析与实现

顺序栈的基本操作

链栈的基本操作

循环队列的基本操作

链队的基本操作

第三章小结

栈是限定仅在表尾进行插入或删除的线性表，又称为后进先出的线性表。栈有两种存储表示，顺序表示（顺序栈） 和链式表示（链栈）。栈的主要操作是进栈和出栈，对于顺序栈的进栈和出栈操作要注意判断栈满或栈空

队列是一种先进先出的线性表。它只允许在表的一端进行插入， 而在另一端删除元素。队列也有两种存储表示，顺序表示（循环队列）和链式表示（链队）

栈和队列的逻辑结构都和线性表一样，数据元素之间存在一对一的关系

循环队列中少用一个元素判断对空或对满时：

• 队空的条件： Q.front == Q.rear
• 队满的条件： (Q.rear+ 1)%MAXQSIZE == Q.front

第三章习题

（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。

A．5，4，3，2，1

B．2，1，5，4，3

C．4，3，1，2，5

D．2，3，5，4，1

答案：C

解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。

A．i B．n-i C．n-i+1 D．不确定

答案：C

解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，…，n，而输出序列的第一个元素为n，说明1，2，3，…，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，…，pi=n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n

答案：D

解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。

（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。

A．x=top->data;top=top->link； B．top=top->link;x=top->link；

C．x=top;top=top->link； D．x=top->link；

答案：A

解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。

（5）设有一个递归算法如下

  int fact(int n) { //n大于等于0if (n <= 0) return 1;else return n * fact(n - 1);}

则计算fact(n)需要调用该函数的次数为（ ）。

A． n+1 B． n-1 C． n D． n+2

答案：A

解释：特殊值法。设n=0，易知仅调用一次fact(n)函数，故选A。

（6）栈在 （ ）中有所应用。

A．递归调用 B．函数调用 C．表达式求值 D．前三个选项都有

答案：D

解释：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。

（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。

A．队列 B．栈 C． 线性表 D．有序表

答案：A

解释：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线性表。

（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。

A．2 B．3 C．4 D． 6

答案：B

解释：元素出队的序列是e2、e4、e3、e6、e5和e1，可知元素入队的序列是e2、e4、e3、e6、e5和e1，即元素出栈的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次进入栈，易知栈S中最多同时存在3个元素，故栈S的容量至少为3。

（9）若一个栈以向量V[1…n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( )。

A．top++; V[top]=x; B．V[top]=x; top++;

C．top–; V[top]=x; D．V[top]=x; top–;

答案：C

解释：初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V[1…n]中，所以进栈时top指针先下移变为n，之后将元素x存储在V[n]。

（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（　）数据结构最佳。

A．线性表的顺序存储结构 B．队列

C. 线性表的链式存储结构 D. 栈

答案：D

解释：利用栈的后进先出原则。

（11）用链接方式存储的队列，在进行删除运算时（　）。

A. 仅修改头指针 B. 仅修改尾指针

C. 头、尾指针都要修改 D. 头、尾指针可能都要修改

答案：D

解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。

（12）循环队列存储在数组A[0…m]中，则入队时的操作为（　）。

A. rear=rear+1 B. rear=(rear+1)%(m-1)

C. rear=(rear+1)%m D. rear=(rear+1)%(m+1)

答案：D

解释：数组A[0…m]中共含有m+1个元素，故在求模运算时应除以m+1

（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（　）。

A. (rear+1)%n = = front B. rear == front

C．rear+1 = = front D. (rear-l)%n == front

答案：B

解释：最大容量为n的循环队列，队满条件是(rear+1)%n = = front，队空条件是rear == front。

（14）栈和队列的共同点是（　）。

A. 都是先进先出 B. 都是先进后出

C. 只允许在端点处插入和删除元素 D. 没有共同点

答案：C

解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素

（15）一个递归算法必须包括（　）。

A. 递归部分 B. 终止条件和递归部分

C. 迭代部分 D. 终止条件和迭代部分

答案：B