3.1 栈和队列的定义和特点

栈和队列时限定插入和删除只能在表的“端点”进行的线性表

栈和队列是线性表的子集（是插入和删除位置受限的线性表）

栈：先进后出（后进先出）

由于栈的操作具有先进后出的固有特性，使得栈称为程序设计中的有用工具。另外，如果问题求解过程具有“先进后出”的天然特性的话，则求解的算法中也必然需要利用“栈”

比如：

• 数制转换、表达式求值
• 括号匹配的检验
• 八皇后问题
• 行编辑程序
• 迷宫求解
• 函数调用
• 递归调用的实现

队列：先进先出

由于队列的操作具有先进先出的特性，使得队列称为程序设计中解决类似排队问题的有用工具

• 脱机打印输出：按申请的先后顺序依次输出
• 多用户系统中，多个用户排成队，分时地循环使用CPU和主存
• 按用户的优先级排成多个队，每个优先级一个队列
• 实时控制系统中，信号按接受的向后顺序依次进行处理
• 网络电文传输，按到达的时间先后顺序依次进行

3.1.1 栈的定义和特点

栈（stack）是一个特殊的线性表，是限定仅在一端（通常是表尾）进行插入和删除操作的线性表

又称先进后出（First In Lirst Out）的线性表，简称FILO结构 （或LIFO）

相关概念

• 仅在表尾进行插入、删除操作的线性表
• 表尾（即an端）称为栈顶 Top；表头（即a1端）称为栈底Base

插入元素到栈顶（即表尾）的操作，称为入栈 “入”= 压入 = push

从栈顶（即表尾）删除最后一个元素的操作，称为出栈 “出”= 弹出 = pop

示意图

栈与一般线性表的区别

3.1.2 队列的定义和特点

队列(queue)是一种先进先出(First In First Out) FIFO的线性表。在表一端插入（表尾），在另一端（表头）删除

相关概念：

• 定义：只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表（头删尾插）
• 逻辑结构：与线性表相同，仍为一对一关系
• 存储结构：顺序队或链队，以循环顺序队列更常见
• 运算规则：只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则
• 实现方式：关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同

3.2 案例引入

3.2.1 进制转换

把十进制数159转换成八进制数 ps：这边不理解的可以看我之前写的计组笔记

这时候就可以用栈

3.2.2 括号匹配的检验

假设表达式中允许包含两种括号：圆括号和方括号

其嵌套的顺序随意，即：

1. （ [ ] ( ) ）或 [ ( [ ] [ ] ) ] 为正确格式
2. [ ( ] ) 为错误格式
3. ( [ ( ) ) 或 ( ( ) ] ) 为错误格式

例如：检验 ( ( ) ] ) 是否匹配

• 可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况
• 在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论

• 当遇到某一个右括号时，栈已空，说明到目前为止，右括号多余左括号
• 从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况
• 算数表达式输入完毕，但栈中还没有匹配的左括号，说明左括号多余右括号

3.2.3 表达式求值

这里介绍的算法是由运算符优先级确定运算顺序的对表达式求值算法 ———算符优先算法

表达式组成：

• 操作数(operand)：常数、变量
• 运算符(operator)：算数运算符、关系运算符和逻辑运算符
• 界限符(delimiter)：左右括弧和表达式结束符

任何一个算术表达式都有操作数（常数、变量）、算术运算符（+、-、*、/）和界限符（括号、表达式结束符‘#’、虚设的表达式起始符‘#’）组成。后两者统称为算符 例如：# 3 * (7 - 2) #

为了实现表达式求值。需要设置两个栈：

• 一个是算符栈OPTR，用于寄存运算符
• 另一个称为操作数栈OPND，用于寄存运算数和运算结果

求值的处理过程是自左至右扫描表达式的每一个字符

• 当扫描的是运算符，则将其压入栈OPND
• 当扫描的是运算符时

• 若这个运算符比OPTR栈顶运算符的优先级高，则入栈OPTR，继续向后处理
• 若这个运算符比OPTR栈顶运算符优先级低，则从OPND栈中弹出两个运算数，从栈OPTR中弹出栈顶运算符进行运算，并将运算结果压入OPND

• 继续处理当前字符，直到遇到结束符为止

3.2.4 舞伴问题

假设在舞会上，男士和女士各自排成一队。舞会开始时，依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不相同，则较长的那一队中未配对着等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题

显然，先入队的男士或女士先出队配成舞伴。因此该问题具有典型的先进先出的特性，可以用队列作为算法的数据结构

