数据结构

数据结构是算法的基础，一般数据结构可以分为：线性结构、非线性结构。
本文章主要是对于常用的线性数据结构进行总结。
常见的线性数据结构有：

数组 Array
链表 LinkedList
队列 Queue
栈 Stack

稀疏数组`SparseArray`

稀疏数组：如果数组中大部分的元素值都未被使用（或都为0），在数组中仅有少部分的空间使用，因此造成内存空间的浪费，为了解决这问题，并且不影响数组中原有的元素值，采用的一种压缩的方式来表示原数组的内容。

稀疏数组处理方法：

统计出原数组一共有多少行、多少列、多少个值（原数组使用的值）
把具有值的元素所在行、列、值，记录在一个小规模数组中。

二维数组转稀疏数组

二维数组转稀疏数组
1. 遍历二维数组，统计有效数据的个数count。
2. 根据有效个数count创建稀疏数组sparseArray[count + 1][3]。
3. 将二维数组有效数据存入稀疏数组。
稀疏数组还原原始二维数组
1. 读取稀疏数组第一行，根据第一行数据创建原始的二维数组。
2. 遍历稀疏数组余下行，将读取的数据填充原始的二维数组。

代码如下：

public class SparseArrayDemo {
    final static int row = 6, column = 7;

    public static void main(String[] args) {
        // 原始数组
        int [][] array = new int[row][column];
        // 设置数据
        array[0][3] =22;
        array[0][6] = 15;
        array[1][5] = 11;
        array[1][5] = 17;
        array[2][6] = -6;
        array[3][5] = 39;
        array[4][0] = 91;
        array[5][7] = 28;
        System.out.println("----------原始数组----------");
        printArray(array);
        
        // 将原二维数组转稀疏数组
        int[][] sparseArray = toSparseArray(array);
        System.out.println("----------稀疏数组----------");
        printArray(sparseArray);
        
        // 根据稀疏数组还原二维数组
        int[][] restoreArray = restoreArray(sparseArray);
        System.out.println("----------还原后数组----------");
        printArray(restoreArray);
    }

