数据结构-栈队列(数组实现栈、队列、循环队列)

栈和队列

栈

1栈描述

先进后出底层是一个数组

2类的概念

永远记住
类是由类的属性和方法组成的，在类中写其它的就是错误
3 栈

/**
 * @Auther: liuhaidong
 * Data: 2019/9/15 0015、17:14
 * Description:
 * @version: 1.0
 */
public class MyStack {
    //底层是一个数组
    private long[] arr;
    private int top;

    /*
     * @Author liuhaidong
     * @Description 默认的构造方法
     * @Date 17:19 2019/9/15 0015
     **/
    public MyStack(){
        arr = new long[10];
        top = -1;
    }
    /*
     * @Author liuhaidong
     * @Description 带参数的构造方法
     * @Date 17:20 2019/9/15 0015
     **/
    public MyStack(int maxsize){
        arr = new long[maxsize];
        top = -1;
    }

    /*
     * @Author liuhaidong
     * @Description 添加数据
     * @Date 17:21 2019/9/15 0015
     **/
    public void push(int value){
        arr[++top] =value;
    }

    /*
     * @Author liuhaidong
     * @Description 移除数据
     * @Date 17:23 2019/9/15 0015
     **/
    public long pop(){
        return arr[top--];
    }
    
    /*
     * @Author liuhaidong 
     * @Description 查看数据
     * @Date 17:24 2019/9/15 0015
     **/
    public long peek(){
        return arr[top];
    }
    
    /*
     * @Author liuhaidong 
     * @Description 判断是否为空
     * @Date 17:24 2019/9/15 0015
     **/
    public boolean isEmpty(){
        return top == -1;
    }

    /*
     * @Author liuhaidong
     * @Description 判断是否满了
     * @Date 17:26 2019/9/15 0015
     **/
    public boolean isFull(){
        return top == arr.length -1;
    }
}

4 主函数

/**
 * @Auther: liuhaidong
 * Data: 2019/9/15 0015、17:32
 * Description:
 * @version: 1.0
 */
public class testMyStack {
    public static void main(String[] args) {
        MyStack myStack = new MyStack(4);
        myStack.push(23);
        myStack.push(65);
        myStack.push(11);
        myStack.push(13);
        System.out.println(myStack.isEmpty());
        System.out.println(myStack.isFull());
        System.out.println(myStack.peek());
        while (!myStack.isEmpty()){
            System.out.println(myStack.pop() + ",");
        }
        System.out.println(myStack.isEmpty());
        System.out.println(myStack.isFull());
    }
}

上述方式不行，如果一直push会报bug
所以需要改进

public class MyStack {
   
    private Integer[] arr;
    private Integer size;
    public MyStack(){
   
        arr = new Integer[10];
        size = 10;
    }
    public MyStack (int initSize) {
   
        if (initSize < 0) {
   
            throw new IllegalArgumentException("The init size is less than 0");
        }
        arr = new Integer[initSize];
        size = 0;
    }

    public Integer peek() {
   
        if (size == 0) {
   
            return null;
        }
        return arr[size - 1];
    }

    public void push(int obj) {
   
        if (size == arr.length) {
   
            throw new ArrayIndexOutOfBoundsException("The queue is full");
        }
        arr[size++] = obj;
    }

    public Integer pop() {
   
        if (size == 0) {
   
            throw new ArrayIndexOutOfBoundsException("The queue is empty");
        }
        return arr[--size];
    }

}

继续对上述代码进行改进，对数组能进行扩容，对类型能进行自动化

public class MyStack1<E> {
   
    private Object[] stack;
    private int size;

    public MyStack1() {
   
        stack = new Object[10];
        //初始长度为10
    }
    public MyStack1(int initSize) {
   
        stack = new Object[initSize];
        //初始长度为10
    }
    /** * 判断栈是否为空 * */
    public boolean isEmpty() {
   
        return size == 0;
    }
    /** * 返回栈顶的一个元素，但是不进行出栈操作 * */
    public E peek() {
   
        if(isEmpty()) {
   
            return null;
        }
        return (E)stack[size -1];
        //返回栈顶元素
    }
    /** * 弹出 * */
    public E pop() {
   
        E e = peek();
        //取得栈顶数据
        if(size > 0) {
   
            //检查栈中是否有数据
            stack[size - 1] = null;
            //将出栈后的位置置为空
            size--;
        }
        //将栈中元素个数减一
        return e;
    }
    /** * 压入 * */
    public E push(E item) {
   
        ensureCapacity(size + 1);
        stack[size++] = item;
        return item;

    }
    /** * 当栈满的时候，对栈进行扩容 * */
    private void ensureCapacity(int size) {
   
        int len = stack.length;
        if(size > len) {
   
            //数组已满
            int newLen = 10;
            //每次数组扩充的容量
            stack = Arrays.copyOf(stack, newLen);
        }
    }
    /** * 打印出栈中所有的数据 * */
    public void printStack() {
   
        System.out.println("开始进行出栈：");
        while(size > 0) {
   
            System.out.println("出栈：" + pop());
        }
        System.out.println("出栈操作结束！");

    }
}

以上代码显然还是有问题，扩容不对

public class testMyStack {
   
    public static void main(String[] args) {
   
       MyStack1<String> myStack = new MyStack1<String>(4);
        myStack.push("23");
        myStack.push("23");
        myStack.push("23");
        myStack.push("23");
        myStack.push("23");
        myStack.push("23");
    }
}

队列

简单队列

/**
 * @Auther: liuhaidong
 * Data: 2019/9/15 0015、17:40
 * Description:
 * @version: 1.0
 */
