数组

二次封装属于自己的数组

  1. public class  Array<E> {
  3.     private E[] data;
  4.     private int size; //用于记录数组中元素的数量
  6.     /**
  7.      * 构造函数，传入数组的容量capacity构造Array
  8.      * @param capacity  容量
  9.      */
  10.     public Array(int capacity) {
  11.         data = (E[])new Object[capacity];
  12.         size = 0;
  13.     }
  15.     /**
  16.      * 默认给10个空间
  17.      */
  18.     public Array() {
  19.         this(10);
  20.     }

java泛型类

  • java语言不支持直接new一个泛型数组E[] data = new E[capacity];
  • 实际应该E[] data = (E[])new Object[capacity];
  • 泛型类的申明中Array<Integer> array = new Array<>();不需要在后面再添加Integer

数组的增删改查

  1. ---------------------------------------------------增-------------------------------------------------------    
  2.     /**
  3.      * 往数组后面添加一个元素
  4.      * @param e
  5.      */
  6.      public void addLast(E e){
  8.         //if (data.length == size){
  9.         //    throw new IllegalArgumentException("AddLast failed . Array is full");
  10.         //}
  11.         //
  12.         //data[size] = e;
  13.         //size++;
  14.         add(size,e);
  15.      }
  17.     /**
  18.      * 往数组前面添加一个元素
  19.      * @param e
  20.      */
  21.      public void addFirst(E e){
  22.          add(0,e);
  23.      }
  25.     /**
  26.      * 在index的位置插入e
  27.      * @param index
  28.      * @param e
  29.      */
  30.      public void add(int index,E e){
  32.          if (data.length == size){
  33.              //扩容两倍
  34.              resize(2*data.length);
  36.          }
  38.          if (index < 0 || index>size){
  39.              throw new IllegalArgumentException("Add failed . Require index>0 or index>size");
  41.          }
  43.          for (int i = size-1 ; i>=index ; i--){
  44.              data[i+1] = data[i];
  45.          }
  46.          data[index] = e;
  47.          size++;
  49.      }
  50. ---------------------------------------------------增-------------------------------------------------------    
  53. ---------------------------------------------------查-------------------------------------------------------    
  55.     /**
  56.      * 获取index位置的元素
  57.      * @param index
  58.      * @return
  59.      */
  60.      E get(int index){
  61.          if (index < 0 || index > size){
  62.              throw new IllegalArgumentException("Get failed. Index is Illegal");
  63.          }
  64.          return data[index];
  65.      }
  68.     /**
  69.      * 修改index的索引位置的元素为e
  70.      * @param index
  71.      * @param e
  72.      */
  73.      E set(int index,E e){
  74.          if (index < 0 || index > size){
  75.              throw new IllegalArgumentException("Set failed. Index is Illegal");
  76.          }
  77.          return data[index] = e;
  78.      }
  81.     /**
  82.      * 查找数组是否有元素e
  83.      * @param e
  84.      * @return
  85.      */
  86.     public boolean contains(E e){
  87.          for (int i = 0 ; i<size ; i++){
  88.              if (data[i].equals(e)){
  89.                  return true;
  90.              }
  91.          }
  93.          return false;
  94.      }
  96.     /**
  97.      * 查找数组是否有元素e所在的索引,不存在则返回-1
  98.      * @param e
  99.      * @return
  100.      */
  101.     public int find(E e){
  102.          for (int i = 0 ; i<size ; i++){
  103.              if (data[i].equals(e)){
  104.                  return i;
  105.              }
  106.          }
  108.          return -1;
  109.      }
  110. ---------------------------------------------------查-------------------------------------------------------    
  113. ---------------------------------------------------删-------------------------------------------------------    
  114.     /**
  115.      * 删除指定位置的元素，并返回当前值
  116.      * @param index
  117.      * @return
  118.      */
  119.     public E remove(int index){
  120.         if (index < 0 || index > size){
  121.             throw new IllegalArgumentException("Remove failed. Index is Illegal");
  122.         }
  124.         E ret = data[index];
  125.         for (int i = index+1 ; i<size ; i++){
  126.             data[i-1] = data[i];
  127.         }
  128.         size--;
  130.         //如果数元素个数是当前数组大小的四分之一（原因是复杂度震荡），则当前数组容量也减半
  131.         if (size == data.length/4  &&  data.length/2 !=0){
  132.             resize(data.length/2);
  133.         }
  135.         return ret;
  138.     }
  140.     /**
  141.      * 删除第一个
  142.      * @return
  143.      */
  144.     public E removeFirst(){
  145.         return remove(0);
  146.     }
  148.     /**
  149.      * 删除最后一个
  150.      * @return
  151.      */
  152.     public E removeLast(){
  153.         return remove(size-1);
  154.     }
  156.     /**
  157.      * 检验数组中有没有e，如果存在就删除他
  158.      *
  159.      * 但只能删除一个，因为元素会重复
  160.      *
  161.      */
  162.     public void removeElement(E e){
  163.         int index = find(e);
  164.         if (index != -1){
  165.             remove(index);
  166.         }
  167.     }
  168. ---------------------------------------------------删-------------------------------------------------------

动态数组

  • 简单来说就是要满的时候扩充两倍，只装了一半的时候缩小两倍
    1.   看一下这个resize函数就行
    2.   /**
    3.    * 如果插入时数组已经满了，那就扩容
    4.    * @param newCapacity
    5.    */
    6.   private void resize(int newCapacity){
    7.       E[] newData = (E[])new Object[newCapacity];
    8.       for (int i = 0; i < size; i++) {
    9.           newData[i] = data[i];
    10.       }
    11.       data = newData;
    12.   }

分析动态数组的复杂度

image.png

复杂度震荡

比如说当前数组的容量是10，当大小要达到10的时候扩容(capacity*2)，此时数组大小是11，然后又减去1，数组大小变为10，此时又要resize，执行capacity/2,这样就执行了两次的resize

  • 由于resize的时间复杂度是O(n),而上述又执行了两次O(n)，所以耗费了更多的时间

  • 解决方案：Lazy

当size == capacity/4 时，才将capacity减半

栈

栈的基本实现

  1. public class ArrayStack<E> implements Stack<E> {
  3.     Array<E> array;
  5.     public ArrayStack(int capacity) {
  6.         array = new Array<>(capacity);
  7.     }
  10.     public ArrayStack() {
  11.         array = new Array<>();
  12.     }
  15.     @Override
  16.     public int getSize() {
  17.         return array.getSize();
  18.     }
  20.     @Override
  21.     public boolean isEmpty() {
  22.         return array.isEmpty();
  23.     }
  25.     @Override
  26.     public void push(E e) {
  27.         array.addLast(e);
  28.     }
  30.     @Override
  31.     public E pop() {
  32.         return array.removeLast();
  33.     }
  35.     @Override
  36.     public E peek() {
  37.         return array.getLast();
  38.     }
  41.     @Override
  42.     public String toString() {
  43.         final StringBuffer sb = new StringBuffer("Queue: ");
  44.         sb.append("front[");
  45.         for (int i = 0; i < array.getSize(); i++) {
  46.             sb.append(array.get(i));
  47.             if (i != array.getSize()-1)
  48.                 sb.append(", ");
  49.         }
  50.         sb.append("] tail");
  51.         return sb.toString();
  52.     }
  54. }

栈的一个应用

  1. /**
  2.  * Valid-Parenttheses
  3.  * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
  4.  * 使用的是java.util包里面的stack
  5.  *
  6.  * @Author Li Cheng
  7.  * @Date 2021/9/17 14:10
  8.  * @Version 1.0
  9.  */
  10. public class Solution {
  12.     public boolean isValid(String s) {
  14.         Stack<Character> stack = new Stack<>();
  15.         for (int i = 0; i < s.length(); i++) {
  17.             char c = s.charAt(i);
  18.             if (c == '(' || c=='[' || c=='{')
  19.                 stack.push(c);
  20.             else {
  21.                 if (stack.isEmpty()){
  22.                     return false;
  23.                 }
  25.                 char topChar = stack.pop();
  26.                 if (c==')' && topChar != '(')
  27.                     return false;
  28.                 if (c==']' && topChar != '[')
  29.                     return false;
  30.                 if (c=='}' && topChar != '{')
  31.                     return false;
  33.             }
  35.         }
  37.          return stack.isEmpty();
  39.     }
  41.     public static void main(String[] args) {
  42.         Solution solution = new Solution();
  43.         System.out.println(solution.isValid("({})"));
  44.         System.out.println(solution.isValid("({}"));
  45.     }
  49. }

队列

队列的实现

2-5 数组队列【一手微信itit11223344】.mp4_20210917_145427507.jpg

数组队列

  • 相对简单，就是用数组实现一个队列，但有点浪费空间，出列之后front就不能往前移了

2-5 数组队列【一手微信itit11223344】.mp4_20210917_150937044.jpg

  1. public class ArrayQueue<E> implements Queue<E> {
  3.     Array<E> array;
  5.     public ArrayQueue(int capacity) {
  6.         array = new Array<>(capacity);
  7.     }
  9.     public ArrayQueue() {
  10.         array = new Array<>(10);
  11.     }
  13.     @Override
  14.     public int getSize() {
  15.         return array.getSize();
  16.     }
  18.     @Override
  19.     public boolean isEmpty() {
  20.         return array.isEmpty();
  21.     }
  23.     @Override
  24.     public void enqueue(E e) {
  25.         array.addLast(e);
  26.     }
  28.     @Override
  29.     public E dequeue(E e) {
  30.         return array.removeFirst();
  31.     }
  33.     @Override
  34.     public E getFront() {
  35.         return array.getFirst();
  36.     }
  38.     @Override
  39.     public String toString() {
  40.         final StringBuffer sb = new StringBuffer("Queue: ");
  41.         sb.append("front[");
  42.         for (int i = 0; i < array.getSize(); i++) {
  43.             sb.append(array.get(i));
  44.             if (i != array.getSize()-1)
  45.                 sb.append(", ");
  46.         }
  47.         sb.append("] tail");
  48.         return sb.toString();
  49.     }
  50. }

循环队列

  • 有点难理解，可以把这个队列想象成一个圆，在不停的循环直到满列
  • 队列为空:front == tail
  • 队列已经满了: (tail + 1)%c == front,c表示的是队列的长度
  • 出队，front在数组队列中是直接+1，但这里是(front+1)%c
  • 入队，tail在数组队列中是直接+1，但这里是(tail+1)%c

  • 扩容 : 要将原队列中的数据从front~tail依次复制给新队列

    2-6 循环队列【一手微信itit11223344】.mp4_20210917_151722888.jpg ```java public class LoopQueue implements Queue {

    private E[] data; private int front,tail; private int size;

    public LoopQueue(int capacity) {

    1.   //因为是泛型，所以要强制类型转换
    2.   data = (E[])new Object[capacity+1];
    3.   front = 0;
    4.   tail = 0;
    5.   size = 0;

    }

    public LoopQueue() {

    1.   this(10);

    }

    public int getCapacity(){

    1.   return data.length-1;

    }

    @Override public int getSize() {

    1.   return size;

    }

    @Override public boolean isEmpty() {

    1.   return front == tail;

    }

    //入队 @Override public void enqueue(E e) {

    1.   //队列满了，就扩容
    2.   if((tail+1)%data.length == front )
    3.       resize(getCapacity()*2);
    5.   data[tail] = e;
    6.   tail = (tail+1) % data.length;
    7.   size++;

    }

    private void resize(int capacity){

    1.   E[] newData = (E[])new Object[capacity+1];
    3.   for (int i = 0; i < size; i++) {
    4.       newData[i] = data[(i+front) % data.length];
    5.   }
    6.   data = newData;
    7.   front = 0;
    8.   tail = size;

    }

  1. //出队
  2. @Override
  3. public E dequeue(E e) {
  4.     if (isEmpty())
  5.         throw new IllegalArgumentException("Cannot dequeue from an empty queue");
  6.     E ret = data[front];
  7.     data[front] = null;
  8.     front = (front+1)%data.length;
  9.     size--;
  11.     //如果只剩下四分之一就缩小容量
  12.     if (size == getCapacity()/4 && getCapacity()/2 !=0){
  13.         resize(getCapacity()/2);
  14.     }
  16.     return ret;
  18. }
  20. @Override
  21. public E getFront() {
  22.     return data[front];
  23. }
  25. @Override
  26. public String  toString() {
  28.     StringBuilder res = new StringBuilder();
  29.     res.append(String.format("Queue: size = %d , capacity = %d\n",size,getCapacity()));
  30.     res.append("front [");
  31.     for (int i=front ; i != tail ; i = (i+1)%data.length){
  32.         res.append(data[i]);
  33.         if ((i+1)%data.length != tail){
  34.             res.append(",");
  35.         }
  36.     }
  37.     res.append("] tail");
  39.     return res.toString();
  40. }

}

  2. <a name="tFs8i"></a>
  3. # 练习题
  4. <a name="G8mpb"></a>
  5. ## 不浪费一个空间的循环队列
  6. ```java
  7. /**
  8.  * 不浪费一个空间的循环队列
  9.  *
  10.  * @Author Li Cheng
  11.  * @Date 2021/9/18 13:26
  12.  * @Version 1.0
  13.  */
  14. public class LoopQueueNoWaste<E> implements Queue<E>{
  16.     private E[] data;
  17.     private int front,tail;
  18.     private int size;
  20.     public LoopQueueNoWaste(int capacity){
  21.         data = (E[]) new Object[capacity];
  22.         front = 0;
  23.         tail=0;
  24.         size=0;
  25.     }
  27.     public LoopQueueNoWaste() {
  28.         this(10);
  29.     }
  31.     public int getCapacity(){
  32.         return data.length;
  33.     }
  36.     @Override
  37.     public int getSize() {
  38.         return size;
  39.     }
  41.     @Override
  42.     public boolean isEmpty() {
  43.         return front == tail;
  44.     }
  46.     /**
  47.      * 入队
  48.      * @param o
  49.      */
  50.     @Override
  51.     public void enqueue(E o) {
  52.         //如果满了就扩容
  53.         if (size == getCapacity()){
  54.             resize(data.length*2);
  55.         }
  57.         data[tail] = o;
  58.         tail = (tail+1)% data.length;
  59.         size++;
  62.     }
  64.     //扩容
  65.     public void resize(int capacity){
  66.         E[] newData = (E[]) new Object[capacity];
  68.         for (int i = 0; i < size; i++) {
  69.             newData[i] = data[(i+front)% data.length];
  70.         }
  71.         data = newData;
  72.         front = 0;
  73.         tail = size;
  76.     }
  79.     /**
  80.      * 出队
  81.      * @param
  82.      * @return
  83.      */
  84.     @Override
  85.     public E dequeue() {
  86.         if (isEmpty())
  87.             throw new IllegalArgumentException("Cannot dequeue from an empty queue");
  89.         E ret = data[front];
  91.         data[front] = null;
  92.         front = (front+1)% data.length;
  93.         size--;
  95.         //如果只剩下四分之一就缩小容量
  96.         if (size == getCapacity()/4 && size/2!=0){
  97.             resize(getCapacity()/2);
  98.         }
  100.         return ret;
  101.     }
  103.     @Override
  104.     public E getFront() {
  105.         return data[front];
  106.     }
  108.     @Override
  109.     public String  toString() {
  111.         StringBuilder res = new StringBuilder();
  112.         res.append(String.format("Queue: size = %d , capacity = %d\n",size,getCapacity()));
  113.         res.append("front [");
  114.         for (int i=front ; i != tail ; i = (i+1)%data.length){
  115.             res.append(data[i]);
  116.             if ((i+1)%data.length != tail){
  117.                 res.append(",");
  118.             }
  119.         }
  120.         res.append("] tail");
  122.         return res.toString();
  123.     }
  126. }

没有size成员变量的循环队列

  1. /**
  2.  * 浪费一个空间但是没有size
  3.  *
  4.  * @Author Li Cheng
  5.  * @Date 2021/9/18 13:55
  6.  * @Version 1.0
  7.  */
  8. public class LoopQueueNoSize<E> implements Queue<E>{
  10.     private E[] data;
  11.     private int front,tail;
  14.     public LoopQueueNoSize(int capacity){
  15.         data = (E[]) new Object[capacity+1];
  16.         front = 0;
  17.         tail=0;
  18.     }
  21.     public LoopQueueNoSize() {
  23.         this(10);
  25.     }
  28.     public int getCapacity(){
  29.         return data.length-1;
  30.     }
  33.     @Override
  34.     public int getSize() {
  35.         int size = (tail + (data.length-front))%data.length;
  36.         return size;
  37.     }
  39.     @Override
  40.     public boolean isEmpty() {
  41.         return tail == front;
  42.     }
  44.     @Override
  45.     public void enqueue(E e) {
  46.         //队列满了，就扩容
  47.         if ((tail+1)% data.length == front)
  48.             resize(getCapacity()*2);
  50.         data[tail] = e;
  51.         tail = (tail+1) % data.length;
  53.     }
  56.     public void resize(int capacity){
  57.         E[] newData = (E[]) new Object[capacity+1];
  58.         for (int i = 0; i < getSize(); i++) {
  59.             newData[i] = data[(i+front) % data.length];
  60.         }
  61.         data = newData;
  62.         tail = getSize();
  63.         front = 0;
  64.     }
  67.     @Override
  68.     public E dequeue() {
  69.         //队列为空就报错
  70.         if (isEmpty())
  71.             throw new IllegalArgumentException("Cannot dequeue an empty queue");
  72.         E ret = data[front];
  73.         data[front] = null;
  74.         front = (front+1)% data.length;
  76.         if (getSize() == getCapacity()/4 && getCapacity()/2 != 0){
  77.             resize(getCapacity()/2);
  78.         }
  80.         return ret;
  81.     }
  83.     @Override
  84.     public E getFront() {
  85.         return data[front];
  86.     }
  88.     @Override
  89.     public String  toString() {
  91.         StringBuilder res = new StringBuilder();
  92.         res.append(String.format("Queue: size = %d , capacity = %d\n",getSize(),getCapacity()));
  93.         res.append("front [");
  94.         for (int i=front ; i != tail ; i = (i+1)%data.length){
  95.             res.append(data[i]);
  96.             if ((i+1)%data.length != tail){
  97.                 res.append(",");
  98.             }
  99.         }
  100.         res.append("] tail");
  102.         return res.toString();
  103.     }
  104. }

实现双端队列

  • 双端队列图示

微信图片_20210921141918.jpg

  1. /**
  2.  * @Author Li Cheng
  3.  * @Date 2021/9/18 18:14
  4.  * @Version 1.0
  5.  */
  6. public class TwoHeadLoopQueue<E>{
  8.     private E[] data;
  9.     private int front,tail;
  10.     private int size;
  12.     public TwoHeadLoopQueue(int capacity) {
  14.         data = (E[]) new Object[capacity];
  15.         front = 0;
  16.         tail = 0;
  17.         size = 0;
  18.     }
  19.     public TwoHeadLoopQueue() {
  20.         this(10);
  21.     }
  25.     public boolean isEmpty() {
  26.         return size == 0;
  27.     }
  29.     public boolean isFull(){
  30.         return size == getCapacity();
  31.     }
  33.     public int getCapacity(){
  34.         return data.length;
  35.     }
  38.     public void addLast(E e){
  39.         if (isFull()){
  40.             resize(getCapacity()*2);
  41.         }
  42.         data[tail] = e;
  43.         tail = (tail+1)% data.length;
  44.         size++;
  45.     }
  48.     public void addFront(E e){
  49.         if (isFull()){
  50.             resize(getCapacity()*2);
  51.         }
  52.         front = front==0 ? data.length - 1 : front-1;
  53.         data[front] = e;
  54.         size++;
  55.     }
  58.     public E removeLast(){
  59.         if (isEmpty()){
  60.             throw new IllegalArgumentException("Cannot dequeue an empty queue");
  61.         }
  62.         E ret = data[tail];
  63.         tail = tail == 0 ? data.length -1 : tail-1 ;
  64.         data[tail] = null;
  65.         size--;
  66.         if (size == getCapacity()/4 && getCapacity()/2 != 0){
  67.             resize(getCapacity()/2);
  68.         }
  69.         return ret;
  70.     }
  72.     public E removeFront(){
  73.         if (isEmpty()){
  74.             throw new IllegalArgumentException("Cannot dequeue an empty queue");
  75.         }
  76.         E ret = data[front];
  77.         data[front] = null;
  78.         front = (front+1)% data.length;
  79.         size--;
  80.         if (size == getCapacity()/4 && getCapacity()/2 != 0){
  81.             resize(getCapacity()/2);
  82.         }
  83.         return ret;
  84.     }
  86.     public E getFront(){
  87.         if ((isEmpty())){
  88.             throw new IllegalArgumentException("Queue is Empty");
  89.         }
  90.         return data[front];
  91.     }
  94.     public E getLast(){
  95.         if ((isEmpty())){
  96.             throw new IllegalArgumentException("Queue is Empty");
  97.         }
  99.         //因为tail指向的是队尾元素的下一个位置，所以需要计算真正的位置
  100.         return data[ tail==0? data.length -1 : tail-1];
  101.     }
  103.     private void resize(int capacity){
  104.         E[] newData = (E[]) new Object[capacity];
  105.         for (int i = 0; i < size; i++) {
  106.             newData[i] = data[(i+front)% data.length];
  107.         }
  108.         data = newData;
  109.         tail = size;
  110.         front = 0;
  111.     }
  113.     @Override
  114.     public String  toString() {
  116.         StringBuilder res = new StringBuilder();
  117.         res.append(String.format("Queue: size = %d , capacity = %d\n",size,getCapacity()));
  118.         res.append("front [");
  119.         for (int i=front ; i != tail ; i = (i+1)%data.length){
  120.             res.append(data[i]);
  121.             if ((i+1)%data.length != tail){
  122.                 res.append(",");
  123.             }
  124.         }
  125.         res.append("] tail");
  127.         return res.toString();
  128.     }
  132. }

用栈实现队列

  1. import java.util.LinkedList;
  2. import java.util.Queue;
  4. /**
  5.  *
  6.  * 用队列实现栈
  7.  * @Author Li Cheng
  8.  * @Date 2021/9/20 18:26
  9.  * @Version 1.0
  10.  */
  11. public class StackForQueue {
  13.     private Queue<Integer> q;
  14.     private int top; //  用来追踪记录栈顶元素将原先的复杂度O(n)变为O(1)
  16.     public StackForQueue() {
  17.         q = new LinkedList<>();
  18.     }
  20.     public boolean isEmpty(){
  21.         return q.isEmpty();
  22.     }
  24.     public void push(int x){
  25.         q.add(x);
  26.         top = x;
  27.     }
  29.     public int pop(){
  31.         //用q2来存储q队列n个元素之前的n-1个元素
  33.         Queue<Integer> q2 = new LinkedList<>();
  34.         for (int i = 0; i < q.size()-1; i++) {
  35.             //每次从q中取出一个元素，都给top赋值
  36.             //top中存储的就是q中除了队尾元素以外的最后一个元素
  37.             //即最新的栈顶元素
  38.             top =  q.peek();
  39.             q2.add(q.remove());
  41.         }
  42.         int ret = q.remove();
  43.         q = q2;
  45.         return ret;
  46.     }
  48.     public int top(){
  49.         return top;
  50.     }
  53. }

用队列实现栈

  1. import java.util.Stack;
  3. /**
  4.  * @Author Li Cheng
  5.  * @Date 2021/9/20 18:53
  6.  * @Version 1.0
  7.  */
  8. public class MyQueue {
  10.     private Stack<Integer> stack;
  12.     /** Initialize your data structure here. */
  13.     public MyQueue() {
  14.         stack = new Stack<>();
  15.     }
  18.     /** Push element x to the back of queue. */
  19.     public void push(int x) {
  20.         Stack<Integer> stack2 = new Stack<>();
  21.         while (stack.size() > 0){
  22.             stack2.push(stack.pop());
  23.         }
  24.         stack.push(x);
  25.         while (stack2.size() > 0){
  26.             stack.push(stack2.pop());
  27.         }
  28.     }
  30.     /** Removes the element from in front of queue and returns that element. */
  31.     public int pop() {
  32.         return stack.pop();
  33.     }
  35.     /** Get the front element. */
  36.     public int peek() {
  37.         return stack.peek();
  38.     }
  40.     /** Returns whether the queue is empty. */
  41.     public boolean empty() {
  42.         return stack.isEmpty();
  43.     }
  44. }