[数据结构与算法]Java学习 day27_stack&queue

Java自带的LinkedList提供泛型，底层是双向链表实现的

栈：是一个操作受限制的线性表，只能在一端进行删除或删除数据 FIFO
栈的实现：用链表或者数组实现一个集合类，这个集合类代表的数据结构是栈
如果一个集合类底层是数组，必定面临两个问题，数组初始化和长度

题外话：
分布式的原理：服务分布在不同的地方，这些分布在不同位置的服务又可以相互关联某些途径

实现栈

用链表实现栈stack

package com.cskaoyan.www.day4.stack;

/**
* 实现集合类
* 模拟的数据结构是栈
* 底层结构是链表: 单链表
*/
public class MyLinkedStack<T> {

   private Node top;// 保存栈的栈顶
   private int size;// 这个栈中保存了多少个元素


   // 对于栈我们应该提供的三个方法:  入栈, 出栈, 查看栈顶元素
   //                              push    pop    peek

   /**
    * 给栈实现一个添加方法
    * @param value : 要添加的元素
    * @return : 添加是否成功
    */
   public boolean push(T value){
       top = new Node(value, top);
       size++;
       return true;
   }

   /**
    * 栈的删除操作
    * @return : 被删除的栈顶元素
    */
   public T pop(){
       // 判断链表为空
       if (isEmpty()) throw new RuntimeException("stack is empty");

       T value = top.value;// 保存原本栈顶值
       top = top.next; // 栈顶向栈底移动一个元素
       size--;

       return value;
   }

   /**
    * 栈的查看栈顶元素的方法
    * @return:  栈顶元素
    */
   public T peek(){
       // 判断链表为空
       if (isEmpty()) throw new RuntimeException("stack is empty");

       return top.value;
   }

   public  boolean isEmpty(){
       return size == 0;
   }
   public int size(){
       return size;
   }

   class Node{
       T value;
       Node next;
       public Node(T value, Node next) {
           this.value = value;
           this.next = next;
       }
   }
}

用数组实现stack

package com.cskaoyan.www.day4.stack;

import java.util.HashMap;

/**
 * 实现集合类
 * 模拟的数据结构是栈
 * 底层结构是数组
 */
public class MyArrayStack<T> {
    private final int MAX_CAPACITY = Integer.MAX_VALUE - 8;
    private final  int INIT_CAPACITY = 10;// 数组的默认容量

    private Object[] objs;// 这个集合类底层持有的数组
    private int size;// 这个集合类存储的元素数量

    public MyArrayStack(){
         objs = new Object[INIT_CAPACITY];
    }
    public MyArrayStack(int initCapacity){
        if (initCapacity < 1 || initCapacity > MAX_CAPACITY)throw new IllegalArgumentException("parame is Illegal");
        objs = new Object[initCapacity];
    }

    public boolean push(T value){
        // 在添加的时候, 要先判断底层数组是否满了
        if (size == objs.length){
            // 数组满了--> 扩容
            int newLen  = getLen();// 获取扩容的长度
            grow(newLen);// 根据要扩容的长度, 扩容这个数组
        }

        // 到这一步, 意味着, 数组一定有位置可供添加数据

        // 添加元素, 栈顶在size-1位置,   栈底在下标为0的位置
        objs[size] = value;
        size++;

        return true;
    }
    // 根据一个新长度扩容底层数组
    private void grow(int newLen) {
        Object[] newObjs = new Object[newLen];

        // 把旧数组的数据转移到新数组
        for (int i = 0; i < objs.length; i++) {
            newObjs[i] = objs[i];
        }

        objs = newObjs;
    }
    // 获取一个数组的新长度
    private int getLen() {
        // 旧数组长度
        int oldLen = objs.length;

        // 新长度扩为原来的二倍
        int newLen = oldLen * 2;

        if (newLen >= MAX_CAPACITY || newLen < 0){
            newLen = MAX_CAPACITY;
        }

        if (newLen == oldLen)throw new RuntimeException("stack can not add");

        return newLen;
    }

    // 栈的出栈方法
    public T pop(){
        if (isEmpty()) throw new RuntimeException("stack is empty");

        T value = (T)objs[size - 1];
        size--;

        return value;
    }

