栈

基本概念

栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线性表。栈是一种数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆。取走时，只能从上面一件一件取。读和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一端称栈底。插入一般称为进栈，删除则称为退栈。 栈也称为后进先出表。

代码

public class MyStack {
    //底层实现是一个数组
    private long[] arr;
    // 数组下标
    private int top;

    /**
     * 默认构造方法
     */
    public MyStack() {
        arr = new long[10];
        top = -1;
    }

    /**
     * 带参数的构造方法
     *
     * @param maxSize 数组的初始化长度
     */
    public MyStack(int maxSize) {
        arr = new long[maxSize];
        top = -1;
    }

    /**
     * 添加数据（压栈）
     *
     * @param value 添加的数值
     */
    public void push(int value) {
        // ++top后top由-1变为了0，即第一个值添加到arr[0]的位置
        arr[++top] = value;
    }

    /**
     * 移除数据
     *
     * @return
     */
    public long pop() {
        return arr[top--];
    }

    /**
     * 查看栈顶数据
     *
     * @return
     */
    public long peek() {
        return arr[top];
    }

    /**
     * 判断是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 判断是否满了
     *
     * @return
     */
    public boolean isFull() {
        return top == arr.length - 1;
    }
}

测试

public class TestMyStack {
    public static void main(String[] args) {
        MyStack ms = new MyStack(4);
        ms.push(0);
        ms.push(1);
        ms.push(2);
        ms.push(3);
        System.out.println(ms.isEmpty());
        System.out.println(ms.isFull());
        System.out.println(ms.peek());
        while (!ms.isEmpty()){
            System.out.print(ms.pop()+" ");
        }
        System.out.println();
        System.out.println(ms.isEmpty());
        System.out.println(ms.isFull());
    }
}

结果

false
true
3
3 2 1 0 
true
false

从结果中可以看到，往栈中压入数据的顺序(0,1,2,3)和弹出数据的顺序(3,2,1,0)刚好相反。

队列

基本概念

队列的操作是在两端进行的，其中一端只能进行插入，该端称为队列的队尾，而另一端只能进行删除，该端称为队列的队首。
队列在我们日常生活中经常碰到，例如，排队买东西，谁先来，谁先买，买完就走，谁后来，谁在队的最后面排队。队列的运算规则是FIFO（first in first out），或者叫做先进先出。

代码

public class MyQueue {
    //底层实现是一个数组
    private long[] arr;
    //有效数据大小
    private int elements;
    //队头
    private int front;
    //队尾
    private int end;

    /**
     * 默认的无参构造
     */
    public MyQueue() {
        arr = new long[10];
        elements = 0;
        front = 0;
        end = -1;
    }

    /**
     * 带参数的构造方法
     *
     * @param maxSize
     */
    public MyQueue(int maxSize) {
        arr = new long[maxSize];
        elements = 0;
        front = 0;
        end = -1;
    }

    /**
     * 从队尾插入数据
     *
     * @param value
     */
    public void insert(long value) {
        if (end == arr.length - 1) {
            end = -1;
        }
        //每次都从队尾插入数据
        arr[++end] = value;
        elements++;
    }

    /**
     * 从队头删除数据
     *
     * @return
     */
    public long remove() {
        long value = arr[front++];
        if (front == arr.length) {
            front = 0;
        }
        elements--;
        return value;
    }

    /**
     * 从队头查看数据
     *
     * @return
     */
    public long peek() {
        return arr[front];
    }

    /**
     * 判断队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return elements == 0;
    }

    /**
     * 判断队列是否满了
     *
     * @return
     */
    public boolean isFull() {
        return elements == arr.length;
    }
}

测试

public class TestMyqueue {
    public static void main(String[] args) {
        MyQueue mq = new MyQueue(4);
        mq.insert(0);
        mq.insert(1);
        mq.insert(2);
        mq.insert(3);
        System.out.println(mq.isEmpty());
        System.out.println(mq.isFull());
        System.out.println(mq.peek());
        while (!mq.isEmpty()){
            System.out.print(mq.remove()+" ");
        }
        System.out.println();
        System.out.println(mq.isEmpty());
        System.out.println(mq.isFull());
    }
}

结果

false
true
0
0 1 2 3 
true
false

从结果中可以看到，往队列中添加数据的顺序(0,1,2,3)和移除数据的顺序(0,1,2,3)相同。