第3讲：栈和队列

目录

• 本节目标
• 1. 栈
  • 1.1 栈的概念及结构
  • 1.2 栈的实现
• 2. 队列
  • 2.1 队列的概念及结构
  • 2.2 队列的实现
• 3. 栈和队列面试题
• 4. 概念选择题
  • 选择题
  • 答案

本节目标

1. 栈
2. 队列
3. 栈和队列面试题

1. 栈

1.1 栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈typedefintSTDataType;#defineN10typedefstructStack{STDataType _a[N];int_top;// 栈顶}Stack;// 支持动态增长的栈typedefintSTDataType;typedefstructStack{STDataType*_a;int_top;// 栈顶int_capacity;// 容量}Stack;// 初始化栈voidStackInit(Stack*ps);// 入栈voidStackPush(Stack*ps,STDataType data);// 出栈voidStackPop(Stack*ps);// 获取栈顶元素STDataTypeStackTop(Stack*ps);// 获取栈中有效元素个数intStackSize(Stack*ps);// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0intStackEmpty(Stack*ps);// 销毁栈voidStackDestroy(Stack*ps);

2. 队列

2.1 队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。

入队列：进行插入操作的一端称为队尾；出队列：进行删除操作的一端称为队头。

2.2 队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

// 链式结构：表示队列typedefstructQListNode{structQListNode*_pNext;QDataType _data;}QNode;// 队列的结构typedefstructQueue{QNode*_front;QNode*_rear;}Queue;// 初始化队列voidQueueInit(Queue*q);// 队尾入队列voidQueuePush(Queue*q,QDataType data);// 队头出队列voidQueuePop(Queue*q);// 获取队列头部元素QDataTypeQueueFront(Queue*q);// 获取队列队尾元素QDataTypeQueueBack(Queue*q);// 获取队列中有效元素个数intQueueSize(Queue*q);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0intQueueEmpty(Queue*q);// 销毁队列voidQueueDestroy(Queue*q);

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

3. 栈和队列面试题

1. 括号匹配问题。20. 有效的括号
2. 用队列实现栈。225. 用队列实现栈
3. 用栈实现队列。232. 用栈实现队列
4. 设计循环队列。622. 设计循环队列

4. 概念选择题

选择题

1. 一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。

   • A.12345ABCDE
   • B.EDCBA54321
   • C.ABCDE12345
   • D.54321EDCBA

2. 若进栈序列为1,2,3,4，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）。

   • A.1,4,3,2
   • B.2,3,4,1
   • C.3,1,4,2
   • D.3,4,2,1

3. 循环队列的存储空间为Q(1:100)，初始状态为front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为（）。

   • A. 1
   • B. 2
   • C. 99
   • D. 0 或者 100

4. 以下（ ）不是队列的基本运算？

   • A. 从队尾插入一个新元素
   • B. 从队列中删除第i个元素
   • C. 判断一个队列是否为空
   • D. 读取队头元素的值

5. 现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？（假设队头不存放数据）

   • A.(rear - front + N) % N + 1
   • B.(rear - front + N) % N
   • C.(rear - front) % (N + 1)
   • D.(rear - front + N) % (N - 1)

答案

1. B
2. C
3. D
4. B
5. B