简介

1. 物理结构和逻辑结构区别

   	线性结构	非线性结构
   逻辑结构	表，队列，栈	树，图

   	顺序存储结构	链式存储结构
   物理结构	数组	链表

2. 栈（FILO）：先进后出，导航条，递归调用

3. 队列 （FIFO）：Android main Looper 消息队列，爬虫队列

基本实现

1. 栈

   // 双向链表实现
   public class Stack<T>{
     int height;
     Node<T> head,tail;
     
     public void push(T item){
       Node<T> tempNode = new Node<T>(item);
       if (height == 0) {
         head = tempNode;
         tail = head;
       } else {
   	    tail.next = tempNode;
         tail = tempNode;
       }  
       height = height + 1;
     }
     
     public T pop(){
       if (height == 0) {
   			return null;
       } else if (height == 1){
         result = head;
       	tail = null;
         head = null;
         height = 0;
         return result;
       } else {
   			tail = tail.pre;
         result = tail.next;
         tail.next = null;
         height = height - 1;
   	    return result;
       }
     }
     
     public T peek(){
       
     }
   }
   

2. 队列

   // 数组实现
   public class Queue<T>{
     
     int size;
     Object[] queue;
     final static capacity = 10;
     
     public Queue() {
       queue = new Object[capacity];
       size = capacity;
     }
     
     public void enqueue(T t){
       if (size >= queue.length) {
         // 动态扩容
         int[] newArray = new int[2 * capacity]{};
   	    System.copyArray(queue,newArray);
     	  queue = newArray;
   	    size = queue.length;
       }
   		queue[size] = t;
     }
   
     public T poll(){
       if (size == 0) {
         throw new Exception("队列为空");
       }
   		T t = queue[size -1];
      	queue[size-1] = null;
       return t;
     }
   
     public T peek(){
       if (size == 0) {
         throw new Exception("队列为空");
       }
   		return queue[size - 1];
     }
   }