数据结构与算法——程序

书籍：严蔚敏 吴伟民《数据结构（C语言版）》、《大话数据结构》

视频：【尚硅谷】数据结构与算法（Java数据结构与算法）_哔哩哔哩_bilibili

语言：Java

写的不好，欢迎各位指出不足

• 数据结构与算法——程序
• • 一、稀疏数组
  • 二、队列
  • 三、链表
  • 四、栈

package atguigu;

public class d1_sparsearray {
    public static void main(String[] args) {
        int i=0,j=0;
        int[][] array1=new int[15][15];
        array1[3][4]=1;
        array1[4][8]=1;
        array1[2][5]=1;
        array1[9][11]=1;
        System.out.println("显示原数组array1：");
        for(i=0;i
            for(j=0;j
                System.out.print(" "+array1[i][j]);
            }
            System.out.println();
        }
        int sum=0;//记录有效元素个数
        for(i=0;i< array1.length;i++){
            for(j=0;j
                if(array1[i][j]!=0)
                    sum++;
            }
        }
        int[][] array_sparse=new int[sum+1][3];
        array_sparse[0][0]=15;
        array_sparse[0][1]=15;
        array_sparse[0][2]=sum;
        sum=0;//sum清零充当计数器，省的再创建一个int变量
        System.out.println("生成稀疏数组~");
        for(i=0;i
            for(j=0;j
                if(array1[i][j]!=0){
                    sum++;
                    array_sparse[sum][0]=i;
                    array_sparse[sum][1]=j;
                    array_sparse[sum][2]=array1[i][j];
                }
            }
        }
        System.out.println("显示生成的稀疏数组array_sparse：");
        for(i=0;i< array_sparse.length;i++){
            for(j=0;j<3;j++){
                System.out.print(" "+array_sparse[i][j]);
            }
            System.out.println();
        }
        int[][] array2=new int[array_sparse[0][0]][array_sparse[0][1]];
        for(i=1;i< array_sparse.length;i++){//跳过第1行
            array2[array_sparse[i][0]][array_sparse[i][1]]=array_sparse[i][2];
        }
        System.out.println("显示还原的数组array2：");
        for(i=0;i< array2.length;i++){
            for(j=0;j
                System.out.print(" "+array2[i][j]);
            }
            System.out.println();
        }
    }
}

（1）用数组实现的单向队列，只能用一次，无法复用

package atguigu;

import java.util.*;

public class d2_queuedemo1 {
    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(3);
        int opt;
        boolean loop = true;
        while (loop) {
            System.out.println("====数组队列====");
            System.out.println("1.显示队列所有元素");
            System.out.println("2.显示队列队首元素");
            System.out.println("3.元素入队");
            System.out.println("4.元素出队");
            System.out.println("5.退出");
            Scanner sc = new Scanner(System.in);
            opt = sc.nextInt();
            switch (opt) {
                case 1: {
                    arrayQueue.showQueue();
                    break;
                }
                case 2: {
                    arrayQueue.showHead();
                    break;
                }
                case 3: {
                    System.out.println("请输入要入队的元素：");
                    int n = sc.nextInt();
                    arrayQueue.enQueue(n);
                    break;
                }
                case 4: {
                    try {
                        System.out.println(arrayQueue.deQueue());
                    } catch (Exception e) {
                        System.out.println(e.toString());
                    } finally {
                        break;
                    }
                }
                case 5: {
                    sc.close();
                    loop = false;
                    break;
                }
                default: {
                    System.out.println("非法输入，请重新输入！");
                    break;
                }
            }
        }
    }
}

//使用数组模拟队列-编写一个ArrayQueue类
class ArrayQueue {
    private int maxSize;
    private int front;
    private int rear;
    private int arr[];