    /**
     * 将二维数组转稀疏数组
     * @param array
     * @return
     */
    public static int[][] toSparseArray(int[][] array) {
        // 1、遍历数组，获取非0个数
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (0 != array[i][j]) {
                    count++;
                }
            }
        }
        System.out.println("非0个数：" + count);
        // 2、根据非0个数创建稀疏数组
        int[][] sparseArray = new int[count + 1][3];
        sparseArray[0][0] = row;
        sparseArray[0][1] = column;
        sparseArray[0][2] = count;
        // 3、将二维数组有效数据存入稀疏数组
        int index = 1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (0 != array[i][j]) {
                    sparseArray[index][0] = i;
                    sparseArray[index][1] = j;
                    sparseArray[index][2] = array[i][j];
                    index++;
                }
            }
        }
        return sparseArray;
    }
    
    /**
     * 根据稀疏数组还原二维数组
     * @param sparseArray
     * @return
     */
    public static int[][] restoreArray(int[][] sparseArray) {
        // 1、读取稀疏数组第一行，根据第一行数据创建原始的二维数组
        int row = sparseArray[0][0],
            column = sparseArray[0][1],
            count = sparseArray[0][2];
        int[][] array = new int[row][column];
        // 2、遍历稀疏数组余下行，将读取的数据填充原始的二维数组
        for(int i = 1; i <= count; i ++) {
            array[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        return array;
    }
    
    /**
     * 打印二维数组
     * @param array
     */
    private static void printArray(int[][] array) {
        for(int i = 0; i < array.length; i++) {
            for(int j = 0; j < array[i].length; j++) {
                System.out.print(array[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

链表LinkedList

链表是有序的列表，每个节点包含两块区域：data区域（实际存储数据），next域（指向下一个节点）。

单链表

单链表数据结构代码：

public class SingleLinkedList {
    public SingleLinkedNode head;    // 指向头部的节点
    
    public SingleLinkedList() {
        super();
        head = new SingleLinkedNode();
    }
    
    // 获取指向头部节点的节点
    public SingleLinkedNode getHead() {
        return head;
    }

    // 列出节点
    public void print() {
        if(null == head.next) {
            System.err.println("~~~空链表~~~");
            return ;
        }
        SingleLinkedNode tmp = head;
        while(null != tmp.next) {
            tmp = tmp.next;
            System.out.println(tmp);
        }
    }
    
    // 移除节点
    public void delete(int index) {
        int size = size();
        if(0 > index || index >= size) {
            System.err.println(String.format("index值非法，只能在0~%s之间。", size - 1));
            return ;
        }
        // 找到待移除节点的前一个节点
        SingleLinkedNode tmp = head;
        for(int i = 0; i < index - 1; i++) {
            tmp = tmp.next;
        }
        tmp.next = tmp.next.next;
    }

    // 插入节点:尾部
    public void add(int id) {
        SingleLinkedNode newNode = new SingleLinkedNode(id);
        // 头部节点空
        if(null == head.next) {
            head.next = newNode;
            return ;
        }
        // 找到尾部节点
        SingleLinkedNode tmp = head;
        while(null != tmp.next) {
            tmp = tmp.next;
        }
        tmp.next = newNode;
    }
    
    // 插入节点：头部
    public void addNodeHead(int id) {
        SingleLinkedNode newNode = new SingleLinkedNode(id);
        if(null == head.next) {
            head.next = newNode;
            return ;
        }
        SingleLinkedNode tmp = head.next;
        newNode.next = tmp;
        head.next = newNode;
    }
    
    // 插入节点：指定位置前插入。(0:从头部插入； size -1:从尾部插入; 中间数，则从中间插入)
    public void addNodeIndex(int index, int id) {
        int size = size();
        if(0 > index || index >= size) {
            System.err.println(String.format("index值非法，只能在0~%s之间。", size - 1));
            return ;
        }
        SingleLinkedNode newNode = new SingleLinkedNode(id);
        SingleLinkedNode tmp = head;
        for (int i = 0; i < index; i ++) {
            tmp = tmp.next;
        }
        SingleLinkedNode tmpNext = tmp.next;
        newNode.next = tmpNext;
        tmp.next = newNode;
    }
    
    // 链表数据个数(有效节点个数)
    public int size() {
        if(null == head.next) {
            return 0;
        }
        int size = 0;
        SingleLinkedNode tmp = head;
        while(null != tmp.next) {
            tmp = tmp.next;
            size ++;
        }
        return size;
    }
    
    /*
     * 获取链表中倒数第lastIndex节点
     * 思路 ：
     * 1、获取链表有效节点个数 size
     * 2、从头开始遍历单链表，遍历至第(size - lastIndex)。得到的节点即为目标节点
     */
    public SingleLinkedNode findLastIndex(int lastIndex) {
        int size = size();
        if(0 > lastIndex || lastIndex > size) {
            System.err.println("不存在该倒数第" + lastIndex + "节点！");
            return null;
        }
        SingleLinkedNode tmp = head.next;
        for(int i = 0; i < (size - lastIndex); i ++) {
            tmp = tmp.next;
        }
        return tmp;
    }
    
    /*
     * 单链表反转
     * 思路：
     * 1、定义一个新的单链表
     * 2、遍历当前链表，将每次获取的节点取出，插入到新的单链表最前端
     */
    public SingleLinkedList reverseLinkedList() {
        // 1、定义一个新的单链表
        SingleLinkedNode reverseHead = new SingleLinkedNode();
        // 2、遍历当前链表，将每次获取的节点取出，插入到新的单链表最前端
        SingleLinkedNode currentNode = head.next;    // 当前操作节点
        SingleLinkedNode nextNode = null;    // 当前操作节点next节点
        while(null != currentNode) {
            nextNode = currentNode.next;
            currentNode.next = reverseHead.next;
            reverseHead.next = currentNode;
            currentNode = nextNode;
        }
        head = reverseHead;
        return this;
    }
    
    // 逆序打印单链表
    public void reversePrint() {
        Deque<SingleLinkedNode> stack = new ArrayDeque<SingleLinkedNode>(); 
        SingleLinkedNode current = head;
        while(null != current.next) {
            current = current.next;
            stack.push(current);;
        }
        while(stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
    
    /**
     * 节点
     * @author jyoryo
     *
     */
    class SingleLinkedNode {
        private int id;    // 数据域
        private SingleLinkedNode next;    // next域
        
        public SingleLinkedNode() {
            super();
        }
        public SingleLinkedNode(int id) {
            super();
            this.id = id;
        }
        public int getId() {
            return id;
        }
        public void setId(int id) {
            this.id = id;
        }
        public SingleLinkedNode getNext() {
            return next;
        }
        public void setNext(SingleLinkedNode next) {
            this.next = next;
        }
        @Override
        public String toString() {
            return "SingleLinkedNode [id=" + id + "]";
        }
    }
}


public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        for(int i = 1; i <= 10; i ++) {
            singleLinkedList.add(i);
        }
        System.out.println("------打印链表-------");
        singleLinkedList.print();
        
        System.out.println("------链表Size-------");
        System.out.println(singleLinkedList.size());
        
         System.out.println("------头部插入-------");
         singleLinkedList.addNodeHead(11);
         singleLinkedList.print();
        
        System.out.println("------按index插入-------");
        singleLinkedList.addNodeIndex(1, 12);
        singleLinkedList.print();
        
        System.out.println("------按index删除-------");
        singleLinkedList.delete(5);
        singleLinkedList.print();
        
        System.out.print("------倒数第index节点-------");
        System.out.println(singleLinkedList.findLastIndex(5));
        
        System.out.println("------逆序打印链表-------");
        singleLinkedList.reversePrint();
        
        System.out.println("------反转链表-------");
        singleLinkedList.reverseLinkedList().print();
    }
}

双链表

双链表是在单链表基础上增加一个prev域（指向前一个节点）。
通过双链表可以解决单链表的一些不足。

单链表只能按一个方向查找，双链表可以向前也可也向后查找
单链表不能自我删除，需要借助复制节点，而双链表可以自我删除。

双链表数据结构代码：

public class DoubleLinkedList {
    private DoubleLinkedNode head;    //指向头部节点
    

    public DoubleLinkedList() {
        super();
        head = new DoubleLinkedNode();
    }

    // 获取指向头部节点的节点
    public DoubleLinkedNode getHead() {
        return head;
    }
    
    // 打印节点
    public void print() {
        if(null == head.next) {
            System.err.println("~~~空链表~~~");
            return ;
        }
        DoubleLinkedNode tmp = head.next;
        while(null != tmp) {
            System.out.println(tmp);
            tmp = tmp.next;
        }
    }
    
    //  逆序打印
    public void reversePrint() {
        if(null == head.next) {
            System.err.println("~~~空链表~~~");
            return ;
        }
        // 找到尾部节点
        DoubleLinkedNode tmp = head;
        while(null != tmp.next) {
            tmp = tmp.next;
        }
        // 从尾部节点开始打印
        while(head != tmp) {
            System.out.println(tmp);
            tmp = tmp.prev;
        }
    }
    
    // 移除节点
    public void delete(int index) {
        int size = size();
        if(0 > index || index > size) {
            System.err.printf("index非法，只能在0~%d之间！\n", size - 1);
            return ;
        }
        // 找到待移除的节点
        DoubleLinkedNode tmp = head;
        for(int i = 0; i <= index; i ++) {
            tmp = tmp.next;
        }
        // 移除节点的上一个节点next域指向移除节点下一个节点
        tmp.prev.next = tmp.next;
        // 移除节点的下一个节点prev域指向移除节点上一个节点(可能不存在)
        if(null != tmp.next) {
            tmp.next.prev = tmp.prev;
        }
    }
    
    // 插入节点：尾部
    public void add(int id) {
        DoubleLinkedNode newNode = new DoubleLinkedNode(id);
        if(null == head.next) {
            head.next = newNode;
            newNode.prev = head;
            return ;
        }
        // 找到尾部节点
        DoubleLinkedNode tmp = head;
        while(null != tmp.next) {
            tmp = tmp.next;
        }
        tmp.next = newNode;
        newNode.prev = tmp;
    }
    
    // 插入节点：头部
    public void addHead(int id) {
        DoubleLinkedNode newNode = new DoubleLinkedNode(id);
        if(null == head.next) {
            head.next = newNode;
            newNode.prev = head;
            return ;
        }
        head.next.prev = newNode;
        newNode.next = head.next;
        newNode.prev = head;
        head.next = newNode;
    }
    
    // 插入节点：指定位置前插入。（0：从头部插入； size - 1：从尾部插入；中间数，则从中间插入）
    public void addNodeIndex(int index, int id) {
        int size = size();
        if(0 > index || index >= size) {
            System.err.printf("index值非法，只能在0~%d之间。\n", size - 1);
            return ;
        }
        DoubleLinkedNode newNode = new DoubleLinkedNode(id);
        DoubleLinkedNode tmp = head;
        for(int i = 0; i < index; i++) {
            tmp = tmp.next;
        }
        tmp.prev.next = newNode;
        newNode.prev = tmp.prev;
        tmp.next.prev = newNode;
        newNode.next = tmp.next;
    }
    
    // 链表有效节点个数
    public int size() {
        if(null == head.next) {
            return 0;
        }
        int size = 0;
        DoubleLinkedNode tmp = head;
        while(null != tmp.next) {
            tmp = tmp.next;
            size ++;
        }
        return size;
    }

    class DoubleLinkedNode {
        private int id;    // 数据域
        private DoubleLinkedNode next;    //next域 指向下一个节点
        private DoubleLinkedNode prev;    //prev域 指向上一个节点
        
        public DoubleLinkedNode() {
            super();
        }
        public DoubleLinkedNode(int id) {
            this.id = id;
        }
        public int getId() {
            return id;
        }
        public void setId(int id) {
            this.id = id;
        }
        public DoubleLinkedNode getNext() {
            return next;
        }
        public void setNext(DoubleLinkedNode next) {
            this.next = next;
        }
        public DoubleLinkedNode getPrev() {
            return prev;
        }
        public void setPrev(DoubleLinkedNode prev) {
            this.prev = prev;
        }
        @Override
        public String toString() {
            return "DoubleLinkedNode [id=" + id + "]";
        }
    }
}


public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        for(int i = 1; i <= 10; i ++) {
            doubleLinkedList.add(i);
        }
        
        System.out.println("-----打印链表-----");
        doubleLinkedList.print();

        System.out.println("-----链表Size-----");
        System.out.println(doubleLinkedList.size());
        
        System.out.println("-----头部插入-----");
        doubleLinkedList.addHead(11);
        doubleLinkedList.print();
        
        System.out.println("-----按index插入-----");
        doubleLinkedList.addNodeIndex(5, 12);
        doubleLinkedList.print();
        
        System.out.println("-----逆序打印-----");
        doubleLinkedList.reversePrint();
    }
}

单向环形链表

单向环形列表与单链表类似，其主要区别是没有指向头部节点的节点head，而是存在一个起始节点first，最后一个节点的next域指向起始节点。
下面的代码是用单向环形链表来解决约瑟夫环(Josephus)：

public class CircleSingleLinkedList {
    private CircleSingleLinkedNode first;

    public CircleSingleLinkedList() {
        super();
    }
    
    // 打印节点
    public void print() {
        if(null == first) {
            System.err.println("~~~空链表~~~");
            return ;
        }
        CircleSingleLinkedNode tmp = first;
        do {
            System.out.println(tmp);
            tmp = tmp.next;
        } while(first != tmp);
    }

    // 插入节点：尾部
    public void add(int id) {
        CircleSingleLinkedNode newNode = new CircleSingleLinkedNode(id);
        if(null == first) {
            first = newNode;
            first.setNext(newNode);
            return ;
        }
        // 找到最后一个节点
        CircleSingleLinkedNode tmp = first.next;
        while(first != tmp.next) {
            tmp = tmp.next;
        }
        tmp.next = newNode;
        newNode.next = first;
    }

    // 约瑟夫问题：从第一个开始数，数到第m的节点出列（删除）
    public void count(int m) {
        int count = 1;
        CircleSingleLinkedNode currentNode = first;
        CircleSingleLinkedNode prevNode = first;
        while(null != currentNode) {
            if(count == m) {
                System.out.printf("出列节点：%s\n", currentNode);
                prevNode.next = currentNode.next;
                currentNode = prevNode.next;
                count = 1;
            }
            prevNode = currentNode;
            currentNode = currentNode.next;
            count++;
            if(currentNode == prevNode) {
                System.out.printf("最终胜出节点：%s\n", currentNode);
                break ;
            }
        }
    }

    class CircleSingleLinkedNode {
        private int id;
        private CircleSingleLinkedNode next;
        public CircleSingleLinkedNode() {
        }
        public CircleSingleLinkedNode(int id) {
            this.id = id;
        }
        public int getId() {
            return id;
        }
        public void setId(int id) {
            this.id = id;
        }
        public CircleSingleLinkedNode getNext() {
            return next;
        }
        public void setNext(CircleSingleLinkedNode next) {
            this.next = next;
        }
        @Override
        public String toString() {
            return "CircleSingleLinkedNode [id=" + id + "]";
        }
    }
}

public class Josephus {
    public static void main(String[] args) {
        CircleSingleLinkedList circleList = new CircleSingleLinkedList();
        for(int i = 1; i <= 10; i++) {
            circleList.add(i);
        }
        System.out.println("-----打印链表-----");
        circleList.print();
        
        System.out.println("-----约瑟夫问题-----");
        circleList.count(3);
    }
}

队列

队列是一个有序结构，遵循先进先出（FIFO）原则：先存入的数据，先取出；后存入的数据，后取出。可以用数组或链表来实现。
使用数组来实现队列的思路(maxSize数组大小)：

指向队列第一个元素front，即array[front]为队列第一个元素。
指向队列尾部元素rear，即array[rear]为队列最后一个元素。
队列满的条件：(rear + 1) % maxSize == front
队列为空的条件：rear == front
队列中有效数据的数量：(rear + maxSize - front) % maxSize

public class ArrayQueue {
    // 队列最大容量
    private int maxSize;
    // 队列头index，array[front]指向第一个元素。初始值0
    private int front;
    // 队列尾index，array[rear]指向最后一个元素。初始值0
    private int rear;
    // 存储队列数据
    private int array[];

    public ArrayQueue(int maxSize) {
        super();
        this.maxSize = maxSize;
        array = new int[maxSize];
    }

    // 判断队列是否满
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

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

    // 队列数据个数
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }

    // 添加数据
    public void add(int num) {
        if (isFull()) {
            System.err.println("队列已满，不允许添加数据！");
            return;
        }
        array[rear] = num;
        rear = (rear + 1) % maxSize;
    }

    // 取出数据
    public int remove() {
        if (isEmpty()) {
            throw new RuntimeException("队列没有数据！");
        }
        int value = array[front];
        front = (front + 1) % maxSize;
        return value;
    }

    // 查看数据
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("队列没有数据！");
        }
        return array[front];
    }

    // 打印队列
    public void print() {
        if (isEmpty()) {
            System.err.println("队列没有数据！");
        }
        for (int i = front; i < front + size(); i++) {
            System.out.printf("array[%s]=%d\n", i, array[i % maxSize]);
        }
    }
}


public class ArrayQueueDemo {
    public static void main(String[] args) {
        System.out.println("测试使用环形数组模拟队列>>>");
        ArrayQueue queue = new ArrayQueue(5);    // 队列最大有效数据为4
        // 用于接受用户输入
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while (loop) {
            System.out.println("p(print)打印队列");
            System.out.println("a(add)向队列添加数据");
            System.out.println("h(hear)查看队列头数据");
            System.out.println("r(remove)向队列取出数据");
            System.out.println("e(exit)退出");
            
            key = scanner.next().charAt(0);
            switch(key) {
                case 'p':
                    queue.print();
                    break;
                case 'a':
                    System.out.println("请输入待添加的数：");
                    int value = scanner.nextInt();
                    queue.add(value);
                    break ;
                case 'h':
                    try {
                        int peekValue = queue.peek();
                        System.out.printf("队列头数据：%d\n", peekValue);
                    } catch(Exception e) {
                        System.err.println(e.getMessage());
                    }
                    break ;
                case 'r':
                    try {
                        int removeValue = queue.remove();
                        System.out.printf("取出的数：%d\n", removeValue);
                    } catch(Exception e) {
                        System.err.println(e.getMessage());
                    }
                    break ;
                case 'e':
                    scanner.close();
                    loop = false;
                    break ;
                default:break;
            }
        }
    }
}

栈`Stack`

栈与队列类似，也是一个有序结构，不过遵循先进后出(FILO)原则：最先存入的数据，最后取出；最后存入的数据，最先取出。
栈是限制线性结构中的元素添加和删除只能在线性的同一端进行。允许操作（添加、删除）的一段为变化的一端，称为栈顶；另一端为固定的一端，称为栈底。

栈的应用场景：

子程序的调用：在调用子程序前，会将下个指令的地址存到堆栈中，知道子程序执行完成后再将地址取出，以回到原来的程序中。
处理递归调用：和上面子程序调用类似，除了存储下一个指令的外，也将参数、区域变量等数据存入堆栈中。
表达式转换（中缀表达式转后缀表达式）与求值。
二叉树的遍历。
图的深度优先搜索法。

数组来实现栈的思路：

定义一个top来表示栈顶，初始值为-1；
入栈操作：
1. top++;
2. array[top] = data；
出站操作：
1. value = array[top];
2. top --;
3. return value;

public class ArrayStatck {
    private int maxSize;
    private int top = -1;
    private int array[];
    
    public ArrayStatck(int maxSize) {
        this.maxSize = maxSize;
        array = new int[maxSize];
    }
    
    // 栈是否满
    public boolean isFull() {
        return top == (maxSize - 1);
    }
    
    // 栈是否空
    public boolean isEmpty() {
        return -1 == top;
    }
    
    // 打印栈
    public void print() {
        if(isEmpty()) {
            System.out.println("~~~空栈~~~");
            return ;
        }
        for(int i = top; i >= 0; i--) {
            System.out.println(array[i]);
        }
    }
    
    // 入栈
    public void push(int value) {
        if(isFull()) {
            System.err.println("栈已满，不允许入栈！");
            return ;
        }
        top++;
        array[top] = value;
    }
    
    // 出栈
    public int pop() {
        if(isEmpty()) {
            throw new RuntimeException("栈已空，不允许出栈操作！");
        }
        int value = array[top];
        top --;
        return value;
    }
    
    // 查看栈顶数据
    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("栈已空！");
        }
        return array[top];
    }
}

