复习一下数据结构，巩固一下基础。

栈

import java.util.Arrays;public class Stack {    private int size;    private int[] array;        public Stack() {        this(10);    }    public Stack(int init) {        if(init <= 0) {            init = 10;        }        array = new int[init];    }    public void push(int item) {        if(size == array.length) {            array = Arrays.copyOf(array, size * 2);        }        array[size++] = item;    }    public int peek() {        if(size == 0) {            throw new ArrayIndexOutOfBoundsException("栈已经空啦");        }        return array[size - 1];    }    public int pop() {        int item = peek();        size--;        return item;    }    public boolean isFull() {        return size == array.length;    }    public boolean isEmpty() {        return size == 0;    }    public int size() {        return size;    }}

队列

public class ArrayQueue {    private final Object[] items;    private int head;    private int tail;    public ArrayQueue(int capacity) {        this.items = new Object[capacity];    }    public boolean put(Object item) {        if(head == (tail + 1) % items.length) {            return false;        }        items[tail] = item;        tail = (tail + 1) % items.length;        return true;    }    public Object peek() {        if(head == tail) {            return null;        }        return items[head];    }    public Object poll() {        if(head == tail) {            return null;        }        Object item = items[head];        items[head] = null;        head = (head + 1) % items.length;        return item;    }    public boolean isFull() {        return head == (tail + 1) % items.length;    }    public boolean isEmpty() {        return head == tail;    }    public int size() {        if(head <= tail) {            return tail - head;        }        return tail - head + items.length;    }}

用栈来模拟队列

public class Stack2Queue {    private Stack stack1;    private Stack stack2;    private int maxLength;    public Stack2Queue(int capacity) {        maxLength = capacity;        stack1 = new Stack(capacity);        stack2 = new Stack(capacity);    }    public boolean put(int item) {        if(stack1.isFull() || size() == maxLength) {            return false;        }        stack1.push(item);        return true;    }    public int poll() {        if(!stack2.isEmpty()) {            return stack2.pop();        }else {            while(!stack1.isEmpty()) {                stack2.push(stack1.pop());            }            return stack2.pop();        }    }    public int size() {        return stack1.size() + stack2.size();    }}

用队列来模拟栈

public class Queue2Stack {    private ArrayQueue queue1;    private ArrayQueue queue2;    private int maxLength;    public Queue2Stack(int capacity) {        maxLength = capacity;        queue1 = new ArrayQueue(capacity);        queue2 = new ArrayQueue(capacity);    }    public boolean push(Object item) {        if(size() == maxLength) {            return false;        }        if(queue2.isEmpty()) {            queue1.put(item);        }else {            queue2.put(item);        }        return true;    }    public Object pop() {        if(size() == 0) {//            return null;            throw new IndexOutOfBoundsException("栈里空啦");        }        if(queue2.isEmpty()) {            while(queue1.size() > 1) {                queue2.put(queue1.poll());            }            return queue1.poll();        }else {            while(queue2.size() > 1) {                queue1.put(queue2.poll());            }            return queue2.poll();        }    }    public int size() {        return queue1.size() + queue2.size();    }}

链表

public class Node {    private int data;    private Node next;    public int getData() {        return data;    }    public void setData(int data) {        this.data = data;    }    public Node getNext() {        return next;    }    public void setNext(Node next) {        this.next = next;    }}public class Link {    private int size = 0;    private Node first;    private Node last;        public Link() {            }    public void addFirst(int data) {        if(size == 0) {            fillStart(data);        }else {            Node node = new Node();            node.setData(data);            node.setNext(first);            first = node;            size++;        }    }    public void addLast(int data) {        if(size == 0) {            fillStart(data);        }else {            Node node = new Node();            node.setData(data);            last.setNext(node);            last = node;            size++;        }    }    public void add(int data, int index) {        if(size > index) {            if(size == 0) {                fillStart(data);            }else if(index == 0) {                addFirst(data);            }else if (index == size -1) {                addLast(data);            }else {                Node node = new Node();                node = get(index - 1);                Node temp = new Node();                temp.setData(data);                temp.setNext(node.getNext());                node.setNext(temp);                size++;            }        }else {            throw new IndexOutOfBoundsException("链表没有这么长");        }    }    public void removeFirst() {        if(size == 0) {            throw new IndexOutOfBoundsException("链表中没有元素");        }else if(size == 1) {            clear();        }else {            Node node = first;            first = first.getNext();            node = null;            size--;        }    }    public void removeLast() {        if(size == 0) {            throw new IndexOutOfBoundsException("链表中没有元素");        }else if(size == 1) {            clear();        }else {            Node node = get(size -2);            node.setNext(null);            last = node;            size--;        }    }    public void removeMiddle(int index) {        if(size == 0) {            throw new IndexOutOfBoundsException("链表中没有元素");        }else if(size == 1) {            clear();        }else {            Node node = get(index - 1);            Node temp = node.getNext();            node.setNext(temp.getNext());            size--;        }    }    public int size() {        return size;    }    public void clear() {        first = null;        last = null;        size = 0;    }    public Node get(int index) {        Node temp = first;        for(int i = 0; i < index; i++) {            temp = temp.getNext();        }        return temp;    }    private void fillStart(int data) {        first = new Node();        first.setData(data);        last = first;        size++;    }    public void printAll() {        Node temp = first;        System.out.println(temp.getData());        for(int i = 0; i < size - 1; i++) {            temp = temp.getNext();            System.out.println(temp.getData());        }    }}

暂时先复习了这么多，本文持续更新~

参考：

1. 《轻松学算法》赵烨