【数据结构】——栈、队列简答题模板

一、栈

（一）栈的基本概念

1、简述栈的特性。

答：栈是被限制存取点的线性表，只允许在一端进行插入或删除操作，栈遵循的原则是先进后出（FILO），即后进的元素先被取出来。

（二）栈的应用

1、栈有哪些应用场景？（试举例至少三种）

答：栈有以下应用场景：
①递归及函数调用；
②表达式求值（例如，中后缀表达式、括号匹配等等）；
③进制转换（例如，十进制数转为二进制数等等）；
④迷宫求解；
⑤缓存机制；
⑥用栈对二叉树进行前、中、后序遍历；
⑦用栈模拟队列。

2、栈的操作原则是什么？举出两个栈的应用例子。

答：栈的操作原则是先进后出，例如用栈对二叉树进行前、中、后序遍历以及用栈模拟队列等等。

3、简述用两个栈模拟一个队列的基本思想。

答：首先，定义两个栈S1和S2，将所有元素依次入栈S1，然后再依次出栈并进入栈S2，再从栈S2出栈。

（三）栈的代码实现

1、写出顺序存储结构的顺序栈的结构体、栈空、栈满、进栈及出栈的关键代码。

答：①顺序栈的结构体：

#define MaxSize 20	//可自行设置
typedef struct {int data[MaxSize];	//存放栈中元素 ，使用数组int top;	//栈顶指针 ，记录栈顶元素的位置 
} SqStack;	//顺序栈的类型定义 

②判断顺序栈是否为空栈的条件是S.top==-1。
③判断顺序栈是否为满栈的条件是S.top==MaxSize-1。
④将一个元素插入顺序栈中，即进栈，

++S.top;	//top指针始终指向栈顶，新的元素进栈，所以指针先加1
S.data[S.top]=x;	//将进栈元素的值传入并入栈

这两行代码也可以使用一行代码：S.data[++S.top]=x直接替换。
⑤将一个元素从顺序栈中删除，即出栈，

x=S.data[S.top];	//出栈
S.top--;	//指针减1

这两行代码也可以使用一行代码：x=S.data[S.top–]直接替换。

（四）递归算法

1、递归算法包括哪两个部分？简述递归的步骤。

答：一个递归算法必须包括终止条件和递归部分，当递归的条件不满足时，此时递归结束返回，否则继续进行递归操作。

2、简述递归算法的优缺点。

答：递归算法的代码简洁明确，其可读性好，但是其时间复杂度和空间复杂度较大，且在调用栈时可能会产生溢出。

（五）栈与队列的区别

1、简述栈和队列的相同点和不同点。

答：①不同点：运算规则不同，栈遵循的原则是先进后出，而队列的原则是先进先出，栈只允许在一端进行插入、删除操作，而队列只允许在一端进行插入、另一端进行删除操作。另外，两个用途不同，栈由于子程序调用和保护现场，而队列用于多道作业处理、指令寄存及其他运算等等；
②相同点：都是操作受限的线性表，逻辑结构相同，且存储表示也相同（顺序存储结构和链式存储结构）。

二、队列

（一）队列的基本概念

1、队列的“先进先出”的特性是指什么？

答：队列遵循的原则是先进先出，其特性是指最后插入队列中的元素总是最后被删除。

（二）队列的应用

1、队列有哪些应用？

答：队列的应用场景有以下：
（1）缓冲区（例如计算机与打印机中间的打印数据缓冲区）；
（2）页面替换算法；
（3）图的广度优先搜索、树的层次遍历，都借助到了队列的基本思想。

（三）循环队列的基本概念

1、怎么解决队列“假溢出”的问题？并写出相关的代码。

答：将存储队列的一维数组首尾相连成环，形成循环队列，其中队头指针、队尾指针加1时通过取余运算实现，从而防止队列的“假溢出”。进对针对队尾指针，即Q.rear=（Q.rear+1）%MAXSIZE，出队针对队头指针，即Q.front=（Q.front+1）%MAXSIZE。

2、什么是循环队列？给出循环队列中元素个数的计算式（设最大长度为N，队首指针FRONT，队尾指针REAR）。

答：循环队列也就是将顺序队列中的一维数组首尾相连成环，即在逻辑上视为一个环连接起来，让队首指针和队尾指针沿着环走；循环队列中元素个数的计算式为（REAR-FRONT+N）%N。