    //构造函数——创建队列
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = 0;//front指向队首元素
        rear = 0;//rear指向队尾元素后一个位置
    }

    //判断队列是否为空
    public boolean isEmpty() {
        if (front == rear)
            return true;
        else return false;
    }

    //判断队列是否已满
    public boolean isFull() {
        if (rear == maxSize)//数组下标和rear都是从0开始，而rear实际上比maxSize大1，但是由于从0开始，这个1相当于抵消了
            return true;
        else return false;
    }

    //显示队列中的元素
    public void showQueue() {
        if (isEmpty() == true) {
            System.out.println("队列为空");
            return;
        } else {
            for (int i = front; i < arr.length; i++) {//如果i从0开始，那么下标为（front++）前面的元素会被打印出来
                System.out.printf("arr[%d]=%dn", i, arr[i]);
            }
        }
    }

    //元素入队
    public void enQueue(int n) {
        if (isFull() == true) {
            System.out.println("队列已满，无法添加");
            return;
        } else {
            arr[rear] = n;
            rear++;//保证rear指向队尾元素的下一个位置
        }
    }

    //元素出队
    public int deQueue() {
        if (isEmpty() == true) {
            throw new RuntimeException("队列为空，没有可取的元素");
        } else {
            front++;
            return arr[front - 1];//front后移之前的位置
        }
    }

    //显示队首元素
    public void showHead() {
        if (isEmpty() == true) {
            System.out.println("队列为空，没有可取的队首元素");
        } else {
            System.out.println("队首元素：" + arr[front]);
        }
    }
}

（2）用数组实现的循环队列，可以复用

package atguigu;

import java.util.*;

public class d2_queuedemo1 {
    public static void main(String[] args) {
        CircleArrayQueue circleArrayQueue = new CircleArrayQueue(3);
        int opt;
        boolean loop = true;
        while (loop) {
            System.out.println("======数组循环队列======");
            System.out.println("1.显示队列所有元素");
            System.out.println("2.显示队列队首元素");
            System.out.println("3.显示循环队列有效元素个数");
            System.out.println("4.元素入队");
            System.out.println("5.元素出队");
            System.out.println("6.退出");
            Scanner sc = new Scanner(System.in);
            opt = sc.nextInt();
            switch (opt) {
                case 1: {
                    circleArrayQueue.showQueue();
                    break;
                }
                case 2: {
                    circleArrayQueue.showHead();
                    break;
                }
                case 3: {
                    System.out.println("有效元素个数："+circleArrayQueue.getSize());
                    break;
                }
                case 4: {
                    System.out.println("请输入要入队的元素：");
                    int n = sc.nextInt();
                    circleArrayQueue.enQueue(n);
                    break;
                }
                case 5: {
                    try {
                        System.out.println(circleArrayQueue.deQueue());
                    } catch (Exception e) {
                        System.out.println(e.toString());
                    } finally {
                        break;
                    }
                }
                case 6: {
                    sc.close();
                    loop = false;
                    break;
                }
                default: {
                    System.out.println("非法输入，请重新输入！");
                    break;
                }
            }
        }
    }
}

//使用数组模拟队列-编写一个ArrayQueue类
class CircleArrayQueue {
    private int maxSize;
    private int front;
    private int rear;
    private int arr[];

    //构造函数——创建队列
    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize + 1;//因为实际的长度有一个作为空位没有存数据，所有多分配一个长度满足用户要求
        arr = new int[this.maxSize];
        front = 0;//front指向队首元素
        rear = 0;//rear指向队尾元素后一个位置
    }

    //判断队列是否为空
    public boolean isEmpty() {
        if (front == rear)
            return true;
        else return false;
    }

    //判断队列是否已满
    public boolean isFull() {
        if ((rear + 1) % maxSize == front)//队列满时需要将尾指针rear映射回低下标
            return true;
        else return false;
    }

    //显示队列中的元素
    public void showQueue() {
        if (isEmpty() == true) {
            System.out.println("队列为空");
            return;
        } else {
            for (int i = front; i < arr.length; i++) {//如果i从0开始，那么下标为（front++）前面的元素会被打印出来
                System.out.printf("arr[%d]=%dn", i, arr[i]);
            }
        }
    }

    //元素入队
    public void enQueue(int n) {
        if (isFull() == true) {
            System.out.println("队列已满，无法添加");
            return;
        } else {
            arr[rear] = n;
            rear = (rear + 1) % maxSize;//保证rear指向队尾元素的下一个位置，并及时将超出maxSize范围的rear映射回低下标
        }
    }

    //元素出队
    public int deQueue() {
        if (isEmpty() == true) {
            throw new RuntimeException("队列为空，没有可取的元素");
        } else {
            int temp = front;
            front = (front + 1) % maxSize;//front的处理和rear一样
            return arr[temp];//front后移之前的位置
        }
    }

    //显示队首元素
    public void showHead() {
        if (isEmpty() == true) {
            System.out.println("队列为空，没有可取的队首元素");
        } else {
            System.out.println("队首元素：" + arr[front]);
        }
    }

    //返回循环队列有效元素个数
    public int getSize() {
        return (rear + maxSize - front) % maxSize;
    }
}