    // 栈的查看栈顶元素方法
    public  T peek(){
        if (isEmpty()) throw new RuntimeException("stack is empty");

        return  (T) objs[size - 1];
    }

    public boolean isEmpty(){
        return size == 0;
    }
    public int  size(){
        return size;
    }

}

队列

用链表实现queue

package com.cskaoyan.www.day4.queue;

/**
 * 实现一个集合类
 * 模拟的数据结构是队列
 * 底层结构是: 单链表
 */
public class MyLinkedQueue<T> {

    private Node head;// 队列的队头
    private Node end;// 队列的队尾
    private int size;// 队列存储了多少元素

    // 作为队列, 它应该存在哪些操作?
    // 入队列-> 添加    出队列 -> 删除     查看队头元素 --> 查找
    //  offer            poll                   peek

    public boolean offer(T value){

        if (isEmpty()){
            // 原队列为空, 这个新添加的元素, 既是队头又是队尾
            head = new Node(value, null );
            end = head;
            size++;
            return true;
        }else {
            // 原队列不空, 这个新添加的元素, 放在队尾
            Node newNode = new Node(value, null);
            end.next = newNode;
            end = newNode;
            size++;
            return true;
        }
    }

    public T poll(){
        if (isEmpty())throw new RuntimeException("queue is empty");

        // 链表不空
        T value = head.value;

        if (size == 1){
            // 队列中只剩一个元素
            head = null;
            end = null;
        }else {
            // 队列中多于一个元素
            head = head.next;
        }
        size--;
       return value;
    }

    public T peek() {
        if (isEmpty()) throw new RuntimeException("queue is empty");
        return head.value;
    }


    public boolean isEmpty(){
        return size == 0;
    }
    public int size(){
        return size;
    }

    class Node{
        T value;
        Node next;
        public Node(T value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

用数组实现queue

package com.cskaoyan.www.day4.queue;

public class MyArrayQueue<T> {

    private final  int MAX_CAPACITY = Integer.MAX_VALUE - 8;
    private final  int INIT_CAPACITY = 10;

    private Object[] arr;// 底层循环数组
    private int size;// 队列中存储了多少元素
    private int head;// 队头的下标
    private int end;// 队尾的下标

    public MyArrayQueue() {
       this.arr = new Object[INIT_CAPACITY];
    }
    public MyArrayQueue(int initCapacity) {
        if (initCapacity < 1 || initCapacity > MAX_CAPACITY)throw new IllegalArgumentException("initCapacity is Illegal");
        this.arr = new Object[initCapacity];
    }

    // offer  poll peek

    public boolean offer(T value){
        if (size == arr.length){
            // 底层数组满了, 需要扩容
            int newLen = getLen();
            grow(newLen);
        }

        // 走到这, 意味着数组中有位置可以添加
        if (size == 0){
            // 原本数组没有存储元素
            arr[head] = value;
            end = head;
        }else {
            // 原本数组已经存储元素
            end = (end + 1) % arr.length;
            arr[end] = value;
        }

        size++;
        return true;
    }
    private void grow(int newLen) {
        Object[] newArr = new Object[newLen];

        // 把旧数组的数组转移到新数组
        for (int i = 0; i < arr.length; i++) {
            int index = (head + i) % arr.length;
            newArr[i] = arr[index];
        }

        // 重新定义指向
        arr = newArr;
        head = 0;
        end = size -1;
    }
    private int getLen() {
        // 旧数组长度
        int oldLen = arr.length;

        // 新长度扩为原来的二倍
        int newLen = oldLen * 2;

        if (newLen >= MAX_CAPACITY || newLen < 0){
            newLen = MAX_CAPACITY;
        }

        if (newLen == oldLen)throw new RuntimeException("stack can not add");

        return newLen;
    }

    public T poll(){
        if (isEmpty()) throw new  RuntimeException("queue is empty");

        T vlaue  = (T)arr[head];

        if (size == 1){// 原本队列中只剩一个元素
            head = 0;
            end = 0;
        }else {
            // 队列中有多个元素
            head = (head + 1) % arr.length;
        }
        size--;
        return vlaue;
    }


    public T peek() {
        if (isEmpty()) throw new RuntimeException("queue is empty");

        return (T)arr[head];
    }

        public boolean isEmpty(){
        return size == 0;
    }

}