栈的实现与应用

栈

栈(stack)是限定尽在表尾进行插入或删除操作的线性表。与线性表类似，栈也有两种存储表示方式。

下面是顺序栈的实现。

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
//定义顺序栈
typedef struct 
{
    ElemType data[MaxSize];
    //栈顶指针
    int top; 
}SqStack;

//初始化栈
void InitStack(SqStack *&s)
{
    s=(SqStack *)malloc(sizeof(SqStack));
    s->top=-1;
} 

//销毁栈
void DestroyStack(SqStack *s)
{
    free(s);
} 

//判断栈空
bool StackEmpty(SqStack *s)
{
    return (s->top==-1);
} 

//进栈
bool Push(SqStack *&s,ElemType e)
{
    //栈满的时候
    if(s->top==MaxSize-1)
        return false;
    s->data[++s->top]=e;
    return true; 
} 

//出栈
bool Pop(SqStack *&s,ElemType &e)
{
    //栈空的时候
    if(s->top==-1)
        return false;
     e=s->data[s->top--];
     return true;
} 

//取栈顶元素
bool GetTop(SqStack *&s,ElemType &e)
{
    //栈空的时候
    if(s->top==-1)
        return false;
     e=s->data[s->top];
     return true;
} 

使用栈我们可以有很多应用。

下面将演示使用栈进行数制转换。

十进制数N和其他d进制数的转换时计算机实现计算的基本问题，下面的简单算法基于下列原理：

N=(N div d)×d+N mod d(其中：div为整除运算，mod为求余运算)

下面是该算法的实现

void conversion()
{
    //构造空栈 
    SqStack *s;
    InitStack(s);
    //获取任意一个非负十进制整数
    unsigned int n;
    scanf("%d",&n); 
    //算法核心
    while(n)
    {
        Push(s,n%8);
        n=n/8;
    } 
    while(!StackEmpty(s))
    {
        ElemType e;
        Pop(s,e);
        printf("%d",e);
    }
}

下面将演示使用栈求解迷宫问题

计算机求解迷宫问题的时候通常用的是“穷举求解”的方法，即从入口出发，顺着某一方向向前搜索，若能走通，则继续往前走；否则沿原路退回，换一个方向在继续搜索，直到所有可能的通路都搜索到为止。

显然，我们需要用到一个后进先出的数据结构来保存从入口到当前为止的路径，所有应用“栈”来解决是自然而然的事情。

算法的基本思想：

若当前位置”可通“，则纳入”当前路径“，并继续朝”下一个位置“搜索，如此重复直到到达出口。

若当前为止”不可通“，则应退回“前一通道块”，然后朝着其他方向继续探索，若该通道块的四周均“不可通”，则应从“当前路径”上删除该通道块。

下面是算法的实现。（利用一个二维数组代表迷宫，1代表墙，0代表通道）

#include <stdio.h>
#define M 4               //行数 
#define N 4               //列数 
#define MaxSize 100
//maze表示一个迷宫，在其四周加上均为1的墙 
int maze[M+2][N+2]=
{
    {1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1},
    {1,0,0,0,1,1},{1,1,0,0,0,1},{1,1,1,1,1,1}
};

//定义栈和存放最短路径的数组  
struct
{
    int x,y;   //横纵坐标 
    int di;    //用来表示该通道块上下左右是否可通 初始化为-1 
}Stack[MaxSize],Path[MaxSize];
int top=-1;             //栈顶指针 
int count=1;            //路径长度计数 
int minlen=MaxSize;     //最短路径长度

//迷宫求解  参数为迷宫入口跟出口的位置 
void GetPath(int xi,int yi,int xe,int ye) 
{
    int i,j,di,find,k;
    top++;
    //入口通道块进栈 
    Stack[top].x=xi;
    Stack[top].y=yi;
    Stack[top].di=-1;
    maze[xi][yi]=-1; 
    //栈不为空时循环
    while(top>-1)
    {
        i=Stack[top].x;
        j=Stack[top].y;
        di=Stack[top].di;
        //找到了出口
        if(i==xe&&j==ye)
        {
            //更新最短路径
            if(top+1<minlen)
            {
                for(k=0;k<=top;k++)
                    Path[k]=Stack[k];
                minlen=top+1;
            } 
            //让该位置标为其他路径可走节点 
            maze[Stack[top].x][Stack[top].y]=0;
            top--;
            i=Stack[top].x;
            i=Stack[top].y;
            di=Stack[top].di;
        }
        find=0;
        //找下一个可走方块 
        while(di<4&&find==0)
        {
            di++;
            //遍历4个方向 
            switch(di)
            {
            case 0:i=Stack[top].x-1;j=Stack[top].y;break;
            case 1:i=Stack[top].x;j=Stack[top].y+1;break;
            case 2:i=Stack[top].x+1;j=Stack[top].y;break;
            case 3:i=Stack[top].x;j=Stack[top].y-1;break;
            }
            if(maze[i][j]==0) find=1;
        }
        //找到了下一个可走方块 
        if(find==1)
        {
            Stack[top].di=di;
            top++;
            Stack[top].x=i;
            Stack[top].y=j;
            Stack[top].di=-1;
            //避免重复走到该方块 
            maze[i][j]=-1; 
        }
        //没有路可走，则退回 
        else
        {
            //让该位置标为其他路径的可走节点 
            maze[Stack[top].x][Stack[top].y]=0;
            top--; 
        }
    } 
    //输出最短路径
    printf("其中一条最短路径如下：
");
    for(k=0;k<minlen;k++)
    {
        printf("(%d %d)  ",Path[k].x,Path[k].y);
    } 
    printf("
"); 
}