public class ArrayStatckDemo {
    public static void main(String[] args) {
        System.out.println(">>>使用数组测试模拟栈>>>");
        ArrayStatck stack = new ArrayStatck(10);
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while(loop) {
            System.out.println("p(print)打印栈");
            System.out.println("a(push)入栈操作");
            System.out.println("r(pop)出栈操作");
            System.out.println("v(peek)查看栈顶数据");
            System.out.println("e(exit)退出");
            key = scanner.next().charAt(0);
            switch(key) {
                case 'p':
                    stack.print();
                    break ;
                case 'a':
                    System.out.println("请输入待添加的整数：");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break ;
                case 'r':
                    try {
                        System.out.printf("出栈数据：%d\n", stack.pop());
                    } catch(Exception e) {
                        System.err.println(e.getMessage());
                    }
                    break ;
                case 'v':
                    try {
                        System.out.printf("栈顶数据：%d\n", stack.peek());
                    } catch(Exception e) {
                        System.err.println(e.getMessage());
                    }
                    break ;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:break;
            }
        }
    }
}

一个栈都会实现如push(T), pop(), peek(), isEmpty()等方法，可以自定义一个Stack接口：

/**
 * 栈接口
 * @author jyoryo
 * @param <T>
 */
public interface Stack<T> {
    /**
     * 将元素压入栈
     * @param element
     */
    void push(T element);
    