按是否带头结点：

1. 带头结点的链表
2. 不带头结点的链表

按链表指针域数量：

1. 单向链表
2. 双向链表
3. 循环链表（环形链表）【约瑟夫问题】

单链表示例代码：包含增删改查操作、链表反转（由head->node1->node2->tail变为head->tail->node2->node1）、逆序输出等操作。其中逆序输出可以用递归实现。

package atguigu;

import java.util.*;

public class d2_nodelist {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        Node node1 = new Node(1, "张三");
        Node node2 = new Node(2, "李四");
        Node node3 = new Node(3, "王五");
        Node node4 = new Node(4, "钱六");
        Node node5 = new Node(5, "赵七");
        singleLinkedList.addNode(1, node1);
        singleLinkedList.addNode(2, node2);
        singleLinkedList.addNode(3, node3);
        singleLinkedList.addNode(4, node4);
        singleLinkedList.addNode(5, node5);
        boolean loop = true;
        int opt;
        while (loop) {
            System.out.println("===Java单链表===");
            System.out.println("1.顺序输出链表");
            System.out.println("2.查询结点");
            System.out.println("3.添加结点");
            System.out.println("4.删除结点");
            System.out.println("5.修改结点");
            System.out.println("6.显示链表长度");
            System.out.println("7.反转链表");
            System.out.println("8.逆序输出链表");
            System.out.println("9.退出");
            Scanner sc = new Scanner(System.in);
            opt = sc.nextInt();
            switch (opt) {
                case 1: {
                    singleLinkedList.showList();
                    break;
                }
                case 2: {
                    System.out.println("请输入要查找的结点序号：");
                    int id_position = sc.nextInt();
                    System.out.println(singleLinkedList.findNode(id_position));
                    break;
                }
                case 3: {
                    System.out.println("请输入要插入的位置：");
                    int id_position = sc.nextInt();
                    System.out.println("请输入要插入的内容：");
                    String data = sc.next();
                    Node node = new Node(id_position + 1, data);
                    singleLinkedList.addNode(id_position, node);
                    break;
                }
                case 4: {
                    System.out.println("请输入要删除的结点序号：");
                    int id_position = sc.nextInt();
                    singleLinkedList.deleteNode(id_position);
                    break;
                }
                case 5: {
                    System.out.println("请输入要修改的结点序号：");
                    int id_position = sc.nextInt();
                    System.out.println("请输入要修改的内容：");
                    String data = sc.next();
                    singleLinkedList.editNode(id_position, data);
                    break;
                }
                case 6: {
                    singleLinkedList.getLength();
                    break;
                }
                case 7: {
                    singleLinkedList.reverseList(singleLinkedList.getHead());
                    System.out.println("反转后的链表：");
                    singleLinkedList.showList();
                    break;
                }
                case 8: {
                    singleLinkedList.reversePrint();
                    break;
                }
                case 9: {
                    sc.close();
                    loop = false;
                    break;
                }
                default: {
                    System.out.println("非法输入，请重新输入！");
                    break;
                }
            }
        }
    }
}

class Node {
    public int id;
    public String data;
    public Node next;//指向下一个节点

    public Node() {
    }

    public Node(int id, String data) {
        this.id = id;
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", data=" + data +
                '}';
    }
}

class SingleLinkedList {
    private Node headNode = new Node(0, "head");//头结点，不存放data，仅记录指针

    //返回头结点
    public Node getHead() {
        return headNode;
    }

    //显示整个链表
    public void showList() {
        Node head = getHead();
        while (head != null) {
            System.out.println(head.toString());
            head = head.next;
        }
    }

    //查找结点
    public Node findNode(int id_position) {
        Node temp = getHead();
        Node empty = new Node(-1, "empty result");
        while (temp != null) {
            if (temp.id == id_position) {
                return temp;
            }
            temp = temp.next;
        }
        return empty;
    }

