1.栈
2.队列
3.栈和队列面试题
正文开始：
1.
栈
1.1
栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
进行数据插入和删除操作的一端
称为栈顶，另一端称为栈底。
栈中的数据元素遵守
后进先出
LIFO
（
Last In First Out
）的原则。
压栈：栈的插入操作叫做进栈
/
压栈
/
入栈，
入数据在栈顶
。
出栈：栈的删除操作叫做出栈。
出数据也在栈顶
1.2
栈的实现
栈的实现一般可以使用
数组或者链表实现
，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
STDataType _a[N];
int _top; // 栈顶
}Stack;
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
2.
队列
2.1
队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有
先进先出
FIFO(First In First Out) 入队列：
进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
2.2
队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
// 链式结构：表示队列
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
补充几个算法题：
4.
概念选择题
选择题
1. 循环队列的存储空间为 Q ( 1 : 100 ) ，初始状态为 front = rear = 100 。经过一系列正常的入队与退队操作后，front = rear = 99 ，则循环队列中的元素个数为（ ）A 100B 2C 99D 02. 下列与队列应用的是（）A 函数的递归调用B 数组元素的引用C 多重循环的执行D 先到先服务的作业调度3. 一个栈的初始状态为空。现将元素 1 、 2 、 3 、 4 、 5 、 A 、 B 、 C 、 D 、 E 依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。A 12345 ABCDEB EDCBA54321C ABCDE12345D 54321 EDCBA4. 若进栈序列为 1 , 2 , 3 , 4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）A 1 , 4 , 3 , 2B 2 , 3 , 4 , 1C 3 , 1 , 4 , 2D 3 , 4 , 2 , 1
答案
1.D2.D3.B4.C
栈（Stack）的特点：
- 后进先出（LIFO）：栈只允许在栈顶进行插入（称为“压入”）和删除（称为“弹出”）操作。因此，最后一个被压入栈的元素将是第一个被弹出的元素。
- 操作限制：栈的操作局限于栈顶，其他位置的元素无法直接访问和操作。
- 存储空间限制：栈的存储空间是有限的，当栈的元素数量超过其容量时，会发生栈溢出错误。
- 递归应用：栈的结构特点使得它在递归算法的实现中非常有用。递归函数调用时，每次进入一层递归都需要保存当前的状态，包括参数、局部变量等信息，在递归返回时再恢复状态。
栈的应用场景包括函数调用、表达式求值、撤销操作以及浏览器的前进和后退功能等。
队列（Queue）的特点：
- 先进先出（FIFO）：队列允许在一端进行插入（称为“入队”）操作，在另一端进行删除（称为“出队”）操作。因此，第一个进入队列的元素将是第一个被移出的元素。
- 核心操作：队列的三大核心操作是入队、出队和取队首元素。
- 遍历速度：队列基于地址指针进行遍历，可以从头部或尾部进行，但不能同时遍历。由于遍历过程不影响数据结构，队列的遍历速度相对较快。
队列的应用场景包括消息传递、打印任务队列等。例如，在一个打印任务中，新的打印任务会被添加到队列的末尾，而打印机则从队列的头部取出任务进行打印，这样就实现了先进先出的管理。