    /**
     * 从栈弹出元素
     * @return
     */
    T pop();
    
    /**
     * 查看栈顶元素
     * @return
     */
    T peek();
    
    /**
     * 是否是空栈
     * @return
     */
    boolean isEmpty();
}

利用容器实现栈Stack：

/**
 * 基于容器实现栈
 * @author jyoryo
 * @param <T>
 */
public class ListStack<T> implements Stack<T> {
    private List<T> list;

    public ListStack() {
        list = new ArrayList<>();
    }

    @Override
    public void push(T element) {
        list.add(element);
    }

    @Override
    public T pop() {
        if(isEmpty()) {
            throw new EmptyStackException();
        }
        return list.remove(list.size() - 1);
    }

    @Override
    public T peek() {
        if(isEmpty()) {
            throw new EmptyStackException();
        }
        return list.get(list.size() - 1);
    }

    @Override
    public boolean isEmpty() {
        return 0 == list.size();
    }
}

一个更加通用的栈实现（基于泛型和链表，参考《Java编程思想（第四版）》）

/**
 * 链表栈
 * @author jyoryo
 * @param <T>
 */
public class LinkedStack<T> implements Stack<T> {
    private static class Node<U> {
        U item;
        Node<U> next;
        Node() { this.item = null; this.next = null; }
        Node(U item, Node<U> next) {
            this.item = item;
            this.next = next;
        }
        boolean end() { return (null == item) && (null == next); }
    }
    
