栈的操作及其应用

青旅半醒 2022-05-10 02:08 194阅读 0赞

### 文章目录 ###

*   *  栈
     *   *   *  结构体定义
             *  初始化
             *  销毁
             *  压栈
             *  出栈
             *  栈顶元素
             *  栈的大小
             *  栈是否为空
     *  判断括号匹配
     *  逆波兰表达式
     *  迷宫
     *   *   *  简单迷宫
             *  多通路迷宫（不带环）
             *  多通路迷宫（带环）

## 栈 ##

栈（stack）又名堆栈，仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。**栈是一种后入先出的操作（LIFO）**

#### 结构体定义 ####

#define MAX 100
    	
    	typedef char SDataType;
    	
    	typedef struct Stack
    	{
    		SDataType arr[MAX];
    		int top;
    	}Stack;

#### 初始化 ####

void StackInit(Stack *ps)
    	{
    		assert(ps);
    		ps->top = 0;
    	}

#### 销毁 ####

void StackDestory(Stack *ps)
    	{
    		assert(ps);
    		ps->top = 0;
    	}

#### 压栈 ####

void StackPush(Stack *ps, SDataType data)
    	{
    		assert(ps);
    		assert(ps->top < MAX);
    		ps->arr[ps->top] = data;
    		ps->top++;
    	}

#### 出栈 ####

void StackPop(Stack *ps)
    	{
    		assert(ps);
    		assert(ps->top > 0);
    		ps->top--;
    	}

#### 栈顶元素 ####

SDataType StackTop(Stack *ps)
    	{
    		assert(ps);
    		return ps->arr[ps->top - 1];
    	}

#### 栈的大小 ####

int StackSize(Stack *ps)
    	{
    		assert(ps);
    		return ps->top;
    	}

#### 栈是否为空 ####

int StackEmpty(Stack *ps) //为空返回1，否则返回0
    	{
    		assert(ps);
    		return ps->top == 0 ? 1 : 0;
    	}

## 判断括号匹配 ##

char a[] = "(())abc{[(])}"; // 左右括号次序匹配不正确
    	char b[] = "(()))abc{[]}"; // 右括号多于左括号
    	char c[] = "(()()abc{[]}"; // 左括号多于右括号
    	char d[] = "(())abc{[]()}";

上面四种表示测试用例，其实也代表了四种不同的情况。我们就可以运用栈来判断括号是否匹配，当遇见左括号，进行压栈，遇见右括号，判断是否与栈顶元素相匹配并出栈，以此下去。  
![在这里插入图片描述][70]

void MatchBrackets(const char *str)
    	{
    		assert(str);
    		Stack stack;
    		StackInit(&stack);
    	
    		const char *p = str;
    		while (*p != '\0')
    		{
    			switch (*p)
    			{
    			case '{':
    			case '[':
    			case '(':
    				StackPush(&stack, *p);
    				break;
    			case '}':
    			case ']':
    			case ')':
    				if (StackEmpty(&stack))
    				{
    					printf("右括号多与左括号\n");
    					return;
    				}
    				char c = StackTop(&stack);
    				StackPop(&stack);
    				if (!((c == '{' && *p == '}') 
    					|| (c == '[' && *p == ']') 
    					|| (c == '(' && *p == ')')))
    				{
    					printf("左右括号不匹配\n");
    					return;
    				}
    				break;
    			default:
    				break;
    			}
    			p++;
    		}
    		if (!StackEmpty(&stack))
    		{
    			printf("左括号多于右括号\n");
    		}
    		else
    		{
    			printf("左右括号匹配\n");
    		}
    	}

结果：  
![在这里插入图片描述][70 1]

## 逆波兰表达式 ##

