数据结构 第三章（栈和队列）【下】

写在前面：

1. 本系列笔记主要以《数据结构（C语言版）》为参考，结合下方视频教程对数据结构的相关知识点进行梳理。所有代码块使用的都是C语言，如有错误欢迎指出。
2. 视频链接：第01周a--前言_哔哩哔哩_bilibili

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

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

（1）在队列的顺序存储结构中，同样要用一组地址连续的存储单元依次存放从队头到队尾的元素之外，另外需附设两个整型变量front和rear分别指示队头元素及队尾元素的位置（后面分别称为头指针和尾指针）。队列的顺序存储结构表示如下：

#define MAXSIZE 100
 
typedef int QElemType;  //以整型为例
 
enum Status
{
	OVERFLOW,
	ERROR,
	OK
};
 
typedef struct SqQueue  //常用的循环队列
{
	QElemType *base;  //存储空间的基地址
	int front;        //头指针
	int rear;         //尾指针
}SqQueue;
 
typedef struct SqQueue_tag  //设有标志的循环队列
{
	QElemType *base;  //存储空间的基地址
	int front;        //头指针
	int rear;         //尾指针
	int tag;          //标志
}SqQueue_tag;

①为在C语言中描述方便起见，约定初始化创建空队列时，令front = rear = 0，每当插入新的队尾元素时尾指针rear增1，每当删除队头元素时头指针front增1，因此在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。

②假设当前队列分配的最大空间为6，则当队列处于上图(d)所示的状态时不可再继续插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致程序的非法操作错误，事实上，此时队列的实际可用空间并未占满，所以这种现象称为“假溢出”，这是由“队尾入队，队头出队”这种受限制的操作造成的。一个比较巧妙的解决办法是将顺序队列变为一个环状的空间，称这样的队列为循环队列，头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增1”的操作可用“模”运算来实现，通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。

③对于循环队列，不能以头、尾指针的值是否相同来判别队列空间是“满”还是“空”，在这种情况下，有两种处理方法：

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

[2]另设一个标志位以区别队列是“空”还是“满”。（还可以改为增设一个整型变量统计当前队列中的元素个数，以此为判断队满的依据，逻辑是相似的）

（2）少用一个元素空间的循环队列：

①循环队列的初始化操作就是动态分配一个预定义大小为MAXSIZE的数组空间。

Status InitQueue(SqQueue *Q)  //初始化
{
	Q->base = (QElemType*)malloc(sizeof(QElemType)*MAXSIZE);  //为队列分配一个最大容量为MAXSIZE的数组空间，base指向数组空间的首地址。
	if (Q->base == NULL)
		return OVERFLOW;
	Q->front = Q->rear = 0;  //将头指针和尾指针置为0，队列为空
	return OK;
}

②对于非循环队列、尾指针和头指针的差值便是队列长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE，然后与MAXSIZE求余。