    private Node<T> top;

    public LinkedStack() {
        top = new Node<>();
    }

    @Override
    public void push(T element) {
        top = new Node<T>(element, top);
    }

    @Override
    public T pop() {
        if(isEmpty()) {
            throw new EmptyStackException();
        }
        T result = top.item;
        if(!top.end()) {
            top = top.next;
        }
        return result;
    }

    @Override
    public T peek() {
        if(isEmpty()) {
            throw new EmptyStackException();
        }
        return top.item;
    }

    @Override
    public boolean isEmpty() {
        return top.end();
    }
}

利用栈实现中缀表达式模拟计算器

使用栈完成计算器思路：

定义2个栈：一个栈numberStatck存储表达式中的数字，一个栈operatorStack存储表达式中的运算符。
定义变量numberSize记录连续是数字的大小，变量operatorIndex记录最后一次出现运算符的索引。
循环计算的表达式字符串。
如果当前字符是数字，记录连续数字大小加1：numberSize ++。
如果当前字符是运算符：
5.1 先更新最后一次出现运算符索引operatorIndex = i
5.2 处理数字：判断numberSize 是否大于0，如果大于0，提取数字expression.substring(i - numberSize, i)入数字栈numberStatck。最后重置numberSize计数。
5.3 判断操作符栈是否为空：如果为空，将操作符入操作符栈，进入下次循环；如果不为空的话，如果当前操作符优先级是否小于或等于操作符栈中的操作符，就需要从数字栈中出2个数字，操作符栈中出1个操作符进行运算，将运算结果入数字栈。
5.4 将当前操作符入符号栈。
将最后运算符后面的数字expression.substring(operatorIndex + 1, length)入数字栈。
表达式循环结束后，就循环操作符栈取操作符，每取一个操作符的同时，从数字栈取2个数字，进行计算，将计算结果入数字栈。
最后在数字栈中只有一个数字，就是表达式结果。