逆波兰表达式又叫做后缀表达式  
例如：1 \* 2 + 3 \* 4 可以表示为：  
1 2 \* 3 4 \* +  
逆波兰表达式就完美的运用到了栈的思想。遇见数字就压栈，遇见操作符，就将栈顶的两个元素进行操作，并出栈，并将运算结果压栈，以此下去，最终栈里只有一个元素  
![在这里插入图片描述][70 2]  
这个问题的思路比较简单，但是如何判断是字符还是数字尼？难道要加一个判断条件，这样显然太麻烦，我们可以运用枚举，里面就两个，操作数和操作符

typedef enum 
    	{
    		NUMBER,
    		OPERATOR
    	}Type;
    	
    	typedef enum
    	{
    		ADD,
    		SUB,
    		MUL,
    		DIV,
    		NOUSED
    	} OP;
    	
    	typedef struct
    	{
    		Type type;
    		int number;
    		OP operator;
    	}Item;
    	
    	Item g_arr[] = 
    	{
    		{
    			NUMBER,
    			1,
    			NOUSED 
    		},
    		{
    			NUMBER,
    			2,
    			NOUSED
    		},
    		{
    			OPERATOR,
    			-1, //因为这是一个操作符，不存在数字，所以就可以随便定义一个
    			MUL
    		},
    		{
    			NUMBER,
    			3,
    			NOUSED
    		},
    		{
    			NUMBER,
    			4,
    			NOUSED
    		},
    		{
    			OPERATOR,
    			-1,
    			MUL
    		},
    		{
    			OPERATOR,
    			-1,
    			ADD
    		},
    	};
    	
    	void RPN(Item g_arr[], int size)
    	{
    		Stack stack;
    		StackInit(&stack);
    		for (int i = 0; i < size; i++)
    		{
    			if (g_arr[i].type == NUMBER)
    			{
    				StackPush(&stack, g_arr[i].number);
    			}
    			else
    			{
    				int result = 0;
    				int n1 = 0;
    				int n2 = 0;
    				n1 = StackTop(&stack);
    				StackPop(&stack);
    				n2 = StackTop(&stack);
    				StackPop(&stack);
    				switch (g_arr[i].operator)
    				{
    				case ADD:
    					result = n1 + n2;
    					break;
    				case SUB:
    					result = n2 - n1;
    					break;
    				case MUL:
    					result = n1 * n2;
    					break;
    				case DIV:
    					result = n2 / n1;
    					break;
    				default :
    					break;
    				}
    				StackPush(&stack, result);
    			}
    		}
    		assert(StackSize(&stack) == 1);
    		printf("%d\n", StackTop(&stack));
    	}
    	
    	int main()
    	{
    		int size = sizeof(g_arr) / sizeof(g_arr[0]);
    		RPN(g_arr, size);
    		system("pause");
    		return 0;
    	}

## 迷宫 ##

#### 简单迷宫 ####

简单迷宫就是指只有一条出路的迷宫，0表示墙，1表示路，如下图：  
![在这里插入图片描述][70 3]  
我们按照左上右下的步骤开始走，也就是先判断左边，是路就走，不是路的话就开始判断上面，是路就走······以此类推。每走一步，都要讲现在的点（坐标）进行压栈，如果走到死路，就要开始一步一步出栈，当出到某一位置还有别的路可以走时，继续压栈，直到最终结果

