堆棧是計(jì)算機(jī)程序中非常重要的一部分，主要用來(lái)參數(shù)的調(diào)用，局部變量的存儲(chǔ)等，在C語(yǔ)言中的函數(shù)調(diào)用過程中通過不同函數(shù)的堆�？臻g可以非常方便的找到傳遞進(jìn)來(lái)的參數(shù)以及退出時(shí)應(yīng)該返回的地址。具體的參看“函數(shù)調(diào)用分析 ”，這篇文章中通過實(shí)例分析討論了函數(shù)調(diào)用過程中堆棧的變化過程。
實(shí)質(zhì)上棧的運(yùn)用并不是只能在函數(shù)調(diào)用中，棧作為一種數(shù)據(jù)結(jié)構(gòu)，自然有其特殊的意義，棧的最大特點(diǎn)是"先入后出，后入先出"，這個(gè)特點(diǎn)可以用來(lái)結(jié)局很多的問題。C語(yǔ)言中的函數(shù)調(diào)用算是其中的最主要的用法之一，也就不再分析和討論。同樣遞歸，嵌套調(diào)用等都屬于函數(shù)調(diào)用的子類也不再描述。在其他方面經(jīng)典的運(yùn)用是解決迷宮問題，不同進(jìn)制數(shù)值之間的轉(zhuǎn)換，長(zhǎng)字符串的分解以及算術(shù)表達(dá)式的求值等。下面我主要采用棧實(shí)現(xiàn)經(jīng)典的迷宮問題。
迷宮問題
迷宮問題是經(jīng)典的一類問題，如何從給出的入口找到對(duì)應(yīng)的出口，實(shí)現(xiàn)的方法和馬踏棋盤問題相似也是通過找到周圍8個(gè)方向坐標(biāo)的關(guān)系，然后依據(jù)深度優(yōu)先搜索方法和一定的條件找到下一步對(duì)應(yīng)的出路。由于迷宮問題需要存儲(chǔ)具體的完成路勁，這與前面的問題存在一定的差別。采用棧能夠很好的解決這個(gè)問題，其中棧結(jié)構(gòu)用來(lái)存儲(chǔ)具體的坐標(biāo)和方向。這樣根據(jù)棧就能保證以后每一次都能快速的找到出路。
實(shí)現(xiàn)的基本步驟如下：
1、為了避免邊界檢測(cè)問題，在迷宮的外圍添加一層圍墻，比如原來(lái)的迷宮為m*n,則添加圍墻以后的矩陣為(m+2)*(n+2)。其中為1表示不能走通，0時(shí)表示可以走通。這樣maze[1][1]表示迷宮的入口，而maze[m][n]表示迷宮的出口。
2、創(chuàng)建一個(gè)堆�？臻g，可以采用靜態(tài)數(shù)組的方式，但由于不能準(zhǔn)確的估計(jì)數(shù)組空間大小，可以采用動(dòng)態(tài)創(chuàng)建的方式。并將入口坐標(biāo)值壓入到棧中。定義一個(gè)與迷宮大小相同的矩陣mark，用來(lái)統(tǒng)計(jì)當(dāng)前坐標(biāo)是否已經(jīng)到達(dá)過，當(dāng)沒有到達(dá)坐標(biāo)（i,j）時(shí)，則有mark[i][j] = 0,如果之前到達(dá)過，則有mark[i][j] = 1.這樣主要是為了避免形成內(nèi)部死循環(huán)，同時(shí)說明此路不能走通。
3、檢測(cè)�？臻g是否為空，如果為空則停止，如果不為空，則彈出棧頂?shù)脑?
4、采用循環(huán)的方式，依據(jù)元素的方向確定下一個(gè)坐標(biāo)，具體的確定方法依據(jù)之前的移動(dòng)關(guān)系找到，判斷該位置是否為0（maze[nextrow][nextcol] == 0）以及之前是否到達(dá)該位置(mark[nextrow][nextcol] == 1)。如果滿足條件，則將mark[nextrow][newcol]設(shè)置為1，并將當(dāng)前位置以及具體的方向值壓入棧中，將當(dāng)前坐標(biāo)設(shè)置為之前確定的下一個(gè)坐標(biāo)，設(shè)置方向?yàn)?。然后重新進(jìn)行步驟4。如果8個(gè)方向全部不能找到合適的下一個(gè)坐標(biāo)，說明此路走不通。重新進(jìn)行步驟3，探索新的路勁。探索成功的條件是(nextrow == EXIT_ROW&&nextcol == EXIT_COL)。
基本的實(shí)現(xiàn)流程圖如下所示：
代碼實(shí)現(xiàn)如下：
/*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;
}
測(cè)試結(jié)果：
在迷宮問題中，棧主要實(shí)現(xiàn)了對(duì)滿足條件坐標(biāo)以及方向值(0-7,分別表示一個(gè)具體的方向)的動(dòng)態(tài)保存能夠保證路勁的一致性，也就是先入后出的特性。