public class MyQueue {
    //底层使用数组
    private long[] arr;
    //有效数据的大小
    private int elements;
    //队头
    private int front;
    //队尾
    private int end;

    /*
     * @Author liuhaidong
     * @Description 默认的构造方法
     * @Date 17:41 2019/9/15 0015
     **/
    public MyQueue(){
        arr = new long[10];
        elements =0;
        front =0;
        end = -1;
    }

    /*
     * @Author liuhaidong
     * @Description 带参数的构造方法，参数为数组的大小
     * @Date 17:43 2019/9/15 0015
     **/
    public MyQueue(int maxsize){
        arr = new long[maxsize];
        elements =0;
        front =0;
        end = -1;
    }

    /*
     * @Author liuhaidong
     * @Description 添加数据，从队尾插入
     * @Date 17:43 2019/9/15 0015
     **/
    public void insert(long value){
        arr[++end] = value;
        elements++;
    }


    /*
     * @Author liuhaidong
     * @Description 删除数据，从队头删除
     * @Date 17:43 2019/9/15 0015
     **/
    public long remove(){
        elements--;
        return arr[front++];
    }

    /*
     * @Author liuhaidong
     * @Description 查看数据，从队头查看
     * @Date 17:52 2019/9/15 0015
     **/
    public long peek(){
        return arr[front];
    }

    /*
     * @Author liuhaidong
     * @Description 判断是否为空
     * @Date 17:53 2019/9/15 0015
     **/
    public boolean isEmpty(){
        return elements ==0;
    }
    
    /*
     * @Author liuhaidong 
     * @Description 判断是否满了
     * @Date 17:54 2019/9/15 0015
     **/
    public boolean isFull(){
        return elements == arr.length;
    }

}

主函数

/**
 * @Auther: liuhaidong
 * Data: 2019/9/15 0015、17:56
 * Description:
 * @version: 1.0
 */
public class testMyQueue {
    public static void main(String[] args) {
        MyQueue mq = new MyQueue(4);
        mq.insert(23);
        mq.insert(1);
        mq.insert(2);
        mq.insert(18);
        System.out.println(mq.isFull());
        System.out.println(mq.isEmpty());
        System.out.println(mq.peek());
        while (!mq.isEmpty()){
            System.out.println(mq.remove()+" ");
        }

        //以下会报错
        mq.insert(23);
    }
}

这里的重点是从队尾插入，从对头删除。
数组越界
ArrayIndexOutOfBoundsException

public class ArrayIndexOutOf BoundsExceptionextends IndexOutOfBoundsException用非法索引访问数组时抛出的异常。如果索引为负或大于等于数组大小，则该索引为非法索引。

循环队列

/**
 * @Auther: liuhaidong
 * Data: 2019/9/15 0015、18:31
 * Description:
 * @version: 1.0
 */
public class MyCycleQueue {

    //底层使用数组
    private long[] arr;
    //有效数据的大小
    private int elements;
    //队头
    private int front;
    //队尾
    private int end;

    /*
     * @Author liuhaidong
     * @Description 默认的构造方法
     * @Date 17:41 2019/9/15 0015
     **/
    public MyCycleQueue(){
        arr = new long[10];
        elements =0;
        front =0;
        end = -1;
    }

    /*
     * @Author liuhaidong
     * @Description 带参数的构造方法，参数为数组的大小
     * @Date 17:43 2019/9/15 0015
     **/
    public MyCycleQueue(int maxsize){
        arr = new long[maxsize];
        elements =0;
        front =0;
        end = -1;
    }

    /*
     * @Author liuhaidong
     * @Description 循环队列，解决插入bug的问题
     * @Date 18:27 2019/9/15 0015
     **/
    public void insert(long value){
        if(end == arr.length -1){
            end = -1;
        }
        arr[++end] = value;
        elements++;
    }


    /*
     * @Author liuhaidong
     * @Description 删除数据，从队头删除
     * @Date 17:43 2019/9/15 0015
     **/
    public long remove(){
        long value = arr[front++];
        if(front == arr.length){
            front =0;
        }
        elements--;
        return value;
    }

    /*
     * @Author liuhaidong
     * @Description 查看数据，从队头查看
     * @Date 17:52 2019/9/15 0015
     **/
    public long peek(){
        return arr[front];
    }

    /*
     * @Author liuhaidong
     * @Description 判断是否为空
     * @Date 17:53 2019/9/15 0015
     **/
    public boolean isEmpty(){
        return elements ==0;
    }

    /*
     * @Author liuhaidong
     * @Description 判断是否满了
     * @Date 17:54 2019/9/15 0015
     **/
    public boolean isFull(){
        return elements == arr.length;
    }
}

主函数

/**
 * @Auther: liuhaidong
 * Data: 2019/9/15 0015、18:33
 * Description:
 * @version: 1.0
 */
public class CycleQueueTest {
    public static void main(String[] args) {
        MyCycleQueue  mq = new MyCycleQueue(4);
        mq.insert(23);
        mq.insert(1);
        mq.insert(2);
        mq.insert(18);
        System.out.println(mq.isFull());
        System.out.println(mq.isEmpty());
        System.out.println(mq.peek());
        while (!mq.isEmpty()){
            System.out.println(mq.remove()+" ");
        }

        mq.insert(23);
        mq.insert(1);
        mq.insert(2);
        mq.insert(18);
        while (!mq.isEmpty()){
            System.out.println(mq.remove()+" ");
        }
    }
}

这样就不会有问题了

数据结构-栈 队列(数组实现栈、队列、循环队列)

栈和队列

栈

队列

数据结构-栈队列(数组实现栈、队列、循环队列)