数据结构——栈与队列（Java实现）

什么是栈与队列？

• 栈是一种特殊的线性表结构，数据在栈中，只能从栈顶进入，也只能从栈顶弹出，具有先进后出的特点。
• 队列也是一种特殊的线性表结构，数据在队列中，只能从队列的最后存入队列，数据移出只能从队列的最前面取出，具有先进先出，后进后出的特点。 【循环队列】循环队列是一种特殊的队列，在满足普通队列的基础上，解决了普通队列因为取出数据而造成空间浪费的情况，它维护了队列的队首和队尾索引，使索引在越界时能够从新返回初始化。

栈的实现（Java）

/**
 *     数据栈，Java实现
 *         数据栈是一种特殊的线性表结构，
 *         所有数据只能从栈顶插入，也只能从栈顶取出
 * @author hrp
 * 2020年2月14日 上午11:33:59
 */
public class MyStack {
    private int[] arr;
    private int maxSize;
    private int top;
    
    /**
     *     指定栈的大小，初始化栈
     *         maxSize：栈的最大容量
     *         top：栈顶数据的索引
     * @param size
     */
    public MyStack(int size) {
        this.maxSize = size;
        this.arr = new int[maxSize];
        this.top = -1;
    }
    
    /**
     *     压栈，将数据从栈顶压入栈中，维护top索引
     * @param value
     */
    public void push(int value) {
        arr[++top] = value;
    }
    
    /**
     *     弹出，将数据中栈顶弹出，维护top索引
     * @return
     */
    public int pop() {
        return arr[top--];
    }
    
    /**
     *     判断栈是否为空，直接比较top==-1
     * @return
     */
    public boolean isEmpty() {
        return top == -1;
    }
    
    /**
     *     判断栈是否满了，直接比较top==(maxSize-1)
     * @return
     */
    public boolean isFull() {
        return top == maxSize - 1;
    }
    
    /**
     *     打印栈，循环次数为top+1
     */
    public void printStack() {
        for(int i = 0; i <= top; i++) {
            System.out.print(arr[i]+"\t");
        }
        System.out.println();
    }    
}

循环队列的实现（Java）

/**
 *     循环队列，Java实现
 *         队列是一种特殊的线性表结构，
 *         它只允许在表的前端进行删除操作，在表的后端进行添加操作 
 * @author hrp
 * 2020年2月14日 上午10:46:57
 */
public class MyQueue {
    
    private int[] arr;
    private int maxSize;
    private int elems;
    private int font;
    private int end;
    
    /**
     *     指定队列的大小，初始化队列
     * @param size
     */
    public MyQueue(int size) {
        this.maxSize = size;
        this.arr = new int[maxSize];
        this.elems = 0;
        this.font = 0;
        this.end = -1;
    }
    
    /**
     *     插入操作，如果此时end索引已经到达最后了，将索引维护为-1，在执行插入操作
     *         同时判断队列是否满了，如果队列未满，则elems++，如果满了，则覆盖最前面的值，font++
     * @param value
     */
    public void insert(int value) {
        if(end == maxSize - 1) {
            end = -1;
        }
        arr[++end] = value;
        if(elems < maxSize) {
            elems++;
        }else {
            font++;
        }
    }
    
    /**
     *     移除操作，先判断font是否已经超出了数组索引范围，是则重新维护索引
     *         首先队列长度elems--，并将font索引是指返回，同时维护索引位置
     * @return
     */
    public int remove() {
        if(font == maxSize) {
            font = 0;
        }
        elems--;
        return arr[font++];
    }
    
    /**
     *     判断队列是否为空，直接比较队列的elems属性是否为0
     * @return
     */
    public boolean isEmpty() {
        return this.elems == 0;
    }
    
    /**
     *     判断队列是否满了，直接比较队列的elems属性和MaxSize的值是否相等
     * @return
     */
    public boolean isFull() {
        return this.elems == maxSize;
    }
    
    /**
     *     打印队列，已知循环次数为队列长度，打印次数为elems
     *         注意：不应该直接使用font作为数组索引进行打印，
     *         因为在++过程中会破坏数组font索引的正确性
     */
    public void printQueue() {
        int index = font;
        for(int i = 0; i < elems; i++) {
            System.out.print(arr[index++]+"\t");
            if(index == maxSize) {
                index = 0;
            }
        }
        System.out.println();
    }
}