2、栈&队列&链表

今天药忘吃喽~ 2022-05-27 03:45 205阅读 0赞

在java中，常见于集合如List这种写法，就是确保一个集合内的所有对象是属于一个类型的。

## 算术表达式的存储 ##

如何让一个算术表达式正确的执行？

> 5 +2\*3 +4/2

E.W.Dijkstra在上世纪60年代发明了一种简单的存储方法，使用2个栈，一个用来保存数字，一个用来保存运算符号；

1、将数字压入 数字栈
    2、将运算符号压入 符号栈
    3、忽略左括弧
    4、遇到右括弧时，取出 前面的 数字栈 和 符号栈进行计算 并压入数字栈

public class Evaluate {
        public static void main(String[] args) {
            Stack<String> ops = new Stack<>();
            Stack<Double> nums = new Stack<>() ;
    
            String str = "(2+(5*2) ) + (2*4)" ; //这里需要做括弧分割!!
            str = "(" +str+")" ;  //格式化输入
    
            for(int i=0;i<str.length();i++){
                String subStr = str.substring(i, i+1) ;
                System.out.println(subStr);
                if(subStr.equals(" ")) ;
                else if(subStr.equals("(")) ;
                else if(subStr.equals("+")) ops.push(subStr) ;
                else if(subStr.equals("-")) ops.push(subStr) ;
                else if(subStr.equals("*")) ops.push(subStr) ;
                else if(subStr.equals("/")) ops.push(subStr) ;
                else if(subStr.equals("sqrt")) ops.push(subStr) ;
                else if(subStr.equals(")")) {  //输出标识
                    System.out.println("-------");
                    String op = ops.pop();
                    double var = nums.pop() ;
                    if(op.equals("+")) var = nums.pop() + var ;
                    else if(op.equals("-")) var = nums.pop() - var ;
                    else if(op.equals("*")) var = nums.pop() * var ;
                    else if(op.equals("/")) var = nums.pop() / var ;
                    else if(op.equals("sqrt")) var = Math.sqrt(var) ;
                    nums.push(var) ;
                }
                else {
                    nums.push(Double.parseDouble(subStr)) ;
                }
            }
            System.out.println(nums.pop());
            //System.out.println(nums.pop());
        }
    }

20.0

## 调整数组大小 ##

private void resize(int max){
        Object[] objs = new Object[max] ;
        for(int i =0 ;i<exsited.length ;i++){
            objs[i] = exsited[i];
        }
        exsited = objs ;
    }

## 对象的游离 ##

从stack的源码得知：

class Stack<E> extends Vector<E> public synchronized void addElement(E obj) { 
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }

对象的管理实际是用一个下标和一个数组定义的，如果stack超出了设定的大小(初始为10)则进行扩容，见上。  
但当使用一个pop方法时，被弹出的元素的引用仍然存在于数组中。这个元素实际上就是个孤儿了，没有谁会再访问它，但Java编译器没法知道这一点，除非该引用被覆盖。这种情况（保存一个不需要的对象的引用）成为游离。在这里，避免对象游离很简单，只需将被弹出的数组元素的值设为null即可，这将覆盖无用的引用，并使系统在使用完被弹出的元素后回收它的内存。

public Item pop(){//删除栈顶元素
        Item item = a[--N];
        a[N] = null;//**避免对象游离**
        ...
        return item;
    }

在stack代码中已经实现：

public synchronized E pop() {
            E      obj;
            int     len = size();
            obj = peek();
            removeElementAt(len - 1);
            return obj;
        }
        public synchronized void removeElementAt(int index) {
            modCount++;
            elementCount--;
            elementData[elementCount] = null; /* to let gc do its work */
        }

stack是一种能够实现动态调整数组大小，支持任意数据类型，支持foreach的后进先出(LIFO)的数据结构。

## LinkedBlockingQueue的数据结构 ##

private class Node<E>{
        E e; //任意数据类型
        Node next ;//指向下一引用
    }
    private final ReentrantLock takeLock = new ReentrantLock();
    private final ReentrantLock putLock = new ReentrantLock();

## ArrayList的数据结构 ##

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

## LinkedList的数据结构 ##

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

### 为什么stack&queue&list可以pull一个null对象? ###

在LinkedBlockingQueue中是不可以的，if (e == null) throw new NullPointerException();  
stack和list是可以的。

## offer，add区别： ##

区别：两者都是往队列尾部插入元素，不同的时候，当超出队列界限的时候，add（）方法是抛出异常让你处理，而offer（）方法是直接返回false  
offer还提供了 long timeout 阻塞方法。

<table> 
 <thead> 
  <tr> 
   <th>-</th> 
   <th align="right">抛出异常</th> 
   <th align="center">返回值</th> 
   <th>阻塞</th> 
   <th>超时</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>插入</td> 
   <td align="right">add(e)</td> 
   <td align="center">offer(e)</td> 
   <td>put(e)</td> 
   <td>offer(e, time, unit)</td> 
  </tr> 
  <tr> 
   <td>移除</td> 
   <td align="right">remove()</td> 
   <td align="center">poll()</td> 
   <td>take()</td> 
   <td>poll(time, unit)</td> 
  </tr> 
  <tr> 
   <td>检查</td> 
   <td align="right">element()</td> 
   <td align="center">peek()</td> 
   <td></td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

Deque & Queue  
1.stack堆栈，没有迭代器，支持push()方法。后进先出,top()返回最顶端的元素,pop()剔除最顶元素，后进先出（LIFO）；

2.deque双端队列，支持迭代器，有push\_back()方法，跟vector差不多，比vector多了个pop\_front,push\_front方法；

3.queue队列，先进先出，不支持迭代器。队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素，使用element()或者peek()方法。

public interface Deque<E> extends Queue<E>

一个线性 collection，支持在两端插入和移除元素。

名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。