    //添加结点,头结点记作序号0
    public void addNode(int id_position, Node node) {//插入id_position的后面
        Node temp = getHead();//头结点很重要，为了保险，这里复制了一份，对复制的这份进行操作
        while (temp.id != id_position) {//沿着链表往下找
            if (temp.next == null) {
                System.out.println("位置" + id_position + "未找到!");
                break;
            }
            temp = temp.next;//往后遍历
        }
        if (temp.data != null) {
            System.out.println("位置" + id_position + "已被占用!");
        }
        //temp是node的前一个结点
        node.next = temp.next;
        temp.next = node;
        updateId(node, 1);
    }

    //删除结点
    public void deleteNode(int id_position) {
        Node temp = getHead();
        Node prev = new Node();//待删除结点的前一个结点
        while (temp.id != id_position) {//循环终止时，temp正好指向要删除的结点
            prev = temp;
            temp = temp.next;
        }
        if (temp.next == null) {//如果要删除的是尾结点
            //释放对象
            prev.next = null;//清空指针
        } else {//如果要删除的不是尾结点
            prev.next = temp.next;
            //释放对象
            updateId(prev, -1);
        }
    }

    //修改结点data
    public void editNode(int id_position, String data) {
        Node temp = findNode(id_position);
        if (temp.data.equals("empty result") && temp.id == -1) {
            System.out.println("没有找到该序号为" + id_position + "的节点！");
            return;
        }
        temp.data = data;
    }

    //更新序号
    public void updateId(Node temp, int x) {
        while (temp.next != null) {//为尾结点时跳出循环
            temp = temp.next;
            temp.id += x;
        }
    }

    //链表长度（不算头结点）
    public void getLength() {
        Node head = getHead();
        while (head.next != null) {//得到尾结点
            head = head.next;
        }
        System.out.println("链表长度为：" + head.id);
    }

    //反转链表
    public void reverseList(Node head) {
        if (head.next == null || head.next.next == null) {//如果当前链表只有头结点或者只有头结点和另一个结点
            return;//无需反转
        }
        //辅助结点，用于遍历反转前链表
        Node current = head.next;//指向原来链表的首元结点（不放数据的头结点的下一个结点，即放数据的第一个结点）
        Node current_next = null;//指向当前结点current的下一个结点，防止原链表中断
        Node reverseHead = new Node(0, "reverseHead");//临时反转链表的头结点
        //遍历原来的链表，每遍历一个结点，就将该结点取出，并放入新的反转链表头结点reverseHead的最前端，即成为反转链表的首元结点
        while (current != null) {
            current_next = current.next;//保存当前结点current的下一个结点，防止原链表断裂
            current.next = reverseHead.next;//这步是从取出第2个结点开始，必须将原先挂在reverseHead上的链表接到新取出的current结点上，否则不知道指针地址
            reverseHead.next = current;//将新取出的current结点接在reverseHead上
            current = current_next;//current后移更新
        }
        head.next = reverseHead.next;//将临时反转链表添加到原head上
    }

    //逆序输出链表，可以使用栈
    public void reversePrint() {
        Node head = getHead();
        if (head.next == null) {//空链表特判
            System.out.println("链表为空！");
            return;
        } else {
            Stack stack = new Stack<>();
            stack.push(head);
            while (head.next != null) {
                stack.push(head.next);
                head = head.next;
            }
            while (stack.size() > 0) {
                System.out.println(stack.pop());
            }
        }
    }
}

双向链表，基于前面的单链表修改而来

package atguigu;

import java.util.Scanner;
import java.util.Stack;

