栈和队列

---

栈是先存进去的数据只能最后被取出来，是FILO（First In Last Out，先进后出）。

栈结构.png

用链表实现栈：

class Node<E>{
    Node<E> next = null;
    E data;
    public Node(E data) {this.data = data;}
}
public class Stack<E>{
    Node<E> top = null;
    public boolean isEmpty(){
      return top ==  null;
    }
    public void push(E data){
        Node<E> newNode = new Node<E>(data);
        newNode.next = top;
        top = newNode;
    }
    public E pop(){
        if(this.isEmpty()){
            return null;
        }
        E data = top.data;
        top = top.next;
        return data;
    }
    public E peek(){
        if(isEmpty()) {
            return null;
        }
        return top.data;
    }
}

队列是FIFO（First In First Out，先进先出），它保持进出顺序一致。

队列结构.png

class Node<E> {
    Node<E> next =null;
    E data;
    public Node(E data){
        this.data = data;
    }
}
public class MyQueue<E> {
    private Node<E> head = null;
    private Node<E> tail = null;
    public boolean isEmpty(){
      return head = tail;
    }
    public void put(E data){
        Node<E> newNode = new Node<E>(data);
        if(head == null && tail == null){
            head = tail = newNode;
        }else{
            tail.next = newNode;
            taile = newNode;
        }
    }
    public E pop(){
        if(this.isEmpty()){
            return null;
        }
        E data = head.data;
        head = head.next;
        return data;
    }
    public int size(){
        Node<E> tmp = head;
        int n = 0;
        while(tmp != null) {
            n++;
            tmp = tmp.next;
        }
        return n;
    }
    public static void main(String []args){
      MyQueue<Integer> q = new MyQueue<Integer>();
      q.put(1);
      q.put(2);
      q.put(3);
      System.out.println("队列长度：" + q.size());
      System.out.println("队列首元素：" + q.pop());
      System.out.println("队列首元素：" + q.pop());
    }
}

输出结果：

队列长度：3
队列首元素：1
队列首元素：2

注：
如果需要实现多线程安全，要对操作方法进行同步，用synchronized修饰方法