本文共 7716 字，大约阅读时间需要 25 分钟。

栈

栈（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{[]()}";

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

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");		}	}

结果：

逆波兰表达式

逆波兰表达式又叫做后缀表达式

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

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表示路，如下图：

我们按照左上右下的步骤开始走，也就是先判断左边，是路就走，不是路的话就开始判断上面，是路就走······以此类推。每走一步，都要讲现在的点（坐标）进行压栈，如果走到死路，就要开始一步一步出栈，当出到某一位置还有别的路可以走时，继续压栈，直到最终结果

#define _CRE_SECURE_NO_WARNINGS 1		#include 
   
    	#include 
    
     	#include 
     
      	#include 
      
       		#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;	}
      
     
    
   

结果：

多通路迷宫（不带环）

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

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

结果：

多通路迷宫（带环）

如果再用上面的堵路法，是不行的，因为只有一个出口，却有不同的路，堵路法只能找到其中一条路

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

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

简单通俗易懂的说就可以把某一个问题理解为树，这个树有很多分支，每一个不同的分支都有一个不同的解，如果某一个节点肯定不是问题的解，就要回溯到该节点的上一个节点处

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;	}