2021-02-23

利用数组实现栈

package com.edagr.seckilldemo;

/**
 * 利用数组实现栈
 */
public class Stack {
    private final int DEFAULT_SIZE = 10;
    private int top = -1;
    private int capacity;
    private Object[] arr;
    public Stack() {
        arr = new Object[DEFAULT_SIZE];
        this.capacity = DEFAULT_SIZE;
    }

    public Stack(int capacity) {
        arr = new Object[capacity];
        this.capacity = capacity;
    }

    public boolean isFull() {
        return  top == capacity - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean push(Object element) {
        if (isFull()) {
            System.out.println("栈已满!!!");
            return false;
        }
        arr[++top] = element;
        return true;
    }

    public Object pop() {
        if (isEmpty()) {
            System.out.println("队列为空");
            return null;
        }
        return arr[top--];
    }

    public void list() {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }

        System.out.println();
    }

    public static void main(String[] args) {
        Stack stack = new Stack();
        for (int i = 0; i < 30; i++) {
            stack.push(i);
            if (i % 3 == 0 && i != 0) {
                stack.list();
                stack.pop();
                stack.pop();
                stack.list();
            }
        }
    }
}

利用数组实现循环队列

package com.edagr.seckilldemo;

/**
 * 利用数组实现循环队列
 */
public class Queue {
    private final int DEFAULT_SIZE = 10;
    private int size;
    private int front;
    private int rear;
    private Object[] arr;

    Queue(int size) {
        this.size = size;
        arr = new Object[size];
    }

    Queue() {
        this.size = DEFAULT_SIZE;
        arr = new Object[size];
    }


    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % size == front;
    }

    public boolean add(Object element) {
        if(isFull()) {
            System.out.println("队列已满!!!");
            return false;
        }
        arr[rear] = element;
        rear = (rear + 1) % size;
        return true;
    }

    public Object get() {
        if (isEmpty()) {
            System.out.println("队列为空!!!");
            return  null;
        }
        Object element = arr[front];
        front = (front + 1) % size;
        return element;
    }

    public void list() {
        while (!isEmpty()) {
            System.out.print(get() + ",");
        }
        System.out.println();
    }


    public static void main(String[] args) {

        Queue queue = new Queue();
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);
        queue.add(6);
        queue.add(7);
        queue.add(8);
        queue.add(9);

        queue.get();
        queue.get();
        queue.get();

        queue.list();
    }
}

利用数组实现可扩容的队列

package com.edagr.seckilldemo;


import java.util.ArrayList;

/**
 * 利用数组实现自动扩容
 */

interface IQueue<E> {
    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

class QueueAdvance<E> implements IQueue<E> {
    private ArrayList<E> array;

    QueueAdvance(int capacity) {
        array = new ArrayList<E>(capacity);
    }

    QueueAdvance() {
        array = new ArrayList<E>();
    }

    @Override
    public int getSize() {
        return array.size();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public void enqueue(E o) {
        array.add(array.size(), o);
    }

    @Override
    public E dequeue() {
        return array.remove(0);
    }

    @Override
    public E getFront() {
        return array.get(0);
    }

    @Override
    public String toString() {
        final String[] str = {""};
        array.forEach((e) -> {
            str[0] = str[0] + e + ",";
        });

        return str[0];
    }

    public static void main(String[] args) {
        QueueAdvance<Integer> queue = new QueueAdvance<Integer>();

        //包装类和其对应的基本数据类型可以自动转换
        for (int i = 0; i < 40; i++) {
            queue.enqueue(i);//入队
            System.out.println(queue);

            if (i%3==2) {//每三个元素出队一次
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}