数据结构与算法 - 栈（java）

说明

实际需求：计算器

栈的介绍

1. 栈的英文为(stack)
2. 栈是一个先入后出(FILO-FirstInLastOut)的有序列表。
3. 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
4. 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删
5. 图解方式说明出栈(pop)和入栈(push)的概念
   【入栈】
   
   【出栈】
   

栈的应用场景

1. 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
2. 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
3. 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
4. 二叉树的遍历。
5. 图形的深度优先(depth一first)搜索法。

数组实现栈

介绍

入栈：top++;stack[top]=date;
出栈：int value = stack[top];top–;return value;

代码

数组 - 栈

class MyArrayStack{
    private int maxSize; //栈的大小
    private int[] stack; //数组
    private int top = -1;//栈顶

    //构造器 - 初始化数组
    public MyArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    //入栈 - push
    public void push(int value){
        //是否为满
        if (top == maxSize - 1){
            System.out.println("栈已满，不能添加数据");
        }
        //添加
        top++;
        stack[top] = value;
    }

    //出栈 - pop
    public int pop(){
        //是否为空
        if (top == -1){
            throw new RuntimeException("栈空，没有数据");
        }
        //出栈
        int value = stack[top];
        top--;
        return value;
    }

    //显示 - 遍历
    public void show(){
        //是否为空
        if (top == -1){
            System.out.println("栈空，没有数据");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.println("stack[" + i + "] = " + stack[i]);
        }
    }
}

测试

public class ArrayStack {
    public static void main(String[] args) {
        MyArrayStack stack = new MyArrayStack(5);
        int key;
        Scanner scanner = new Scanner(System.in);
        boolean isFalse = true;

        while (isFalse){
            System.out.println("---- 栈 ----");
            System.out.println("  1：显示栈");
            System.out.println("  2：入栈");
            System.out.println("  3：出栈");
            System.out.println("  4：退出");
            System.out.print("  输入选择：");
            key = scanner.nextInt();
            switch (key){
                case 1:stack.show();break;
                case 2:
                    System.out.print("输入一个数：");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case 3:
                    try {
                        int pop = stack.pop();
                        System.out.println("出栈数据：" + pop);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 4:isFalse = false;break;
            }
        }
    }
}

链表实现栈

介绍

入栈:top.next = date;top = top.next
出栈:top.next = null

代码

节点数据

class Date{
    public int number;
    public Date next;

    public Date(int number) {
        this.number = number;
    }

    @Override
    public String toString() {
        return "Date{" +
                "number=" + number +
                '}';
    }
}

栈

class MyLinkedListStack{
    private Date head = new Date(0);

    //入队-push
    public void push(int value){
        Date date = new Date(value);
        Date temp = head;
        //遍历，找到最后一个节点
        while (true){
            if (temp.next == null){
                break;
            }
            temp = temp.next;
        }
        temp.next = date;
    }

    //出队-pop
    public void pop() {
        if (head.next == null){
            System.out.println("栈为空，没有数据");
            return;
        }
        Date temp = head;
        //遍历，找到倒数第二个节点
        while (true){
            if (temp.next.next == null){
                break;
            }
            temp = temp.next;
        }
        System.out.println("出栈节点：" + temp.next);
        temp.next = null;
    }

    //显示-show
    public void show(){
        if (head.next == null){
            System.out.println("栈为空，没有数据");
            return;
        }
        Date temp = head.next;
        //遍历，
        while (true){
            if (temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }

    }
}

测试

public class LinkedListStack {
    public static void main(String[] args) {
        MyLinkedListStack stack = new MyLinkedListStack();
        int key;
        Scanner scanner = new Scanner(System.in);
        boolean isFalse = true;

        while (isFalse){
            System.out.println("---- 栈 ----");
            System.out.println("  1：显示栈");
            System.out.println("  2：入栈");
            System.out.println("  3：出栈");
            System.out.println("  4：退出");
            System.out.print("  输入选择：");
            key = scanner.nextInt();
            switch (key){
                case 1:stack.show();break;
                case 2:
                    System.out.print("输入一个数:");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case 3:stack.pop();break;
                case 4:isFalse = false;break;
            }
        }
    }
}