具体实现代码：

public class InfixExpressionCalculator {
    public static void main(String[] args) {
        ArrayStatck numberStatck = new ArrayStatck(10);
        ArrayStatck operatorStack = new ArrayStatck(10);
        String expression = "702*22*2-594+1456-56+35-4";
        System.out.println("原表达式：" + expression);
        int length = expression.length();
        int numberSize = 0;    // 记录连续数字长度
        int operatorIndex = 0;    // 当前运算符所在index
        for(int i = 0; i < length; i++) {
            char ch = expression.charAt(i);
            // 数字
            if(!isOperator(ch)) {
                numberSize ++;
                continue ;
            }
            // 运算符
            operatorIndex = i;
            // 处理数字
            if(numberSize > 0) {
                System.out.println(expression.substring(i - numberSize, i));
                numberStatck.push(Integer.parseInt(expression.substring(i - numberSize, i)));
            }
            numberSize = 0;
            
            // 操作符栈是空
            if(operatorStack.isEmpty()) {
                operatorStack.push(ch);
                continue ;
            }
            // 操作符栈不为空，判断当前操作符优先级是否小于等于操作符栈顶元素的优先级
            if(priority(ch) <= priority((char) operatorStack.peek())) {
                int result = cal(numberStatck.pop(), numberStatck.pop(), (char)operatorStack.pop());
                // 运算结果入栈
                numberStatck.push(result);
            }
            // 当前操作符入栈
            operatorStack.push(ch);
        }
        // 最后部分是数字
        numberStatck.push(Integer.parseInt(expression.substring(operatorIndex + 1, length)));
        
        // 遍历操作符栈
        while(!operatorStack.isEmpty()) {
            int result = cal(numberStatck.pop(), numberStatck.pop(), (char)operatorStack.pop());
            numberStatck.push(result);
        }
        System.out.println("结果：" + numberStatck.pop());
    }

