数据结构 堆栈

堆栈特点

• 只能从顶部存取数据
• “先进后出”原则

定义堆栈

class StackByArray<T>{
     private T[] stack;
     private int top;
     public StackByArray(int stack_size){
         this.stack = new T[stack_size];
         this.top = -1;
     }
     public boolean isEmpty(){}
     public boolean push(T data){}
     public T pop(){}
}
class StackByLink<T>{
     private Node<T> stackTop;
     public StackByLink(){
         this.stackTop = null;
     }
     public boolean isEmpty(){}
     public boolean push(T data){}
     public T pop(){}
}
class Node<T>{
   T data;
   Node next;
   public Node(T data){
      this.data = data;
      this.next = null;
   }
}

数组实现堆栈

public boolean isEmpty(){
    if(this.top == -1){return true;}
    return false;
}
public boolean push(T data){
    if(this.top >= (this.stack.length-1)){
        System.out.println("堆栈已满");
        return false;
    }
    this.stack[++this.top] = data;
    return true;
}
public T pop(){
    if(isEmpty()){
        System.out.println("堆栈为空");
        return null;
    }
    return (T)this.stack[this.top--];
}

链表实现堆栈

public boolean isEmpty(){
    if(stackTop == null){return true;}
    return false;
}
public void push(T data){
    Node<T> newNode = new Node(data);
    if(isEmpty()){
        this.stackTop = newNode;
    }else{
        newNode.next = this.stackTop;
        this.stackTop = newNode;
    }
    this.size++;
}
public T pop(){
    if(isEmpty()){
        System.out.println("堆栈为空");
        return null;
    }
    Node<T> newNode = this.stackTop;
    this.stackTop = this.stackTop.next;
    this.size--;
    return newNode.data;
}

堆栈应用-走迷宫

• ⭕ 代表开始和结束的位置
• 1 ：代表墙体，无法通行。
• 0 ： 代表路，可通行。
• 走过的路 0 变为 2

public class TraceRecord {

    class Node{
       int x;
       int y;
        Node next;
        public Node(int x, int y) {
           this.x = x;
           this.y = y;
           this.next = null;
        }
    }
    private Node stackTop;

    private int size = 0;
    public TraceRecord(){
        this.stackTop = null;
    }

    public int size(){
        return this.size;
    }
    public boolean isEmpty(){
        if(stackTop == null){return true;}
        return false;
    }
    public void push(int x, int y){
        Node newNode = new Node(x, y);
        if(isEmpty()){
            this.stackTop = newNode;
        }else{
            newNode.next = this.stackTop;
            this.stackTop = newNode;
        }
        this.size++;
    }
    public Node pop(){
        if(isEmpty()){
            System.out.println("堆栈为空");
            return null;
        }
        Node newNode = this.stackTop;
        this.stackTop = this.stackTop.next;
        this.size--;
        return newNode;
    }
}

public class Labyrinth {
    public static int EndX = 8;
    public static int EndY = 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, 1, 1, 0, 1, 1},
            {1, 1, 0, 0, 0, 0, 0, 0, 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 record = new TraceRecord();
        x=y=1;

        while (x<=EndX && y<=EndY){
            MAZE[x][y] = 2;
            if (MAZE[x-1][y] == 0){
                x-=1;
                record.push(x,y);
            }else
                if (MAZE[x+1][y] == 0){
                    x+=1;
                    record.push(x,y);
                }else
                    if (MAZE[x][y-1] == 0){
                        y-=1;
                        record.push(x,y);
                }else
                    if (MAZE[x][y+1] == 0){
                        y+=1;
                        record.push(x,y);
                    }else
                        if (isExit(x,y)){
                            break;
                        }else {
                            MAZE[x][y] = 2;
                            TraceRecord.Node node = record.pop();
                            x = node.x;
                            y = node.y;
                        }
        }
    }

    public static boolean isExit(int x, int y){
        if (x == EndX && y == EndY){
            return true;
        }
        return false;
    }

}