public class d3_doublenodelist {
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        Node2 node1 = new Node2(1, "张三");
        Node2 node2 = new Node2(2, "李四");
        Node2 node3 = new Node2(3, "王五");
        Node2 node4 = new Node2(4, "钱六");
        Node2 node5 = new Node2(5, "赵七");
        doubleLinkedList.addNode2(1, node1);
        doubleLinkedList.addNode2(2, node2);
        doubleLinkedList.addNode2(3, node3);
        doubleLinkedList.addNode2(4, node4);
        doubleLinkedList.addNode2(5, node5);
        boolean loop = true;
        int opt;
        while (loop) {
            System.out.println("===Java双链表===");
            System.out.println("1.顺序输出链表");
            System.out.println("2.查询结点");
            System.out.println("3.添加结点");
            System.out.println("4.删除结点");
            System.out.println("5.修改结点");
            System.out.println("6.显示链表长度");
            System.out.println("7.反转链表");
            System.out.println("8.逆序输出链表");
            System.out.println("9.退出");
            Scanner sc = new Scanner(System.in);
            opt = sc.nextInt();
            switch (opt) {
                case 1: {
                    doubleLinkedList.showList();
                    break;
                }
                case 2: {
                    System.out.println("请输入要查找的结点序号：");
                    int id_position = sc.nextInt();
                    System.out.println(doubleLinkedList.findNode2(id_position));
                    break;
                }
                case 3: {
                    System.out.println("请输入要插入的位置：");
                    int id_position = sc.nextInt();
                    System.out.println("请输入要插入的内容：");
                    String data = sc.next();
                    Node2 Node2 = new Node2(id_position + 1, data);
                    doubleLinkedList.addNode2(id_position, Node2);
                    break;
                }
                case 4: {
                    System.out.println("请输入要删除的结点序号：");
                    int id_position = sc.nextInt();
                    doubleLinkedList.deleteNode2(id_position);
                    break;
                }
                case 5: {
                    System.out.println("请输入要修改的结点序号：");
                    int id_position = sc.nextInt();
                    System.out.println("请输入要修改的内容：");
                    String data = sc.next();
                    doubleLinkedList.editNode2(id_position, data);
                    break;
                }
                case 6: {
                    doubleLinkedList.getLength();
                    break;
                }
                case 7: {
                    doubleLinkedList.reverseList(doubleLinkedList.getHead());
                    System.out.println("反转后的链表：");
                    doubleLinkedList.showList();
                    break;
                }
                case 8: {
                    doubleLinkedList.reversePrint();
                    break;
                }
                case 9: {
                    sc.close();
                    loop = false;
                    break;
                }
                default: {
                    System.out.println("非法输入，请重新输入！");
                    break;
                }
            }
        }
    }
}

class Node2 {
    public int id;
    public String data;
    public Node2 next;//指向下一个节点
    public Node2 prev;//指向上一个结点

    public Node2() {
    }

    public Node2(int id, String data) {
        this.id = id;
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node2{" +
                "id=" + id +
                ", data=" + data +
                '}';
    }
}

class DoubleLinkedList {
    private Node2 headNode2 = new Node2(0, "head");//头结点，不存放data，仅记录指针

    //返回头结点
    public Node2 getHead() {
        return headNode2;
    }

    //显示整个链表
    public void showList() {
        Node2 head = getHead();
        while (head != null) {
            System.out.println(head.toString());
            head = head.next;
        }
    }

    //查找结点
    public Node2 findNode2(int id_position) {
        Node2 temp = getHead();
        Node2 empty = new Node2(-1, "empty result");
        while (temp != null) {
            if (temp.id == id_position) {
                return temp;
            }
            temp = temp.next;
        }
        return empty;
    }

    //添加结点,头结点记作序号0
    public void addNode2(int id_position, Node2 node) {//插入id_position的后面
        Node2 temp = getHead();//头结点很重要，为了保险，这里复制了一份，对复制的这份进行操作
        while (temp.id != id_position) {//沿着链表往下找
            if (temp.next == null) {
                System.out.println("位置" + id_position + "未找到!");
                break;
            }
            temp = temp.next;//往后遍历
        }
        if (temp.data != null) {
            System.out.println("位置" + id_position + "已被占用!");
        }
        //temp是node的前一个结点
        if (temp.next == null) {//链表为空
            node.next = temp.next;
            temp.next = node;
            node.prev = temp;
        } else {
            node.next = temp.next;
            temp.next = node;
            node.prev = temp;
            node.next.prev = node;
        }
        updateId(node, 1);
    }

    //删除结点
    public void deleteNode2(int id_position) {
        Node2 temp = getHead();
        while (temp.id != id_position) {//循环终止时，temp正好指向要删除的结点
            temp = temp.next;
        }
        if (temp.next == null) {//如果要删除的是尾结点
            //释放对象
            temp.prev.next = null;//清空指针
            temp.prev.prev = null;
        } else {//如果要删除的不是尾结点
            temp.prev.next = temp.next;
            temp.next.prev = temp.prev;
            //释放对象
            updateId(temp.prev, -1);
        }
    }

    //修改结点data
    public void editNode2(int id_position, String data) {
        Node2 temp = findNode2(id_position);
        if (temp.data.equals("empty result") && temp.id == -1) {
            System.out.println("没有找到该序号为" + id_position + "的节点！");
            return;
        }
        temp.data = data;
    }