• 首先构造两个队列
• 依次将队头元素出队配成舞伴
• 某队为空，则另外一对等待着则是下一舞曲第一个可获得舞伴的人

3.3 栈的表示和操作的实现

3.3.1 栈的抽象数据类型定义

由于栈本身就是线性表，于是栈也有顺序存储和链式存储两种实现方式

• 栈的顺序存储：顺序栈
• 栈的链式存储：链式栈

3.3.2 顺序栈

存储方式：同一般线性表的顺序存储结构完全相同，利用一组地址连续的存储单元依次存放至栈底到栈顶的数据元素。栈底一般在低地址端

• 附设top指针，指示栈顶元素在顺序栈中的位置
• 另设base指针，指示栈底元素在顺序栈中的位置
• 另外，用stacksize表示栈可使用的最大容量

但是，为了方便操作，通常top指示真正的栈顶元素之上的下标地址

例如

使用数组作为顺序栈存储方式的特点：简单、方便、但易产生溢出（数组大小固定）

• 上溢(overflow)：栈已经满，又要压入元素
• 下溢(underflow)：栈已经空，还要弹出元素

注：上溢是一种错误，使问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束

定义

typedef struct {
	SElemType* base;	// 栈底指针
	SElemType* top;		// 栈顶指针
	int stackSize;		// 栈的大小
}sequenStack;

图解：

这里我们元素类型定义为char

#define MAXSIZE 100

typedef struct {
	char* base;		// 栈底指针
	char* top;		// 栈顶指针
	int stackSize;	// 栈的大小

}sequenStack;

初始化

构造一个空栈，让栈顶指针等于栈底指针

/*******************************************************************************************************************************
 * @description：初始化栈
 * @param：s	指向栈的指针
 * @return：	状态码
 */
status initSequenStack(sequenStack* s)
{
	s->base = (char*)malloc(MAXSIZE * sizeof(char));
	if (!s->base) {
		exit(OVERFLOW);
	}
	s->top = s->base;
	s->stackSize = MAXSIZE;
	return OK;
}

判空

/*******************************************************************************************************************************
 * @description：判断栈是否为空
 * @param：s	栈
 * @return：	空返回 1；否则返回 0
 */
status isSequenStackEmpty(sequenStack s)
{
	if (s.top == s.base) {
		return TRUE;
	}
	else {
		return FALSE;
	}
}

求长度

/*******************************************************************************************************************************
 * @description：求顺序栈长度
 * @param：s	栈
 * @return：	栈的长度
 */
int getSequenStackLength(sequenStack s)
{
	return s.top - s.base;
}

清空

/*******************************************************************************************************************************
 * @description：清空顺序栈
 * @param：s	指向栈的指针
 * @return：	状态码
 */
status clearSequenStack(sequenStack* s)
{
	if ((*s).base)
		(*s).top = (*s).base;
	return OK;
}

销毁

/*******************************************************************************************************************************
 * @description：销毁顺序栈
 * @param：s	栈
 * @return：	状态码
 */
status destroySequenStack(sequenStack s)
{
	if (s.base) {
		free(s.base);
	}
	s.base = NULL;
	s.top = NULL;
	s.stackSize = 0;
	return OK;
}

入栈

算法步骤：

1. 先判断是否栈满，若满则出错（上溢）
2. 元素e压入栈顶
3. 栈指针加1

/*******************************************************************************************************************************
 * @description：入栈
 * @param：s	栈
 * @param：e	要入栈的元素
 * @return：	状态码
 */
status pushSequenStack(sequenStack* s, char e)
{
	if (s->top - s->base >= s->stackSize) {
		return ERROR;
	}
	*s->top++ = e;
	return OK;
}

出栈

算法步骤：

1. 判断是否栈空，若空则出错（下溢）
2. 获取栈顶元素e
3. 栈顶指针减1

/*******************************************************************************************************************************
 * @description：出栈
 * @param：s	指向栈的指针
 * @param：e	用于返回要出栈的元素
 * @return：	状态码
 */
status popSequenStack(sequenStack* s, char* e)
{
	if (s->top == s->base) {
		return ERROR;
	}
	*e = *--s->top;
	return OK;
}

3.3.3 链式栈

链式栈是运算受限的单链表，只能在链表头部进行操作。所以定义形式和单链表类似

typedef struct StackNode {
	char data;
	struct StackNode* next;
}stackNode, * linkStack;

注意：

