实质上栈的运用并不是只能在函数调用中，栈作为一种数据结构，自然有其特殊的意义，栈的最大特点是"先入后出，后入先出"，这个特点可以用来结局很多的问题。C语言中的函数调用算是其中的最主要的用法之一，也就不再分析和讨论。同样递归，嵌套调用等都属于函数调用的子类也不再描述。在其他方面经典的运用是解决迷宫问题，不同进制数值之间的转换，长字符串的分解以及算术表达式的求值等。下面我主要采用栈实现经典的迷宫问题。

迷宫问题

迷宫问题是经典的一类问题，如何从给出的入口找到对应的出口，实现的方法和马踏棋盘问题相似也是通过找到周围8个方向坐标的关系，然后依据深度优先搜索方法和一定的条件找到下一步对应的出路。由于迷宫问题需要存储具体的完成路劲，这与前面的问题存在一定的差别。采用栈能够很好的解决这个问题，其中栈结构用来存储具体的坐标和方向。这样根据栈就能保证以后每一次都能快速的找到出路。

实现的基本步骤如下：

1、为了避免边界检测问题，在迷宫的外围添加一层围墙，比如原来的迷宫为m*n,则添加围墙以后的矩阵为(m+2)*(n+2)。其中为1表示不能走通，0时表示可以走通。这样maze[1][1]表示迷宫的入口，而maze[m][n]表示迷宫的出口。

2、创建一个堆栈空间，可以采用静态数组的方式，但由于不能准确的估计数组空间大小，可以采用动态创建的方式。并将入口坐标值压入到栈中。定义一个与迷宫大小相同的矩阵mark，用来统计当前坐标是否已经到达过，当没有到达坐标（i,j）时，则有mark[i][j] = 0,如果之前到达过，则有mark[i][j] = 1.这样主要是为了避免形成内部死循环，同时说明此路不能走通。

3、检测栈空间是否为空，如果为空则停止，如果不为空，则弹出栈顶的元素.

4、采用循环的方式，依据元素的方向确定下一个坐标，具体的确定方法依据之前的移动关系找到，判断该位置是否为0（maze[nextrow][nextcol] == 0）以及之前是否到达该位置(mark[nextrow][nextcol] == 1)。如果满足条件，则将mark[nextrow][newcol]设置为1，并将当前位置以及具体的方向值压入栈中，将当前坐标设置为之前确定的下一个坐标，设置方向为0。然后重新进行步骤4。如果8个方向全部不能找到合适的下一个坐标，说明此路走不通。重新进行步骤3，探索新的路劲。探索成功的条件是(nextrow == EXIT_ROW&&nextcol == EXIT_COL)。

基本的实现流程图如下所示：

代码实现如下：

/*maze_problem.h*/

#ifndef MAZE_PROBLEM_H_H_

#define MAZE_PROBLEM_H_H_

typedef struct

{

int vert;

int horiz;

}offsets;

typedef struct {

int row;

int col;

int dir;

}element;

typedef struct {

int row;

int col;

}coordinate;

#endif

/*maze_problem.c*/

#include "maze_problem.h"

#include<stdio.h>

#include<stdlib.h>

offsets move[8];

/*the stack save the path, and used */

element * stack;

int top = -1;

void initial_move(void)

{

/*horiz means cols*/

move[0].horiz = 0;

/*vert means rows*/

move[0].vert = -1;

move[1].horiz = 1;

move[1].vert = -1;

move[2].horiz = 1;

move[2].vert = 0;

move[3].horiz = 1;

move[3].vert = 1;

move[4].horiz = 0;

move[4].vert = 1;

move[5].horiz = -1;

move[5].vert = 1;

move[6].horiz = -1;

move[6].vert = 0;

move[7].horiz = -1;

move[7].vert = -1;

}

#define MAZE_ROWS 12

#define MAZE_COLS 15

#define NEW_MAZE_ROWS (MAZE_ROWS + 2)

#define NEW_MAZE_COLS (MAZE_COLS + 2)

#define EXIT_COL 15

#define EXIT_ROW 12

int maze[NEW_MAZE_ROWS][NEW_MAZE_COLS]

= {

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1,

1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1,

1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,

1,1,1,0,1,1,1,1,1,1,1,0,1,1,0,0,1,

1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,

1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1,

1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1,

1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,

1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,

1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1,

1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1,

1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

};

/*used to store the used place*/

int mark[NEW_MAZE_ROWS][NEW_MAZE_COLS];

void mark_init()

{

int i = 0,j = 0;

for(i = 0; i < NEW_MAZE_ROWS ; ++ i)

for(j = 0; j < NEW_MAZE_COLS ; ++ j)

mark[i][j] = 0;

}

int mark_stack_size(int maze[NEW_MAZE_ROWS][NEW_MAZE_COLS])

{

int i = 0,j = 0;

int size = 0;

for(i = 0; i < NEW_MAZE_ROWS; ++ i)

for (j = 0; j < NEW_MAZE_COLS ; ++ j)

{

if(!maze[i][j])

size ++;

}

return size;

}

coordinate nextposition(element a,int dir)

{

coordinate b;

b.col = a.col + move[dir].horiz;

b.row = a.row + move[dir].vert;

return b;

}

int maze_out()

{

element temp;

coordinate nextp;

/*Test the stack is not empty*/

while(top >= 0)

{

/*pop a element*/

temp = *(stack+top);

top --;

/*find on eight directions*/

while(temp.dir < 8)

{

/*get the possible next positions*/

nextp = nextposition(temp,temp.dir);

/*next direction*/

temp.dir ++;

/*success conditions*/

if(nextp.row == EXIT_ROW &&

nextp.col == EXIT_COL)

{

/*save current position*/

stack[++top] = temp;

/*save the exit pointion*/

stack[++top].row = EXIT_ROW;

stack[top].col = EXIT_COL;

stack[top].dir = 0;

/*exit*/

return 1;

}

/*the new position is ok and does not wake*/

if(maze[nextp.row][nextp.col] ==0 &&

mark[nextp.row][nextp.col] == 0)

{

/*mark means that this way has been waked*/

mark[nextp.row][nextp.col] = 1;

/*

*push a element in stack

*save current position and direction

*if this way is failed, used to this position to start new way.

*/

stack[++top] = temp;

/*go to the new position as current position*/

temp.row = nextp.row;

temp.col = nextp.col;

temp.dir = 0;

}

}

}

/*failed*/

return 0;

}

int main()

{

int i = 0;

/*inital the mark array*/

mark_init();

initial_move();

/*create stack*/

stack = (element*)malloc(mark_stack_size(maze)*sizeof(element));

/*if failed*/

if(stack == NULL)

return 0;

/*push a element in stack*/

top ++;

(stack+top)->col = 1;

(stack+top)->row = 1;

(stack+top)->dir = 0;

if(maze_out())

{

while(i <= top)

{

printf("(%d,%d,%d)\n",stack[i].row,stack[i].col,stack[i].dir);

i ++;

}

// printf("(%d,%d)\n",EXIT_ROW,EXIT_COL);

}

/*free the memory*/

free(stack);

/*point to the NULL*/

stack = NULL;

return 1;

}

测试结果：

在迷宫问题中，栈主要实现了对满足条件坐标以及方向值(0-7,分别表示一个具体的方向)的动态保存能够保证路劲的一致性，也就是先入后出的特性。