#define _CRE_SECURE_NO_WARNINGS 1
    	
    	#include <stdlib.h>
    	#include <assert.h>
    	#include <stdio.h>
    	#include <Windows.h>
    	
    	#define ROW (6)
    	#define COL (6)
    	#define MAX (100)
    	
    	int g_arr[ROW][COL] = 
    	{
    		{ 0, 0, 0, 0, 0, 0 },
    		{ 0, 0, 1, 0, 0, 0 },
    		{ 0, 0, 1, 0, 0, 0 },
    		{ 0, 0, 1, 1, 1, 0 },
    		{ 0, 0, 1, 0, 1, 1 },
    		{ 0, 0, 1, 0, 0, 0 }
    	};
    	
    	typedef struct Position
    	{
    		int x;
    		int y;
    	}Position;
    	
    	typedef struct Stack
    	{
    		Position arr[MAX];
    		int top;
    	}Stack;
    	
    	void StackInit(Stack *ps)
    	{
    		assert(ps);
    		ps->top = 0;
    	}
    	
    	void StackPush(Stack *ps, Position pos)
    	{
    		assert(ps);
    		assert(ps->top < MAX);
    		ps->arr[ps->top] = pos;
    		ps->top++;
    	}
    	
    	void StackPop(Stack *ps)
    	{
    		assert(ps);
    		assert(ps->top > 0);
    		ps->top--;
    	}
    	
    	Position StackTop(Stack *ps)
    	{
    		assert(ps);
    		return ps->arr[ps->top - 1];
    	}
    	
    	int StackEmpty(Stack *ps)
    	{
    		assert(ps);
    		if (ps->top == 0)
    		{
    			return 1;
    		}
    		return 0;
    	}
    	
    	//打印
    	void printMaze(int arr[ROW][COL])
    	{
    		for (int i = 0; i < ROW; i++)
    		{
    			for (int j = 0; j < COL; j++)
    			{
    				//1表示路
    				if (arr[i][j] == 1)
    				{
    					printf("  ");
    				}
    				//0表示墙
    				else if (arr[i][j] == 0)
    				{
    					printf("█");
    				}
    				//2表示已经走过
    				else if (arr[i][j] == 2)
    				{
    					printf("⊙");
    				}
    			}
    			printf("\n");
    		}
    	}
    	//判断栈是否为空
    	int IsExit(Position pos)
    	{
    		if (pos.y == COL - 1)
    		{
    			return 1;
    		}
    		return 0;
    	}
    	//判断是否可以走
    	int CanPass(Position pos)
    	{
    		if (pos.x < 0 || pos.x >= ROW)
    		{
    			return 0;
    		}
    		if (pos.y < 0 || pos.y >= ROW)
    		{
    			return 0;
    		}
    		if (g_arr[pos.x][pos.y] == 1)
    		{
    			return 1;
    		}
    		else
    		{
    			return 0;
    		}
    	}
    	
    	void test()
    	{
    		Stack stack;
    		StackInit(&stack);
    		Position entry = { 5, 2 }; //表示入口
    		Position pos = entry;
    		Position nextPos;
    	
    		while (1)
    		{
    			g_arr[pos.x][pos.y] = 2;
    	
    			system("cls");
    			printMaze(g_arr);
    			Sleep(300);
    			StackPush(&stack, pos); //每走一步进行压栈
    			if (IsExit(pos))
    			{
    				printf("找到出口\n");
    				return;
    			}
    			//按照左、上、右、下步骤走
    			//左
    			nextPos = pos;
    			nextPos.y -= 1;
    			if (CanPass(nextPos))
    			{
    				pos = nextPos;
    				continue;
    			}
    			//上
    			nextPos = pos;
    			nextPos.x -= 1;
    			if (CanPass(nextPos))
    			{
    				pos = nextPos;
    				continue;
    			}
    			//右
    			nextPos = pos;
    			nextPos.y += 1;
    			if (CanPass(nextPos)) {
    				pos = nextPos;
    				continue;
    			}
    			//下
    			nextPos = pos;
    			nextPos.x += 1;
    			if (CanPass(nextPos)) {
    				pos = nextPos;
    				continue;
    			}
    			//如果都不能走，就要出栈
    			pos = StackTop(&stack);
    			StackPop(&stack);
    			g_arr[pos.x][pos.y] = 2;
    			if (StackEmpty(&stack))
    			{
    				printf("结束\n");
    				return;
    			}
    			//这个pos就是上一个不能走的位置的前一个位置
    			pos = StackTop(&stack);
    			StackPop(&stack);
    		}
    	}
    	
    	int main()
    	{
    		test();
    		system("pause");
    		return;
    	}

结果：  
![在这里插入图片描述][70 4]

#### 多通路迷宫（不带环） ####