• 链式栈中指针的方向，与链表的指针方向相反
• 链栈的头指针就是栈顶
• 不需要头结点
• 基本不存在栈满的情况
• 空栈相当于头指针指向空
• 插入和删除仅在栈顶处执行

初始化

/*******************************************************************************************************************************
 * @description：初始化链式栈
 * @param：s	指向链栈的头指针
 * @return：	状态码
 */
status initLinkStack(linkStack* s)
{
	(*s) = NULL;
	return OK;
}

判空

/*******************************************************************************************************************************
 * @description：判空
 * @param：s
 * @return：	空返回 1；否则返回 0
 */
status isLinkStackEmpty(linkStack* s)
{
	if (*s == NULL)
		return TRUE;
	else
		return FALSE;
}

入栈

/*******************************************************************************************************************************
 * @description：入栈
 * @param：s	栈顶指针
 * @param：e	要插入的元素
 * @return：	状态码
 */
status pushLinkStack(linkStack* s, char e)
{
	linkStackNode* p = (linkStackNode*)malloc(sizeof(linkStackNode));
	if (!p)
		return OVERFLOW;
	p->data = e;
	p->next = *s;
	*s = p;
	return OK;
}

出栈

/*******************************************************************************************************************************
 * @description：出栈
 * @param：s	栈顶指针
 * @param：e	用于返回被删除的元素
 * @return：	状态码
 */
status popLinkStack(linkStack* s, char* e)
{
	linkStackNode* p;
	if (isLinkStackEmpty(s))
		return ERROR;
	*e = (*s)->data;
	p = *s;
	*s = (*s)->next;
	free(p);
	return OK;
}

取栈顶元素

/*******************************************************************************************************************************
 * @description：取栈顶元素
 * @param：s	栈顶指针
 * @return：	栈顶元素
 */
char getLinkStackTopElement(linkStack* s)
{
	if (isLinkStackEmpty(s))
		return ERROR;

	return (*s)->data;;
}

3.4 栈与递归

3.4.1 递归的定义

• 若一个对象部分地包含自己，或用它自己给自己定义，则称这个对象是递归的
• 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程

• 例如：递归求n的阶乘

以下三种情况常常用到递归方法：

• 递归定义的数学函数：阶乘、斐波那契数列
• 具有递归特性的数据结构：二叉树、广义表
• 可递归求解的问题：迷宫问题

递归问题：用分治法求解

分治法：对于一个较为复杂的问题，能过分解成几个相对简单的且解法相同或类似的子问题来求解

必备的三个条件：

1. 能将一个问题转变为一个新问题，而新问题与原问题的解话相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的
2. 可以通过上述转发而使问题简化
3. 必须有一个明确的递归出口，或称递归的边界

求解阶乘 n！的过程

递归的优缺点：

• 优点：结构清晰，程序易读
• 缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息，时间开销大

递归 -> 非递归

方法1：尾递归、单向递归 -> 循环结构

方法2：自用栈模拟系统的运行时栈

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

3.5.1 队列的抽象数据类型定义

3.5.2 顺序队列

定义

typedef struct {
	QElementType* base;	// 初始化的动态分配存储空间
	int front;			// 头指针
	int rear;			// 尾指针
}suquenQueue;

入队和出队

队列溢出

只有当front = 0，rear = MAXQUEUESIZE时，再入队--真溢出

front ≠ 0，rear = MAXQUEUESIZE时，再入队--假溢出

两种解决假上溢办法：

1. 依次移动队列里的每一个元素 (时间复杂度高)
2. 用循环队列：base[0]接在base[MAXQUEUESIZE -1]之后，若 rear + 1 = MAXQUEUESIZE，则令 rear = 0

实现方法：利用模（mod，C语言中：%）运算

插入元素：

• Q.base[Q.rear] = x
• Q.rear = (Q.rear +1) % MAXQUEUESIZE

当 front ≠ 0 时，只要rear加1取余最大长度，说明已经到头了，这时候自动等于 0；否则还是原来的值

删除元素：

• x = Q.base[s.front]
• Q.front = (Q.front + 1) % MAXQUEUESIZE

所以对于循环队列：front = rear，队列有可能是队空，也可能是队满

解决方案：

1. 另外设一个标志以区别队空、队满
2. 另设一个变量，记录元素个数
3. 少用一个元素空间

假设最MAXQUEUESIZE为：6，少用一个元素空间，所以只能放 5 个

此时rear=4，front=5

（rear+1)%6 = front = 5

初始化

/*******************************************************************************************************************************
 * @description：初始化队列
 * @param：		Q指向队列的指针
 * @return：	状态码
 */