    // 是否是运算符
    public static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }
    
    // 运算符优先级
    public static int priority(char operator) {
        if(operator == '*' || operator == '/') {
            return 1;
        } else if(operator == '+' || operator == '-') {
            return 0;
        }
        return -1;
    }
    
    // 根据操作符进行计算
    public static int cal(int number1, int number2, char operator) {
        switch(operator) {
            case '+':
                return number1 + number2;
            case '-':
                return number2 - number1;
            case '*':
                return number1 * number2;
            case '/':
                return (int)(number2 / number1);
            default:return 0;
        }
    }
}

后缀表达式

后缀表达式也叫作逆波兰表达式。
例如表达式(3 + 4) x 5 - 6对应的后缀表达式是3 4 + 5 x 6 -。

使用后缀表达式实现计算器：

public class PolandCalculator {
    public static void main(String[] args) {
        // (30 + 4) * 5 - 6 ===> 30 4 + 5 * 6 -(中间以一个空格分隔)
        String expression = "30 4 + 5 * 6 -";
        String [] partArray = expression.split("\\s");
        int result = calculate(partArray);
        System.out.println("计算结果：" + result);
    }
    
    // 逆波兰表示进行计算
    public static int calculate(String [] parts) {
        // 栈
        Deque<String> numberStatck = new ArrayDeque<String>();
        for(String part : parts) {
            // 数字
            if(part.matches("\\d+")) {
                numberStatck.push(part);
                continue ;
            }
            // 非数字
            int number2 = Integer.parseInt(numberStatck.pop());
            int number1 = Integer.parseInt(numberStatck.pop());
            int result = 0;
            if("+".equals(part)) {
                result = number1 + number2;
            } else if("-".equals(part)) {
                result = number1 - number2;
            } else if("*".equals(part)) {
                result = number1 * number2;
            } else if("/".equals(part)) {
                result = number1 / number2;
            } else {
                throw new RuntimeException(part + "不是合法的运算符！");
            }
            // 计算结果入栈
            numberStatck.push(String.valueOf(result));
        }
        return Integer.parseInt(numberStatck.pop());
    }
}

中缀表达式转换为后缀表达式

上面运用后缀表达式实现计算器比较简单，也不用考虑括号等，但是人却不太容易写出来，特别是表达式较长的情况。通常我们需要将中缀表达式转换为后缀表达式。

中缀表达式转换为后缀表达式步骤：