![在这里插入图片描述][70 5]  
如果再按照上面的那种方法走，就会发现只能找到一个出口就停止了，二找不到两个出口。怎么找另一条路？当我们找到第一条路的出口时就可以将这个出口给堵住，就能够找到第二条路了，这种方法也叫做堵路法。  
代码只有一个地方发生改变：

if (IsExit(pos))
    			{
    				printf("找到出口\n");
    				g_arr[pos.x][pos.y] = 0; // 只需将出口变成墙就可以了
    				//return;
    			}

结果：  
![在这里插入图片描述][70 6]

#### 多通路迷宫（带环） ####

![在这里插入图片描述][70 7]  
如果再用上面的堵路法，是不行的，因为只有一个出口，却有不同的路，堵路法只能找到其中一条路

在开始分析复杂迷宫之前，我们先理解一个思想：**回溯**。

> 回溯法是按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法

简单通俗易懂的说就可以把某一个问题理解为树，这个树有很多分支，每一个不同的分支都有一个不同的解，如果某一个节点肯定不是问题的解，就要回溯到该节点的上一个节点处  
![在这里插入图片描述][70 8]

Stack pathStack;
    	Stack shortPathStack; //保存最短路径
    	
    	void CopyStack(Stack *pdest, Stack *psrc)
    	{
    		memcpy(pdest->arr, psrc->arr, psrc->top * sizeof(Position));
    		pdest->top = psrc->top;
    	}
    	
    	void test(Position pos)
    	{
    		g_arr[pos.x][pos.y] = 2;
    		Position nextPos;
    		StackPush(&pathStack, pos);
    		//system("cls");
    		printMaze(g_arr);
    		Sleep(300);
    		if (IsExit(pos))
    		{
    			g_arr[pos.x][pos.y] = 1;
    			printf("找到出口\n");
    			StackPop(&pathStack);
    			for (int i = 0; i < pathStack.top; i++)
    			{
    				printf("%d %d\n", pathStack.arr[i].x, pathStack.arr[i].y);
    			}
    			if (shortPathStack.top == 0 || pathStack.top < shortPathStack.top)
    			{
    				CopyStack(&shortPathStack, &pathStack);
    			}
    			return;
    		}
    		nextPos = pos;
    		nextPos.y -= 1;
    		if (CanPass(nextPos))
    		{
    			test(nextPos);
    		}
    		//上
    		nextPos = pos;
    		nextPos.x -= 1;
    		if (CanPass(nextPos))
    		{
    			test(nextPos);
    		}
    		//右
    		nextPos = pos;
    		nextPos.y += 1;
    		if (CanPass(nextPos)) {
    			test(nextPos);
    		}
    		//下
    		nextPos = pos;
    		nextPos.x += 1;
    		if (CanPass(nextPos)) {
    			test(nextPos);
    		}
    		g_arr[pos.x][pos.y] = 1;
    		StackPop(&pathStack);
    	}
    	
    	int main()
    	{
    		StackInit(&pathStack);
    		StackInit(&shortPathStack);
    		Position entry = { 5, 2 };
    		test(entry);
    		system("pause");
    		return;
    	}

[70]: /images/20220510/8b994231d5a94891a1fe3aa4fb27b79f.png
[70 1]: /images/20220510/98b8092e7aeb4cc09dc22cd18eb87bc0.png
[70 2]: /images/20220510/89a83f901c55455eb1e2a9bf1aa6eeab.png
[70 3]: /images/20220510/f1fb8709b7494fdebab25a8f617e1a3e.png
[70 4]: /images/20220510/686f78fe7fab4c70a90e4fa4de3acd3d.png
[70 5]: /images/20220510/ba9d7b717bd747d49f8a5f9363b4449c.png
[70 6]: /images/20220510/41699ba2722842fe8c64128f0491348f.png
[70 7]: /images/20220510/38b0aafed8d84c28951f525e8ae26a54.png
[70 8]: /images/20220510/09e8c276a1764c7f9abe701e5128badf.png