status initSequenQueue(suquenQueue* Q)
{
	(*Q).base = (char*)malloc(MAXQUEUESIZE * sizeof(char));
	if (!(*Q).base)
	{
		exit(OVERFLOW);
	}
	(*Q).front = (*Q).rear = 0;
	return OK;
}

求队列的长度

/*******************************************************************************************************************************
 * @description：求队列的长度
 * @param：Q	队列
 * @return：	队列的长度
 */
int getSequenQueueLength(suquenQueue Q)
{
	return (Q.rear - Q.front + MAXQUEUESIZE) % MAXQUEUESIZE;
}

入队

/*******************************************************************************************************************************
 * @description：入队
 * @param：Q	队列指针
 * @param：e	要入队的元素
 * @return：	状态码
 */
status enSequenQueue(suquenQueue* Q, char e)
{
	if (((*Q).rear + 1) % MAXQUEUESIZE == (*Q).front)
	{	// 队满
		return ERROR;
	}
	(*Q).base[(*Q).rear] = e;
	(*Q).rear = ((*Q).rear + 1) % MAXQUEUESIZE;
	return OK;
}

出队

/*******************************************************************************************************************************
 * @description：出队
 * @param：Q	队列指针
 * @param：e	用于返回删除的元素
 * @return：	状态码
 */
status deSequenQueue(suquenQueue* Q, char* e)
{
	if ((*Q).front == (*Q).rear)
	{	// 队空
		return ERROR;
	}
	*e = (*Q).base[(*Q).front];
	(*Q).front = ((*Q).front + 1) % MAXQUEUESIZE;
	return OK;
}

取队头元素

/*******************************************************************************************************************************
 * @description：取队头元素
 * @param：Q	队列
 * @return：	队头元素
 */
char getSequenQueueHead(suquenQueue Q)
{
	if (Q.front == Q.rear)
	{	// 队空
		return ERROR;
	}
	return  Q.base[Q.front];
}

3.5.3 链式队列

定义

typedef struct Qnode {
	char data;
	struct Qnode* next;
}linkQueueNode, * QueuePtr;


typedef struct {
	QueuePtr front;	// 头指针
	QueuePtr rear;	// 尾指针
}linkQueue;

初始化

/*******************************************************************************************************************************
 * @description：初始化
 * @param：Q	指向队列的指针
 * @return：	状态码
 */
status initLinkQueue(linkQueue* Q)
{
	(*Q).front = (*Q).rear = (QueuePtr)malloc(sizeof(linkQueueNode));
	if (!(*Q).front){
		exit(OVERFLOW);
	}
	(*Q).front->next = NULL;
	return OK;
}

销毁

/*******************************************************************************************************************************
 * @description：销毁
 * @param：Q	指向队列的指针
 * @return：	状态码
 */
status destroyLinkQueue(linkQueue* Q)
{
	while ((*Q).front)
	{
		QueuePtr temp;
		temp = (*Q).front->next;
		free((*Q).front);
		(*Q).front = temp;
	}
	return OK;
}

入队

/*******************************************************************************************************************************
 * @description：入队
 * @param：Q	指向队列的指针
 * @param：e	要入队的元素
 * @return：	状态码
 */
status enLinkQueue(linkQueue* Q, char e)
{
	QueuePtr temp;
	temp = (QueuePtr)malloc(sizeof(linkQueueNode));
	if (!temp){
		exit(OVERFLOW);
	}
	temp->data = e;
	temp->next = NULL;
	(*Q).rear->next = temp;
	(*Q).rear = temp;
	return OK;
}

出队

/*******************************************************************************************************************************
 * @description：出队
 * @param：Q	指向队列的指针
 * @param：e	用于接收出队的元素
 * @return：	状态码
 */
status deLinkQueue(linkQueue* Q, char* e)
{
	if ((*Q).front == (*Q).rear)
	{	// 队空
		return ERROR;
	}
	QueuePtr temp;
	temp = (*Q).front->next;
	*e = temp->data;
	(*Q).front->next = temp->next;
    
	if ((*Q).rear == temp)
	{	// 如果队列中只有一个元素
		(*Q).rear = (*Q).front;
	}
	free(temp);
	return OK;
}

取队头元素

/*******************************************************************************************************************************
 * @description：取队头元素
 * @param：Q	队列
 * @return：	队头元素
 */
char getLinkQueueHead(linkQueue Q)
{
	if (Q.front == Q.rear)
	{	// 队空
		return ERROR;
	}
	return Q.front->next->data;
}