    //更新序号
    public void updateId(Node2 temp, int x) {
        while (temp.next != null) {//为尾结点时跳出循环
            temp = temp.next;
            temp.id += x;
        }
    }

    //链表长度（不算头结点）
    public void getLength() {
        Node2 head = getHead();
        while (head.next != null) {//得到尾结点
            head = head.next;
        }
        System.out.println("链表长度为：" + head.id);
    }

    //反转链表
    public void reverseList(Node2 head) {
        if (head.next == null || head.next.next == null) {//如果当前链表只有头结点或者只有头结点和另一个结点
            return;//无需反转
        }
        //辅助结点，用于遍历反转前链表
        Node2 current = head.next;//指向原来链表的首元结点（不放数据的头结点的下一个结点，即放数据的第一个结点）
        Node2 current_next = null;//指向当前结点current的下一个结点，防止原链表中断
        Node2 reverseHead = new Node2(0, "reverseHead");//临时反转链表的头结点
        //遍历原来的链表，每遍历一个结点，就将该结点取出，并放入新的反转链表头结点reverseHead的最前端，即成为反转链表的首元结点
        while (current != null) {
            current_next = current.next;//保存当前结点current的下一个结点，防止原链表断裂
            current.next = reverseHead.next;//这步是从取出第2个结点开始，必须将原先挂在reverseHead上的链表接到新取出的current结点上，否则不知道指针地址
            reverseHead.next = current;//将新取出的current结点接在reverseHead上
            current = current_next;//current后移更新
        }
        head.next = reverseHead.next;//将临时反转链表添加到原head上
    }

    //逆序输出链表
    public void reversePrint() {
        Node2 head = getHead();
        if (head.next == null) {//空链表特判
            System.out.println("链表为空！");
            return;
        } else {
            while (head.next!=null) {
                head=head.next;
            }
            while(head.prev!=null){
                System.out.println(head);
                head=head.prev;
            }
            System.out.println(head);
        }
    }
}

循环链表在此不再赘述

package atguigu;

import java.util.Scanner;

public class d4_stack {
    public static void main(String[] args) {
        ArrayStack arrayStack = new ArrayStack(5);
        Scanner sc = new Scanner(System.in);
        int opt;
        boolean loop = true;
        while (loop) {
            System.out.println("====数组栈====");
            System.out.println("1.输出栈");
            System.out.println("2.入栈");
            System.out.println("3.出栈");
            System.out.println("4.退出");
            opt = sc.nextInt();
            switch (opt) {
                case 1: {
                    arrayStack.showStack();
                    break;
                }
                case 2: {
                    System.out.println("请输入入栈元素：");
                    int value = sc.nextInt();
                    arrayStack.push(value);
                    break;
                }
                case 3: {
                    try {
                        System.out.println("出栈值：" + arrayStack.pop());
                    } catch (Exception e) {
                        System.out.println(e.toString());
                    } finally {
                        break;
                    }
                }
                case 4: {
                    sc.close();
                    loop = false;
                    break;
                }
                default: {
                    System.out.println("非法输入，请重新输入！");
                    break;
                }
            }
        }
    }
}

class ArrayStack {
    public int maxSize;
    public int[] stack;
    int top = 0;//栈顶指针

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[maxSize];
    }

    //判断栈满
    public boolean isFull() {
        if (top == maxSize)
            return true;
        else return false;
    }

    //判断栈空
    public boolean isEmpty() {
        if (top == 0) return true;
        else return false;
    }

    //入栈
    public void push(int value) {
        if (isFull() == true) {
            System.out.println("栈已满，无法入栈！");
            return;
        } else {
            top++;
            stack[top] = value;
        }
    }

    //出栈
    public int pop() {
        if (isEmpty() == true) {
            throw new RuntimeException("栈空，无法出栈！");
        } else {
            int temp = stack[top];
            top--;
            return temp;
        }
    }

    //显示栈所有元素
    public void showStack() {
        if (isEmpty()) {
            System.out.println("栈空");
            return;
        } else {//全部出栈
            for (int i = top; i >= 0; i--) {
                System.out.printf("stack[%d]=%dn", i, stack[i]);
            }
        }
    }
}

剩余部分和数据结构与算法笔记合并