《数据结构》堆栈（铁路、洗牌、汉诺塔、走迷宫）全解析
目录
一、栈
堆栈简介
堆栈的基本应用
二、数组（顺序表）实现堆栈
使用Java程序实现一个堆栈的基本功能
顺序堆栈的应用（扑克牌洗牌以及发牌）
三、链表实现堆栈
用链表来实现堆栈
使用Java程序实现一个链表的基本功能
四、堆栈的应用
铁路调度问题
汉诺塔问题
当只有一个圆盘时
当有两个圆盘时
当有三个圆盘时
老鼠走迷宫
使用Java语言表示
五、总结
一、栈
堆栈简称为栈，堆栈是一组相同数据类型的集合，所有的操作均在堆栈顶端进行，具有“先进后出”（Last In First Out,LIFO）的特征；堆栈结构在计算机中应用相当广泛，时常被用来解决计算机的问题，例如递归调用、子程序的调用等。在日常生活中的应用也是相当广泛，例如：大楼电梯、货架上的货品等，都类似于堆栈的数据结构原理
自助餐中的餐盘的应用：
堆栈简介
所谓的先进后出的概念，其实就如同自助餐中餐盘由桌面网上一个一个叠放且取用时由上面先拿，这就是典型的堆栈概念的应用
由于堆栈是一种抽象数据类型，它有以下特征：
·只能从堆栈的顶端存储数据
·数据的取舍符合“先进后出”的原则
堆栈压入和弹出操作的过程如图所示：
堆栈的基本应用
堆栈的基本运算有以下五种：
· create：创建一个空堆栈
· push：把数据压入堆栈顶端，并返回新堆栈
· pop：从堆栈顶端弹出数据，并返回新堆栈
· IsEmoty：判断堆栈是否为空堆栈，是返回true，否则返回false
· full：判断堆栈是否已满，是返回true，否则返回false
在Java程序设计中，堆栈包含数组结构和链表结构
二、数组（顺序表）实现堆栈
以数组结构实现堆栈的好处是设计的算法都相当简单，但是，堆栈本身的大小是变动的话，而数组大小只能事先提前规划和声明好，那么数组规划过大又会造成浪费空间，规划太小了又不够用（所以 敲黑板！ 问你堆栈的实现用哪种结构实现简单，那么毋庸置疑就是顺序表了）
使用Java程序实现一个堆栈的基本功能
package Dome1;
import java.util.Scanner;
class StackByArray{//以数组模拟堆栈的类声明
private int[] stack;
private int top;
public StackByArray(int stacksize) {
stack=new int[stacksize];
top=-1;//-1代表无数据
}
public boolean push(int data){//压入堆栈元素
if(top>stack.length){
System.out.println("堆栈已满，无法再压入");
return false;
} else {
stack[++top]=data;
return true;
}
}
public boolean empet(){//判断堆栈是否为空栈
if(top==-1)return true;
else return false;
}
public int pop(){//从栈顶弹出数据
if(empet()){
System.out.println("栈为空，无法弹出");
return -1;//此处-1为代表空栈
}
else{
return stack[top--];
}
}
}
public class Test {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=10;
StackByArray stack=new StackByArray(n);
System.out.println("请按照要压入栈的顺序输入10个数字");
while(n>0){
int val=scanner.nextInt();
if(!stack.push(val)){
System.out.println("压入失败");
break;
}
n--;
}
System.out.println("================");
System.out.println("下面为取出栈帧中的值");
while(!stack.empet()){
System.out.print(stack.pop()+" ");
}
}
}以下为运行结果
顺序堆栈的应用（扑克牌洗牌以及发牌）
我们来使用数组方针扑克牌洗牌及发牌过程，使用随机数来生成扑克牌压入堆栈，放满52张牌后开始发牌，使用堆栈的弹出功能来给四个人发牌
public class Test {
static int top=-1;
public static void push(int[] stack,int MAX,int val){
if(top>=MAX-1){
System.out.println("堆栈已满");
}else {
top++;
stack[top]=val;
}
}
public static int pop(int[] stack){
if(top==-1){
System.out.println("堆栈已空");
return -1;//这边返回-1则为空栈 业务上的东西暂时不处理
}else {
top--;
return stack[top];
}
}
public static void main(String[] args) {
int[] card=new int[52];//扑克52张牌（抛去大小王）
int[] stack=new int[52];//堆栈
int i,j,k=0,test;
String ascVal=null;
int style;
for(i=0;i<52;i++) {
card[i] = i;
}
System.out.println("洗牌中，请稍后");
while(k<30){//洗牌
for ( i = 0; i < 51 ; i++) {
for(j=i+1;j<52;j++){
if(((int)(Math.random()*5))==2){
test=card[i];//洗牌
card[i]=card[j];
card[j]=test;
}
}
}
k++;
}
i=0;
while(i!=52){
push(stack,52,card[i]);
i++;
}
System.out.println("逆时针发牌");
System.out.println("显示各家的牌 \n 东家\t 北家\t 西家\t 南家\t");
System.out.println("======================================");
while(top>=0){
style=stack[top]/13;//因为扑克牌只有1-13 一张牌有四种花色
switch(style){
case 0:
ascVal="♣";
break;
case 1:
ascVal="♦";
break;
case 2:
ascVal="♥";
break;
case 3:
ascVal="♠";
break;
}
System.out.print("["+ascVal+(stack[top]%13+1)+"]");
System.out.print('\t');
if(top%4==0){
System.out.println();
}
top--;
}
}
}
打印结果如下：（因为使用了随机数，所以每次发牌结果都是不一样的）
洗牌思路是自己做的 可以按照自己的思路修改，合理即可
三、链表实现堆栈
用链表来实现堆栈
虽然以数组结构来制作堆栈的好处是制作与设计的算法都相当简单，但因为如果堆栈本身是变动的话，数组大小并无法事先规划声明。这时往往必须考虑使用最大可能性的数组空间，这样会造成内存空间的浪费，而用链表制作堆栈的优点是随时可以动态改变链表的长度，不过缺点是设计时算法较为复杂
使用Java程序实现一个链表的基本功能
package LinkListStack;
import java.util.*;
class Node{
public int val;
public Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
}
class LinkListStack{
public Node front;
public Node rear;
public boolean IsEmpty(){
return front==null;
}
public void insert(int data){//压入栈
Node newStack=new Node(data);
if(IsEmpty()){//如果是空栈
front=newStack;
rear=newStack;
}else {
rear.next=newStack;
rear=newStack;
}
}
public void pop(){
if(IsEmpty()){
System.out.println("栈为空栈");
return ;
}else {
Node cur=front;
while(cur!=rear&&cur.next!=rear){
cur=cur.next;
}
if(cur==front){
front=null;
rear=null;
}else {
cur.next=null;
}
rear=cur;//弹出栈
}
}
public void print_Stack(){
if(IsEmpty()){
System.out.println("当前栈为空栈");
return ;
}
System.out.println(rear.val+" ");
pop();
}
}
public class Test {
public static void mune(){
System.out.println("0->退出");
System.out.println("1->压栈");
System.out.println("2->弹栈");
System.out.println("3->打印并弹出");
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
LinkListStack stack=new LinkListStack();
int input=0;
while(true){
mune();
input=scanner.nextInt();
switch(input){
case 0:return;
case 1:{
System.out.println("请输入要压入栈的值");
int data=scanner.nextInt();
stack.insert(data);
break;
}
case 2:stack.pop();break;
case 3:stack.print_Stack();break;
}
}
}
}四、堆栈的应用
堆栈在计算机领域应用相当广泛，主要特征是限制了数据输入与删除的位置和方法，属于有序表的应用，堆栈的各种应用如下
· 二叉树和森林的遍历
· 计算机中央处理单元的中断处理
· 图形的深度优先查找法
· 某些所谓堆栈计算机
· 当从递归返回
· 算数表达式的转换和求值
· 调用子程序和返回处理
· 编译错误处理
铁路调度问题
有一个火车站，铁路如图所示，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n≤1000），分别按照顺序编号为1，2，3，…，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站C。
根据题意，写出可能的出栈序列有多少种？出栈的序列分别是什么？
可能的出栈序列有14种；
出栈的序列分别是1234；1243；1324；1342；1432；2134；2143；2314；2341；2431；3214；3241；3421；4321。分析：
1.列车4辆全部进站后顺序出站的情况（1种）：4321
2.列车3辆车进站后开始出站（3种）：3421，3241，3214
3.列车2辆车进站后开始出站（5种）：2431，2341，2134，2143，2314
4.列车1辆车进站后开始出站（5种）：1432，1324，1342，1234，1243所以我们可以得到 不可能会出现的出栈顺序有：15234……
汉诺塔问题
汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？（每次只能移动1个盘子，大盘子只能放在小盘子下面）
当只有一个圆盘时
当只有一个圆盘时，我们直接可以将1柱移动到3柱
当有两个圆盘时
当有两个圆盘时，我们操作如下：
1->2 1->3 2->3
当有三个圆盘时
当有三个圆盘时，我们操作如下
1->3 1->2 3->2 1->3 2->1 2->3 1->3
有了以上理解 我们再放到递归中 我们发现 汉诺塔问题非常适合以递归方式与堆栈来解决，因为它满足了两大特征：一是有反复执行的过程，二是有停止的出口，以下是以递归的方式来描述的汉诺塔递归函数
import java.util.Scanner;
public class Test {
public static void main(String[] args) {
int j;
Scanner scanner=new Scanner(System.in);
System.out.println("请输入盘子的数量");
j=scanner.nextInt();
hanoi(j,1,2,3);
}
public static void hanoi(int n,int pos1,int pos2,int pos3){
if(n==1){
System.out.print(pos1+"->"+pos3+" ");
} else {
hanoi(n-1,pos1,pos3,pos2);
System.out.print(pos1+"->"+pos3+" ");
hanoi((n-1),pos2,pos1,pos3);
}
}
}运行结果
老鼠走迷宫
堆栈的应用有一个相当有趣的问题，就是实验心理学中有名的“老鼠走迷宫”问题。老鼠走迷宫问题的陈述是：假设把一只大老鼠放在一个没有盖子的大迷宫盒的入口处，盒中有许多墙使得大部分的路径都被挡住而无法前进。老鼠可以按照尝试错误的方法找到出口。不过，这只老鼠具备走错路时就会退回来并把走过的路记下来，避免下次走重复的路，就这样直到找到出口为止。简单来说，老鼠行进时，必须遵守以下三个原则：
1.一次只能走一格
2.遇到墙无法往前走时，则退回一步找找看是否有其他的路可以走
3.走过的路不会再走第二次
我们之所以对这个问题感兴趣，就是它可以提供一种典型堆栈应用的思考方法，有许多大学曾举办“计算机老鼠走迷宫” 的比赛，就是要设计这种堆栈技巧走迷宫的程序，在编写走迷宫程序之前，我们先来了解如何在计算机中变现一个仿真迷宫的方式，这时可以利用二维数组MAZE[row][col],并符合以下规则：
MAZE [ i ] [ j ] =1 表示[ i ] [ j ]处有墙，无法通过
MAZE [ i ] [ j ] =0 表示[ i ] [ j ]处无墙，可以通过
MAZE[ 1 ] [ 1 ]是入口，MAZE[ m ] [ n ]是出口
假设老鼠从左上角的MAZE [ 1 ] [ 1 ]进入，从右下角的MAZE [ 8 ] [ 10 ]出来，当前老鼠位置以MAZE [ i ] [ j ]表示，那么我们可以将老鼠可能移动的方向表示
使用Java语言表示
package Dome3;
class Node {
int x;
int y;
Node next;
public Node(int x, int y) {
this.x = x;
this.y = y;
this.next = null;
}
}
class TraceRecord{
public Node first;
public Node last;
public Boolean IsEmpty(){
return first==null;
}
public void insert(int x,int y){
Node newNode=new Node(x,y);
if(this.IsEmpty()){
first=newNode;
last=newNode;
} else {
last.next=newNode;
last=newNode;
}
}
public void delete(){
Node newNode;
if(this.IsEmpty()){
System.out.println("队列已空");
return ;
}
newNode=first;
while(newNode.next!=last){
newNode=newNode.next;
}
newNode.next=null;
last=newNode;
}
}
public class Test {
public static int ExitX = 8;
public static int ExitY = 10;
public static int[][] MAZE = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1},
{1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1},
{1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1},
{1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1},
{1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};
public static void main(String[] args) {
int i, j, x, y;
TraceRecord path = new TraceRecord();
x = 1;
y = 1;
System.out.println("迷宫的路径（0标记的部分）");
for (i = 0; i < 10; i++) {
for (j = 0; j < 12; j++) {
System.out.print(MAZE[i][j] + " ");
}
System.out.println();
}
while (x <= ExitX && y <= ExitY) {
MAZE[x][y] = 2;
if (MAZE[x - 1][y] == 0) {
x -= 1;
path.insert(x, y);
} else if (MAZE[x+1][y] == 0) {
x += 1;
path.insert(x, y);
} else if (MAZE[x][y - 1] == 0) {
y -= 1;
path.insert(x, y);
} else if (MAZE[x][y+ 1] == 0) {
y += 1;
path.insert(x, y);
} else {
if(chkExit(x,y,ExitX,ExitY)==1){
break;
} else {
MAZE[x][y]=2;
path.delete();
x=path.last.x;
y=path.last.y;
}
}
}
System.out.println("老鼠走过的路径（2标记的部分）");
for (int k = 0; k < 10; k++) {
for (int l = 0; l < 12; l++) {
System.out.print(MAZE[k][l]+" ");
}
System.out.println();
}
}
public static int chkExit(int x,int y,int ex,int ey){
if(x==ex&&y==ey){
if(MAZE[x-1][y]==1||MAZE[x+1][y]==1||MAZE[x][y-1]==1||MAZE[x][y+1]==2){
return 1;
}
if(MAZE[x-1][y]==1||MAZE[x+1][y]==1||MAZE[x][y-1]==2||MAZE[x][y+1]==1){
return 1;
}
if(MAZE[x-1][y]==1||MAZE[x+1][y]==2||MAZE[x][y-1]==1||MAZE[x][y+1]==1){
return 1;
}
if(MAZE[x-1][y]==2||MAZE[x+1][y]==1||MAZE[x][y-1]==1||MAZE[x][y+1]==1){
return 1;
}
}
return 0;
}
}运行结果
五、总结
其实堆栈的应用还有非常非常多 这里只做简单的举例，期待大家的三连（滑稽）