int QueueLength(SqQueue Q)  //求队列长度
{
	return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

③入队操作是指在队尾插入一个新的元素。

Status EnQueue(SqQueue *Q, QElemType e)  //入队
{
	if ((Q->rear + 1) % MAXSIZE == Q->front)  //若尾指针在循环意义上加1后等于头指针，表明队满
		return ERROR;
	Q->base[Q->rear] = e;                 //新元素插入队尾
	Q->rear = (Q->rear + 1) % MAXSIZE;    //队尾指针加1
	return OK;
}

④出队操作是指将队头元素删除。

Status DeQueue(SqQueue *Q, QElemType *e)  //出队
{
	if (Q->rear == Q->front)                //若尾指针等于头指针，表明队空
		return ERROR;
	*e = Q->base[Q->front];                 //保存队头元素
	Q->front = (Q->front + 1) % MAXSIZE;    //队头指针加1
	return OK;
}

⑤当队列非空时，取出当前队头元素的值，队头指针保持不变。

QElemType GetHead(SqQueue Q)  //取队头元素
{
	if (Q.front != Q.rear)
		return Q.base[Q.front];
}

（3）另设一个标志位的循环队列：

①循环队列的初始化操作就是动态分配一个预定义大小为MAXSIZE的数组空间，同时需要置标志位为0，表示队列为“空”。

Status InitQueue_tag(SqQueue_tag *Q)  //初始化
{
	Q->base = (QElemType*)malloc(sizeof(QElemType)*MAXSIZE);
	if (Q->base == NULL)
		return OVERFLOW;
	Q->front = Q->rear = 0;  //将头指针和尾指针置为0，队列为空
	Q->tag = 0;              //标志值为0，表示队列为空
	return OK;
}

②对于非循环队列、尾指针和头指针的差值便是队列长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE，然后与MAXSIZE求余。

int Queue_tagLength(SqQueue_tag Q)  //求队列长度
{
	if (Q.tag == 1 && Q.rear == Q.front)
		return MAXSIZE;  //队满，返回最大值
	else
		return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

③入队操作是指在队尾插入一个新的元素，插入一个新元素后，不管怎样队列都已经非空，需要将标志位置为1，当头指针和尾指针相等且标志位为1时，说明队满。

Status EnQueue_tag(SqQueue_tag *Q, QElemType e)  //入队
{
	if (Q->rear == Q->front && Q->tag == 1)  //当头指针和尾指针相等且标志位为1时，说明队满
		return ERROR;
	Q->base[Q->rear] = e;
	Q->rear = (Q->rear + 1) % MAXSIZE;
	Q->tag = 1;
	return OK;
}

④出队操作是指将队头元素删除，删除前需判断队列是否为空（头指针和尾指针相等且标志位为1时，说明队列中没有元素，也就是队空），不为空则开始出队，当出完最后一个元素时，头指针和尾指针相等，此时需要将标志位置0以表队空。

Status DeQueue_tag(SqQueue_tag *Q, QElemType *e)  //出队
{
	if (Q->rear == Q->front && Q->tag == 0)
		return ERROR;
	*e = Q->base[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;
	if (Q->front == Q->rear)
		Q->tag = 0;
	return OK;
}

⑤当队列非空时，取出当前队头元素的值，队头指针保持不变。

QElemType GetHead_tag(SqQueue_tag Q)  //取队头元素
{
	if (Q.front != Q.rear)
		return Q.base[Q.front];
}

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

（1）链队列是指采用链式存储结构实现的队列，通常链队列用单链表来表示。一个链队列需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定，为了操作方便起见，给链队列添加一个头结点，并令头指针始终指向头结点。队列的链式存储结构表示如下：

typedef int QElemType;  //以整型为例
 
typedef struct QNode   //常用的链队列
{
	QElemType data;
	struct QNode* next;
}QNode, *QueuePtr;
 
typedef struct LinkQueue
{
	QueuePtr front; //队头指针
	QueuePtr rear;  //队尾指针
}LinkQueue;
 
enum Status
{
	OVERFLOW,
	ERROR,
	OK
};

（2）链队的初始化操作就是构造一个只有一个头结点的空队。

Status InitQueue(LinkQueue *Q)  //初始化
{
	Q->front = (QNode*)malloc(sizeof(QNode));  //生成新结点作为头结点，队头和队尾指针指向此结点
	Q->rear = Q->front;
	Q->front->next = NULL;    //头结点的指针域置空
	return OK;
}

（3）链队列在入队前不需要判断队是否满，只需要为入队元素动态分配一个结点空间。

Status EnQueue(LinkQueue *Q, QElemType e)  //入队
{
	QNode* p = (QNode*)malloc(sizeof(QNode));  //为入队元素分配结点空间
	p->data = e;                 //将新结点的数据域置e
	p->next = NULL;              //将新结点的指针域置空
	Q->rear->next = p;           //将新结点插入队尾
	Q->rear = p;                 //修改队尾指针
	return OK;
}

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

Status DeQueue(LinkQueue *Q, QElemType *e)  //出队
{
	if (Q->front == Q->rear)     //队列为空
		return ERROR;
	QNode* p = Q->front->next;     //指针p指向队头元素
	*e = p->data;                  //e保存队头元素的值
	Q->front->next = p->next;      //修改头结点指针域，指向“下一个队头”
	if (Q->rear == p)    //最后一个元素被删，队尾指针会变成野指针，需要对其重新赋值
		Q->rear = Q->front;
	free(p);             //释放原队头元素的空间
	return OK;
}

（5）当队列非空时，可以返回当前队头元素的值，队头指针保持不变。

QElemType GetHead(LinkQueue Q)  //取队头元素
{
	if (Q.front != Q.rear)
		return Q.front->next->data;
}

（6）销毁链队列：

Status DestoryQueue(LinkQueue *Q)  //销毁
{
	while (Q->front)
	{
		Q->rear = Q->front->next;
		free(Q->front);
		Q->front = Q->rear;
	}
	return OK;
}

五、算法设计举例

1、例1

（1）问题描述：回文是指正读、反读均相同的字符序列，设计一个算法判定输入的字符串是否为回文。

（2）代码：

#define MAXSIZE 100
typedef int SElemType;  //以整型为例
 
typedef struct SqStack
{
	SElemType* base; //栈底指针
	SElemType* top;  //栈顶指针
	int stacksize;   //栈可用的最大容量
}SqStack;
 
void Stack_work(void)
{
	char str[MAXSIZE * 2];
	scanf("%s", str);
	int n = strlen(str);
	SqStack S;
	InitStack(&S);
	int i;
	for (i = 0; i < n / 2; i++)
	{
		Push(&S, (SElemType)str[i]);
	}
	if (n % 2 != 0)
		i++;
	for (; i < n; i++)
	{
		SElemType tmp;
		Pop(&S, &tmp);
		if (tmp != (SElemType)str[i])
			break;
	}
	if (i == n)
		printf("是回文！\n");
	else
		printf("不是回文！\n");
}

2、例2

（1）问题描述：从键盘输入一整数序列，用栈结构存储输入的整数。当元素不等于-1时，元素进栈；当元素等于-1时，输出栈顶整数并出栈；算法应对栈满等异常情况给出相应信息。

（2）代码：

#define MAXSIZE 100
typedef int SElemType;  //以整型为例
 
typedef struct SqStack
{
	SElemType* base; //栈底指针
	SElemType* top;  //栈顶指针
	int stacksize;   //栈可用的最大容量
}SqStack;
 
void Stack_work(void)
{
	int n;
	printf("请输入整数序列的元素个数：");
	scanf("%d", &n);
	SqStack S;
	InitStack(&S);
	int i = 0;
	while (i < n)
	{
		SElemType s;
		scanf("%d", &s);
		if (s != -1 && i == S.stacksize)
		{
			printf("\n 栈满！\n");
			n--;
		}
		if (s != -1 && i < S.stacksize)
		{
			Push(&S, s);
			i++;
		}
		if (s == -1 && i == 0)
		{
			printf("\n 栈空！\n");
			n--;
		}
		if (s == -1 && i > 0)
		{
			SElemType tmp;
			Pop(&S, &tmp);
			printf("%d ", tmp);
			i--;
		}
	}
}

3、例3

（1）问题描述：从键盘上输入一个后缀表达式，设计算法计算它的值（后缀表达式不用考虑运算符优先级），规定后缀表达式的长度不超过一行，输入以“$”作为结束，操作数之间用空格分隔，操作符只可能有“+”、“-”“*”、“/”4种。

①中缀表达式转为前缀表达式的手算方法：

[1]确定中缀表达式中各个运算符的运算顺序。（只要右边的运算符能先计算，就优先算右边的）

[2]选择下一个运算符，按照「运算符 左操作数 右操作数」的方式组合成一个新的操作数。

[3]如果还有运算符没被处理，就继续第二步。

②中缀表达式转为后缀表达式的手算方法：

[1]确定中缀表达式中各个运算符的运算顺序。（只要左边的运算符能先计算，就优先算左边的）

[2]选择下一个运算符，按照「左操作数 右操作数 运算符」的方式组合成一个新的操作数。

[3]如果还有运算符没被处理，就继续第二步。

③前缀表达式的手算方法：从右往左扫描，每遇到一个运算符，就让运算符右边最近的两个操作数执行对应运算，合体为一个操作数。

④后缀表达式的手算方法：从左往右扫描，每遇到一个运算符，就让运算符左边最近的两个操作数执行对应运算，合体为一个操作数。

⑤用栈实现前缀表达式的计算：

[1]对前缀表达式进行从右至左依次扫描。

[2]当遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（先出栈的是左操作数），并将结果入栈。

[3]重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

⑥用栈实现中缀表达式的计算：

[1]初始化两个栈——运算符栈和操作数栈。

[2]从右至左扫描中缀表达式，遇到操作数时将其压入操作数栈。

[3]若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）。

⑦用栈实现后缀表达式的计算：

[1]对后缀表达式进行从左至右依次扫描。

[2]当遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（先出栈的是右操作数），并将结果入栈。

[3]重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。

⑧用栈实现中缀表达式转前缀表达式：

[1]初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。

[2]从右到左处理各个元素，直到末尾，可能遇到3中情况：

#1 遇到操作数：直接将操作数加入前缀表达式。

#2 遇到界限符：遇到“)”直接入栈，遇到“(”则依次弹出栈内运算符并加入前缀表达式，直到弹出“)”为止。

#3 遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入前缀表达式，若碰到“)”或栈空则停止，之后再把当前运算符入栈。

[3]按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入前缀表达式。

⑨用栈实现中缀表达式转后缀表达式：

[1]初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。

[2]从左到右处理各个元素，直到末尾，可能遇到3中情况：

#1 遇到操作数：直接将操作数加入后缀表达式。

#2 遇到界限符：遇到“(”直接入栈，遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。

#3 遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止，之后再把当前运算符入栈。

[3]按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

（2）代码：

#define MAXSIZE 100
typedef char SElemType;
 
typedef struct SqStack
{
	SElemType* base; //栈底指针
	SElemType* top;  //栈顶指针
	int stacksize;   //栈可用的最大容量
}SqStack;
 
double Postfix(void)
{   //测试用例：200 30+2*$   转换成中缀表达式为(200+30)*2=460
	SqStack OPND;
	InitStack(&OPND);   //操作数栈初始化
	float num = 0.0f;   //数字初始化
	char ch = getchar();  //读入后缀式的第一个字符
	while (ch != '$')
	{
		int i = 0;
		int flag = 0;   //标识操作数是否为小数
		char data[6];    //一个操作数（加上小数点）最多占4位，否则可能出错
		while ((ch >= '0'&&ch <= '9') || ch == '.')
		{   //拼数，将读入的数字或小数点依次保存在字符数组data中
			data[i] = ch;
			i++;
			if (ch == '.')
				flag = 1;
			ch = getchar();
		}
		if (flag == 0)
			data[i] = '.';   //如果操作数没小数点，补上，以便转换
		num = atof(data);    //将字符数组转换为浮点数
		printf("%f\n", num);
		Push(&OPND, num);  //操作数进栈
		SElemType a, b;
		switch (ch)
		{   //遇到操作符，弹出两个数据进行运算，然后压栈
		case ' ':  //遇到空格，继续往下读
			break;
		case '+':
			Pop(&OPND, &b);
			Pop(&OPND, &a); 
			Push(&OPND, a + b); 
			break;
		case '-':
			Pop(&OPND, &b); 
			Pop(&OPND, &a); 
			Push(&OPND, a - b); 
			break;
		case '*':
			Pop(&OPND, &b); 
			Pop(&OPND, &a); 
			Push(&OPND, a * b); 
			break;
		case '/':
			Pop(&OPND, &b); 
			Pop(&OPND, &a); 
			Push(&OPND, a / b); 
			break;
		}
		ch = getchar();
	}
	return GetTop(OPND);
}

4、例4

（1）问题描述：对于一个循环队列（不带标志位），允许它在两端进行插入和删除操作，需要补充从队头插入和从队尾删除的操作函数。

（2）代码：

typedef int QElemType;  //以整型为例
typedef struct SqQueue  //常用的循环队列
{
	QElemType *base;  //存储空间的基地址
	int front;        //头指针
	int rear;         //尾指针
}SqQueue;
 
enum Status
{
	OVERFLOW,
	ERROR,
	OK
};
 
Status EnQueue_front(SqQueue *Q, QElemType e)  //从队头插入（非常用）
{
	if ((Q->rear + 1) % MAXSIZE == Q->front)
		return ERROR;
	Q->front = (Q->front - 1 + MAXSIZE) % MAXSIZE;
	Q->base[Q->front] = e;
	return OK;
}
 
Status DeQueue_rear(SqQueue *Q, QElemType *e)  //从队尾删除（非常用）
{
	if (Q->rear == Q->front)
		return ERROR;
	Q->rear = (Q->rear - 1 + MAXSIZE) % MAXSIZE;
	*e = Q->base[Q->rear];
 
	return OK;
}

5、例5

（1）问题描述：假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点，设计相应的置空队列、判断队列是否为空、入队和出队等算法。

（2）代码：

typedef int QElemType;  //以整型为例
typedef struct QNode_p   //只设队尾指针的循环链表队列
{
	QElemType data;
	struct QNode_p* next;
}QNode_p, *Queue_pPtr;
 
typedef struct LinkQueue_p
{
	Queue_pPtr rear;
}LinkQueue_p;
 
enum Status
{
	OVERFLOW,
	ERROR,
	OK
};
 
Status InitQueue_p(LinkQueue_p *Q)  //初始化
{
	Q->rear = (QNode_p*)malloc(sizeof(QNode_p));
	Q->rear->next = Q->rear;
	return OK;
}
 
Status ClearQueue_p(LinkQueue_p *Q)  //置空队列
{
	Q->rear = Q->rear->next;    //将尾指针指向头结点
	while (Q->rear != Q->rear->next)
	{
		QNode_p* p = Q->rear->next;
		Q->rear->next = p->next;
		free(p);
	}
	return OK;
}
 
Status EnQueue_p(LinkQueue_p *Q, QElemType e)  //入队
{
	QNode_p* p = (QNode_p*)malloc(sizeof(QNode_p));
	p->data = e;
	p->next = Q->rear->next;
	Q->rear->next = p;
	Q->rear = p;
	return OK;
}
 
Status DeQueue_p(LinkQueue_p *Q, QElemType *e)  //出队
{
	if (Q->rear->next == Q->rear->next->next)
		return ERROR;
	QNode_p* p = Q->rear->next->next;
	*e = p->data;
	if (p == Q->rear)    //当队列中仅剩一个结点（除头结点外）
	{
		Q->rear = Q->rear->next;
		Q->rear->next = p->next;
	}
	else
		Q->rear->next->next = p->next;
	free(p);
	return OK;
}
 
int IsEmptyQueue_p(LinkQueue_p Q)  //判断队列是否为空
{
	if (Q.rear->next == Q.rear->next->next)
		return 1;
	else
		return 0;
}

6、例6

（1）问题描述：假设表达式中允许包含两种括号——圆括号和方括号，其嵌套顺序随意，需要检验表达式的括号是否正确匹配，表达式以“#”结束。

（2）代码：

#define MAXSIZE 100
typedef char SElemType;
typedef struct SqStack
{
	SElemType* base; //栈底指针
	SElemType* top;  //栈顶指针
	int stacksize;   //栈可用的最大容量
}SqStack;
 
enum Status
{
	OVERFLOW,
	ERROR,
	OK
};
 
bool Matching()
{
	SqStack S;
	InitStack(&S);   //初始化空栈
	int flag = 1;   //标记匹配结果以控制循环及返回结果
	char ch = getchar();  //读入第一个字符
	while (ch != '#' && flag)
	{
		switch (ch)
		{
		case '[':
		case '(':
			Push(&S, ch);    //左括号入栈
			break;
		case ')':     //若是“)”，则根据当前栈顶元素的值分情况考虑
			if (!StackEmpty(S) && GetTop(S) == '(')  //栈非空且栈顶为“(”，正确匹配
			{
				SElemType x;
				Pop(&S, &x);
			}
			else    //否则错误匹配
			{
				flag = 0;
			}
			break;
		case ']':     //若是“]”，则根据当前栈顶元素的值分情况考虑
			if (!StackEmpty(S) && GetTop(S) == '[')  //栈非空且栈顶为“[”，正确匹配
			{
				SElemType x;
				Pop(&S, &x);
			}
			else    //否则错误匹配
			{
				flag = 0;
			}
			break;
		}
		ch = getchar();   //继续读入下一个字符
	}
	if (StackEmpty(S) && flag)
		return true;   //匹配成功
	else
		return false;  //匹配失败
}