堆栈，也可直接称栈，是一种特殊的串行形式的数据结构，它的特殊之处在于只能允许在链结串行或阵列的一端进行加入资料和输出资料的运算。另外堆栈也可以用一维阵列或连结串行的形式来完成。
1 #define STACK_INIT_SIZE 100 2 #define STACKINCREMENT 10 3 4 typedef struct 5 { int* top; 6 int* base; 7 int stacksize; 8 }SqStack; 9 10 int InitStack(SqStack &S) 11 { 12 S.base = (int*)malloc(sizeof(int)*STACK_INIT_SIZE); 13 if(!S.base)exit(1);//分配内存失败 14 S.stacksize = STACK_INIT_SIZE; 15 S.top = S.base; 16 return 1; 17 } 18 //栈顶插入 19 int Push(SqStack &S,int e) 20 { 21 if(S.top - S.base >= S.stacksize) 22 { 23 S.base = (int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); 24 if(!S.base)exit(1);//分配内存失败 25 S.top = S.base+S.stacksize; 26 S.stacksize += STACKINCREMENT； 27 } 28 *S.top++ = e; 29 return 1; 30 } 31 int Pop(SqStack &S,int &e) 32 { 33 if(S.top == S.base) 34 return 0; 35 e = *--S.top; 36 return 1; 37 }
迷宫求解问题实现：
1 // mazepath.cpp : Defines the entry point for the console application. 2 // 3 4 #include "stdafx.h" 5 #include "stdio.h" 6 #include "stack.h" 7 #include "malloc.h" 8 9 #define RANGE 10 //设置数组的最大长度 10 11 12 typedef int DirectType; 13 14 typedef struct { 15 int r,c; //迷宫中r行c列的位置 16 }PosType; 17 18 typedef struct { 19 int row,col; 20 char arr[RANGE][RANGE];//各位置取值' ','#','@'或'*' 其中#表示墙壁 @表示走不通的节点 *表示走过的节点 21 }MazeType; 22 23 24 typedef struct { 25 int step; //当前位置在路径上的“序号” 26 PosType seat; //当前的坐标位置 27 DirectType di; //往下一坐标位置的方向 28 }ElemType; //栈的元素类型 29 30 31 typedef struct NodeType { 32 ElemType data; 33 struct NodeType *next; 34 }NodeType,*LinkType; //结点类型，指针类型 35 36 typedef struct { 37 LinkType top; 38 int size; 39 }Stack; //栈类型 40 41 42 void Initialization(){ 43 printf("CreatMaze-cn"); 44 printf("MazePsth-cn"); 45 printf("PrintMaze-cn"); 46 } 47 48 void MakeNode(LinkType &p,ElemType e){ 49 p=(LinkType)malloc(sizeof(NodeType)); 50 p->data.step=e.step; 51 p->data.seat.r=e.seat.r; 52 p->data.seat.c=e.seat.c; 53 p->data.di=e.di; 54 } 55 //标记走过的节点 56 void FootPrint(MazeType &Maze,PosType curpos){ 57 Maze.arr[curpos.r][curpos.c]='*'; 58 } 59 60 int Pass(MazeType &Maze,PosType curpos){ 61 if(Maze.arr[curpos.r][curpos.c]=='#'||Maze.arr[curpos.r][curpos.c]=='@') 62 return 0; 63 else return 1; 64 } 65 66 67 68 void CreateMaze(MazeType &Maze){ 69 int i,j; 70 printf("产生迷宫：输入迷宫的大小n"); 71 printf("行：n"); 72 scanf("%d",&Maze.row); 73 printf("列：n"); 74 scanf("%d",&Maze.col); 75 //给迷宫四周加障碍 76 for(i=0;i<=Maze.row+1;i++) 77 for(j=0;j<=Maze.col+1;j++) 78 if(i==0||i==Maze.row+1)Maze.arr[i][j]='#'; 79 else if(j==0||j==Maze.col+1)Maze.arr[i][j]='#'; 80 else Maze.arr[i][j]=' '; 81 //接收障碍位置 82 printf("如果设置障碍结束，请输入“q”,否则输入障碍所在行n"); 83 scanf("%d",&i); 84 while(i!='q'){ 85 printf("输入障碍所在列n"); 86 scanf("%d",&j); 87 Maze.arr[i][j]='#'; 88 printf("如果设置障碍结束，请输入“q”,否则输入障碍所在行n"); 89 scanf("%d",&i); 90 } 91 } 92 //标记四个方向都走不通的节点 93 void MakePrint(MazeType &Maze,PosType curpos){ 94 Maze.arr[curpos.r][curpos.c]='@'; 95 } 96 97 98 void NextPos(PosType &curpos,DirectType di){ 99 switch(di){ 100 case 1:curpos.c++;break; 101 case 2:curpos.r++;break; 102 case 3:curpos.c--;break; 103 case 4:curpos.r--;break; 104 } 105 } 106 107 108 109 void PrintMaze(MazeType Maze){ 110 int i,j; 111 for(i=1;i<=Maze.row;i++){ 112 for(j=1;j<=Maze.col;j++){ 113 printf("%c",Maze.arr[i][j]); 114 } 115 printf("n"); 116 } 117 118 119 120 int MazePath(MazeType Maze,PosType start,PosType end){ 121 PosType curpos; 122 ElemTpye e; 123 int curstep=1,found=0; 124 InitStack(S); 125 curpos=start; 126 do{ 127 if(Pass(Maze,curpos)){ 128 FootPrint(Maze,curpos); 129 e.step=curstep; 130 e.seat=curpos; 131 e.di=1; 132 Push(S,e); 133 if(curpos==end)found=1; 134 else { 135 curpos=NextPos(curpos,1); 136 curstep++: 137 }//else 138 }//if 139 else 140 if (!StackEmpty(S)){ 141 Pop(S,e); 142 while(e.di==4&&!StackEmpty(S)){ 143 MarkPrint(Maze,e.seat); 144 Pop(S,e); 145 curstep--; 146 }//while 147 if(e.di<4){ 148 e.di++; 149 Push(S,e); 150 curpos=NextPos(e.seat,e.di); 151 }//if 152 }//if 153 }while(!StackEmpty(S)&&!found); 154 return found; 155 }//Mazepath