定义2个栈：一个栈s1存储运算符，一个栈s2存储中间结果；
从左至右扫描中缀表达式；
如果遇到操作数，将其入栈s2中；
如果遇到运算符，将其与栈s1的栈顶运算符比较优先级：
4.1 如果栈s1为空，或栈顶运算符为(，则直接将此运算符直接入栈s1；
4.2 栈s1不为空，若运算符的优先级比运算符栈顶运算符高，也将此运算符入栈s1；
4.3 否则将s1栈顶的运算符弹出并入栈s2，再次转到4.1与s1中新的栈顶运算符比较。
遇到括号：
5.1 如果是(，则直接入栈s1；
5.2 如果是)，则一次弹出栈s1的运算符，并压入s2，直到遇到(，然后将这一对括号丢弃。
重复上面步骤2~5，直到表达式最右边；
将栈s1中剩余的运算符依次出栈并入栈s2；
一次弹出栈s2中的元素并输出，结果的逆向即为中缀表达式对应的后缀表达式。

实现代码：

public class InfixExpressionToPolandNotation {
    public static void main(String[] args) {
        String expression = "702*22*2-594+1456-56+35-4";    // 1+((2+3)*4)-5
        System.out.printf("表达式：%s\n", expression);
        List<String> results = toInfixExpressionList(expression);
        System.out.printf("中缀表达式：%s\n", Arrays.toString(results.toArray(new String[results.size()])));
        List<String> suffixResults = convertInfixExpressionToSuffixExpreesion(results);
        System.out.printf("后缀表达式:%s\n", Arrays.toString(suffixResults.toArray(new String[suffixResults.size()])));
        System.out.println("计算结果：" + calculate(suffixResults));
    }
    
    /**
     * 中缀表达式转换为后缀表达式步骤：
     * <pre>
     * 1. 定义2个栈：一个栈`s1`存储运算符，一个栈`s2`存储中间结果；
     * 2. 从左至右扫描中缀表达式；
     * 3. 如果遇到操作数，将其入栈`s2`中；
     * 4. 遇到括号：
     *  4.1 如果是`(`，则直接入栈`s1`；
     *  4.2 如果是`)`，则依次弹出栈`s1`的运算符，并压入`s2`，直到遇到`(`，然后将这一对括号丢弃。
     * 5. 如果遇到运算符，将其与栈`s1`的栈顶运算符比较优先级：
     *  5.1 如果栈`s1`为空，或栈顶运算符为`(`，则直接将此运算符直接入栈`s1`；
     *  5.2 栈`s1`不为空，若运算符的优先级比运算符栈顶运算符高，也将此运算符入栈`s1`；
     *  5.3 否则将`s1`栈顶的运算符弹出并入栈`s2`，再次转到5.1与`s1`中新的栈顶运算符比较。
     * 6. 重复上面步骤2~5，直到表达式最右边；
     * 7. 将栈`s1`中剩余的运算符依次出栈并入栈`s2`；
     * 8. 一次弹出栈`s2`中的元素并输出，结果的逆向即为中缀表达式对应的后缀表达式。
     * </pre>
     * @param items
     * @return
     */
    public static List<String> convertInfixExpressionToSuffixExpreesion(List<String> items) {
        Deque<String> s1 = new ArrayDeque<>();    // 存储运算符
        List<String> s2 = new ArrayList<>();    // 存储中间结果【由于中间没有pop操作，并且最后需要逆向，可以直接用List代替处理】
        for(String item : items) {
            // 数字
            if(item.matches("\\d+")) {
                s2.add(item);
                continue ;
            }
            // 非数字 括号
            if("(".equals(item)) {
                s1.push(item);
                continue ;
            }
            if(")".equals(item)) {
                while(!"(".equals(s1.peek())) {
                    s2.add(s1.pop());
                }
                s1.pop();
                continue ;
            }
            // 非数字 运算符
            while(s1.size() > 0 && priority(item) <= priority(s1.peek())) {
                s2.add(s1.pop());
            }
            s1.push(item);
        }
        while(s1.size() > 0) {
            s2.add(s1.pop());
        }
        while(s1.size() > 0) {
            s2.add(s1.pop());
        }
        return s2;
    }
    
    // 逆波兰表示进行计算
    public static int calculate(List<String> parts) {
        // 栈
        Deque<String> numberStatck = new ArrayDeque<String>();
        for(String part : parts) {
            // 数字
            if(part.matches("\\d+")) {
                numberStatck.push(part);
                continue ;
            }
            // 非数字
            int number2 = Integer.parseInt(numberStatck.pop());
            int number1 = Integer.parseInt(numberStatck.pop());
            int result = 0;
            if("+".equals(part)) {
                result = number1 + number2;
            } else if("-".equals(part)) {
                result = number1 - number2;
            } else if("*".equals(part)) {
                result = number1 * number2;
            } else if("/".equals(part)) {
                result = number1 / number2;
            } else {
                throw new RuntimeException(part + "不是合法的运算符！");
            }
            // 计算结果入栈
            numberStatck.push(String.valueOf(result));
        }
        return Integer.parseInt(numberStatck.pop());
    }
    
    // 表达式转换为中缀表达式
    public static List<String> toInfixExpressionList(String expression) {
        List<String> results = new ArrayList<>();
        int length = expression.length();
        int charIndex = 0;    // 最新非数字的索引
        int numberSize = 0;    // 连续数字的大小
        for(int i = 0; i < length; i ++) {
            char ch = expression.charAt(i);
            // 数字
            if(ch>= 48 && ch <= 57) {
                numberSize ++;
                continue ;
            }
            charIndex = i;
            // 处理数字
            if(numberSize > 0) {
                results.add(expression.substring(charIndex - numberSize, charIndex));
            }
            numberSize = 0;
            results.add(String.valueOf(ch));
        }
        // 最后一部分数字
        results.add(expression.substring(charIndex + 1, length));
        return results;
    }
    
    // 获取运算符优先级
    public static int priority(String operator) {
        switch (operator) {
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
            default:
                return 0;
        }
    }
}

参考资料

《Java编程思想（第四版）》

线性数据结构数组队列链表栈

数据结构

稀疏数组`SparseArray`

链表LinkedList

单链表

双链表

单向环形链表

队列

栈`Stack`

利用栈实现中缀表达式模拟计算器

后缀表达式

中缀表达式转换为后缀表达式

参考资料

仅有一条评论

添加新评论

分类

归档

线性数据结构 数组 队列 链表 栈

数据结构

稀疏数组SparseArray

链表LinkedList

单链表

双链表

单向环形链表

队列

栈Stack

利用栈实现中缀表达式模拟计算器

后缀表达式

中缀表达式转换为后缀表达式

参考资料

仅有一条评论

添加新评论

分类

归档

线性数据结构数组队列链表栈

稀疏数组`SparseArray`

栈`Stack`